D言語にもnextPermutationあるんですけどね(ごり押し)
— W521 (@yosupot) October 13, 2017
このツイートを見て「そうだったのか！知らなかった！」と言ってググったが目が節穴なのでこうして記事を書きはじめるまで目の前の検索結果が読めなかった。
悔しいので無視して「D言語 next_permutation」では出てこなかったので記事を書く。
std.algorithm.sorting.nextPermutation
C++のnext_permutationと同じもの。
void main()
{
import std.stdio;
import std.algorithm : nextPermutation;
auto ary = [1,2,3];
do
{
writeln(ary);
}
while(nextPermutation(ary));
}
BidirectionalRangeを全部の並べ方を列挙できるようにIn-placeで入れ替える。
最後になるとfalseを返すため、上記のようにdo-whileで全パターンを列挙できる。
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
C++と同じように、全パターンを列挙するためには最初がソート済みでなければならない。
void main()
{
import std.stdio;
import std.algorithm : nextPermutation;
auto ary = [3,2,1]; // ソートされていない
do
{
writeln(ary);
}
while(nextPermutation(ary));
}
[3, 2, 1]
std.algorithm.iteration.Permutations
こちらはより汎用的に使える。
与えられたRangeのすべての並べ方のPermutations!Range、順列を返す。
ソート済みでなくても、そもそも要素が比較可能でなくともいいようだ。
void main()
{
import std.stdio;
import std.algorithm : permutations, nextPermutation;
import std.complex : complex;
auto ary = [complex(1,1),
complex(2,0),
complex(3,-1)]; // 比較ができないためnextPermutationは動かない
permutations(ary).writeln();
}
[[1+1i, 2+0i, 3-1i], [2+0i, 1+1i, 3-1i], [3-1i, 1+1i, 2+0i], [1+1i, 3-1i, 2+0i], [2+0i, 3-1i, 1+1i], [3-1i, 2+0i, 1+1i]]
“Heap’s algorithm"というのを使っているらしいが、日本語の情報が全然なくてつらいので理解できたらまた別に記事を書こうと思う。
追記
Wikipediaの記事 “Heap’s algorithm"を翻訳した。