D言語を使って順列組み合わせ

はじめに

この記事では、
D言語での順列、組み合わせの取得方法について、記述します。

順列

標準ライブラリに２種類用意されています。

permutations

１つめは permutationsで、「Heapのアルゴリズム」を使って効率的に並び替えているとのこと。

permutations1.d

import std.stdio;
import std.algorithm.iteration;
void main()
{
  writefln("%(%s\n%)",['🍇','🍉','🍍'].permutations);
}

実行結果

🍇🍉🍍
🍉🍇🍍
🍍🍇🍉
🍇🍍🍉
🍉🍍🍇
🍍🍉🍇

permutations の実装例を記載しました。3つのフルーツを並び替えています。(全部で6通り)
実行結果のある行と次の行を見比べると、フルーツの並び替えは1回ずつですべての順列を取得していることがわかります。
ただ、直感的な見た目としては、わかりにくいですね。

nextPermutation

もう１つは、nextPermutation です。
予めソート済みの配列やrangeを並び替えることができます。

permutations2.d

import std.stdio;
import std.algorithm.sorting;
void main()
{
  auto fruits = ['🍇','🍉','🍍'];
  int[] idx = [0,1,2];
  do {
    writeln(fruits[idx[0]],fruits[idx[1]],fruits[idx[2]]);
  } while ( idx.nextPermutation );
}

実行結果

🍇🍉🍍
🍇🍍🍉
🍉🍇🍍
🍉🍍🍇
🍍🍇🍉
🍍🍉🍇

注意点として、ソートされていない配列でnextPermutationを使用すると、すべての順列を取得する前にfalseを返し、ループが終了してしまいます。そんな場合は、実装例のようにソート済みの配列idxをインデックスとして使用することで、うまく並べ替えできます。
ちなみに、実装例のフルーツ配列fruitsは文字コード順にソートされているため、idxを使わなくても並べ替え可能です。

組み合わせ

標準ライブラリを調べましたが、組み合わせの関数はなさそうです。
Rosetta Codeというサイトで、組み合わせが紹介されていましたので、こちらを参考に実装例を記載しました。
実装例のcombinationsを使えば、組み合わせが取得できます。
5つのフルーツ配列fruitsから、3つを選ぶ場合の組み合わせです。(全部で10通り)

combinations1.d

struct Combinations(T) {
  import std.traits: Unqual;
  
  Unqual!T[] pool, front;
  size_t[] index;
  size_t n, r;
  bool empty = false;
  
  this(T[] pool_, in size_t r_) pure nothrow @safe {
    this.pool = pool_.dup;
    this.n = pool.length;
    this.r = r_;
    if (r > n){
      empty = true;
    }
    front.length = r;
    index.length = r;
    foreach ( i; 0 .. r){
      front[i] = pool[i];
      index[i] = i;
    }
  }
  void popFront() pure nothrow @safe {
    if (!empty) {
      bool broken = false;
      size_t pos;
      foreach_reverse (immutable i; 0 .. r) {
        pos = i;
        if (index[i] != i + n - r) {
          broken = true;
          break;
        }
      }
      if (!broken) {
        empty = true;
        return;
      }
      index[pos]++;
      foreach (immutable i; pos + 1 .. r){
        index[i] = index[i - 1] + 1;
        front[i] = pool[index[i]];
      }
      front[pos] = pool[index[pos]];
    }
  }
}

Combinations!(T) combinations(T)(T[] items, in size_t k)
{
  return typeof(return)(items, k);
}

void main()
{
  import std.stdio;
  
  auto fruits = ['🍇','🍉','🍍','🍑','🍒'];
  foreach ( f; fruits.combinations(3) ){
    writefln("%s",f);
  }
}

実行結果

🍇🍉🍍
🍇🍉🍑
🍇🍉🍒
🍇🍍🍑
🍇🍍🍒
🍇🍑🍒
🍉🍍🍑
🍉🍍🍒
🍉🍑🍒
🍍🍑🍒

参考情報

参考までに、他のプログラミング言語についてのリンク情報です。