[解決済み] 並べ換えの遅延生成

質問

Clojureで遅延リストを作成するような方法で、セットの並べ換えを生成するアルゴリズムを探しています。つまり、並べ換えのリストに対して反復処理を行い、各並べ換えは私が要求するまで計算されず、すべての並べ換えが一度にメモリに格納される必要はありません。

代わりに、私はある集合が与えられると、その集合の "next"順列を返すようなアルゴリズムを探しています。それは、それ自身の出力で繰り返し関数を呼び出すと、ある順序で元の集合のすべての順列を循環するような方法です（順序は重要ではありません）。

そのようなアルゴリズムはあるのでしょうか？ 私が見た順列生成アルゴリズムのほとんどは、一度に（通常は再帰的に）それらを生成する傾向があり、これは非常に大きな集合にスケールしません。 Clojure（または他の関数型言語）での実装は有用でしょうが、私は擬似コードからそれを見つけ出すことができます。

どのように解決するのですか？

はい、そこで です。 というアルゴリズムがあり、それも非常に単純です。C++の標準テンプレートライブラリ(STL)には next_permutation .

このアルゴリズムでは、実際に の次に の順列、つまり辞書的に次の順列を見つけます。例えば、32541 のようなシーケンスが与えられたとします。次の並べ換えは何でしょうか？

よく考えてみると、それは "34125" であることがわかると思います。そして、あなたの考えは、おそらく次のようなものだったでしょう。で、"32541"です。

• は、"32" を固定したまま、"541" の部分で後の順列を見つける方法はありません。なぜならその順列はすでに 5、4、および 1 の最後のもので、それは降順にソートされています。
• したがって、"2" をより大きなものに--実際には、"541" の部分でそれより大きい最小の数、すなわち 4 に--変更する必要があります。
• さて、順列が "34" として始まると決めたら、残りの数字は増加する順序になるはずなので、答えは "34125" となります。

アルゴリズムは、まさにその推論のラインを実装することです。

1. 降順に並べられた最も長い "tail" を見つけなさい。("541" の部分です)。
2. 末尾の直前の数（"2"の部分）を末尾のそれよりも大きい最小の数（4）に変えなさい。
3. tail を昇順にソートします。

(1.)は、前の要素が現在の要素より小さくない限り、最後から始めて逆行することで効率的に行えます。(2.)は、"4" と '2" を入れ替えるだけで、"34521" とすることができます。一度これを行えば、(3.)のソートアルゴリズムを使用せずに済みます。なぜなら、テールは昔も今も（これについて考えてみてください）降順でソートされているので、それを逆にすればよいだけだからです。

C++のコードはまさにこれを行います(ソースを見てください。 /usr/include/c++/4.0.0/bits/stl_algo.h のソースを見るか、あるいは この記事 を参照); それをあなたの言語に翻訳するのは簡単なはずです。[C++のイテレータに馴染みがなければ、 "BidirectionalIterator" を "pointer" と読めばよいでしょう。このコードでは false を返します。これは次の順列がない場合、つまり、すでに降順になっている場合です]。

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

順列ごとに O(n) の時間がかかるように見えるかもしれませんが、もっと注意深く考えると、すべての順列の合計で O(n!) の時間がかかるので、順列ごとに O(1) -- 定数時間 -- だけであることが証明できます。

良いことに、このアルゴリズムは要素が繰り返されるシーケンスでも動作します。たとえば "232254421" では、末尾を "54421" として見つけ、 "2" と "4" を交換し ("232454221") 残りを逆にして "232412245" とし、それが次の順列となる、ということです。