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

从其中包含 1 的最小数字开始l：(1 << l) - 1

然后应用NextBitPermutation直到达到最高数字，即lowest << k.

score 2 · Accepted Answer

从 k 0s 后跟 l 1s 的排列开始。重复此步骤，同时您可以：

找到q 1s (q > 0)的最右边一段，前面是 0，后面是 r 0s (r >= 0)。将其全部替换为 1，然后是 (r+1) 0s，然后是 (q-1) 1s。那将是你的下一个排列。

score 1 · Accepted Answer

1

DEKnuth生成所有排列

见第一章开头的Algorithm L(lexicographic permutation generation)

于 2013-03-01T17:32:15.637 回答

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