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

#はじめに

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

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

##permutations

１つめは [permutations](https://dlang.org/library/std/algorithm/iteration/permutations.html)で、「Heapのアルゴリズム」を使って効率的に並び替えているとのこと。

https://ja.wikipedia.org/wiki/Heap%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

https://en.wikipedia.org/wiki/Heap%27s_algorithm

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

```txt:実行結果
🍇🍉🍍
🍉🍇🍍
🍍🍇🍉
🍇🍍🍉
🍉🍍🍇
🍍🍉🍇
```

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

##nextPermutation

もう１つは、[nextPermutation](https://dlang.org/library/std/algorithm/sorting/next_permutation.html) です。
予めソート済みの配列や`range`を並び替えることができます。

```d: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 );
}
```

```txt:実行結果
🍇🍉🍍
🍇🍍🍉
🍉🍇🍍
🍉🍍🍇
🍍🍇🍉
🍍🍉🍇
```

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

#組み合わせ

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

```d: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);
  }
}
```

```txt:実行結果
🍇🍉🍍
🍇🍉🍑
🍇🍉🍒
🍇🍍🍑
🍇🍍🍒
🍇🍑🍒
🍉🍍🍑
🍉🍍🍒
🍉🍑🍒
🍍🍑🍒
```

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

https://maku77.github.io/java/numstr/permutation.html

https://qiita.com/5zm/items/949bf0721e8324f0ee35

https://qiita.com/s-katsumasa/items/7b8ce83df22467f74c51

https://qiita.com/kokardy/items/a18b574d548c212e58e6

https://qiita.com/herara_ofnir3/items/d4e4d4516e8271d34d3f

https://kamino.hatenablog.com/entry/cpp-permutation-combination

http://www5.airnet.ne.jp/tomy/cpro/perm.htm

https://qiita.com/namitop/items/5ff20790fd1ea102e002

https://qiita.com/BlueSilverCat/items/77f4e11d3930d7b8959b

http://jecteca.blogspot.com/2012/08/php.html