algorithm - `k``0's`と`l``1's`からなる集合のすべての順列を辞書式順序で生成するにはどうすればよいですか？

Question

辞書式順序でk 0's構成されるセットのすべての順列を生成するにはどうすればよいですか？l 1's擬似コードまたはC++コードを探しています。例：

関数は次のようにnext_perm01動作するはずです： next_perm01(permutation_{i})=next_perm01(permutation_{i-1})異なる要素のセットのすべての順列を生成する方法しか見つかりませんでした。

score 4 · Accepted Answer

l1が含まれる最小の数字から始めます。(1 << l) - 1

次に、最大数であるに達するまでNextBitPermutationlowest << kを適用します。

score 2 · Accepted Answer

k 個の 0 の順列から始まり、その後に l 個の 1 が続きます。次のことができるまで、この手順を繰り返します。

q 1 (q > 0)の右端のストレッチを見つけます。前に 0 があり、その後に r 0 (r >= 0) が続きます。すべてを 1 に置き換え、その後に (r+1) 0 と (q-1) 1 を続けます。それが次の順列になります。

score 1 · Accepted Answer

DEKnuthによるすべての順列の生成

最初の章の冒頭にあるアルゴリズムL（辞書式順列の生成）を参照してください。

score 1 · Accepted Answer

私が正しく理解していれば、文字列の一般的なアルゴリズムは次のようになります。

nextPermutation string =
scan string from right to left
replace first occurrence of "01" with "10"
move all "1"'s that are on the right of the "01" to the string end*
return replaced string

*私の間違いを指摘してくれたnmに感謝します。

score 0 · Accepted Answer

これは Java ですが、これは疑似コードと見なすことができます。

public static boolean nextPermutation (int [] permutation)
{
    int l = permutation.length;
    if (l < 2) return false;
    else
    {
        int i = l - 1;
        while (i >= 0 && permutation [i] == 0)
            i--;

        int j = 0;
        while (i >= 0 && permutation [i] == 1)
        {
            i--;
            j++;
        }

        if (i < 0) return false;
        else
        {
            permutation [i] = 1;

            Arrays.fill (permutation, i + 1, l - j + 1, 0);
            Arrays.fill (permutation, l - j + 1, l, 1);

            return true;
        }
    }
}

public static void main(String[] args) {
    int [] permutation = new int [] {0, 0, 0, 1, 1, 1, 1};
    do
    {
        for (int i: permutation)
            System.out.print(i);
        System.out.println();
    } while (nextPermutation(permutation));
}

私にとっての出力は次のとおりです。

algorithm - `k``0's`と`l``1's`からなる集合のすべての順列を辞書式順序で生成するにはどうすればよいですか？

5 に答える 5

Related

Reference