如何按字典顺序生成由`k`` 0``和`l``1``组成的集合的所有排列？

如何生成从k0's和l1's按字典顺序排列的所有排列组合？我正在寻找伪代码或C++代码。实施例：如何按字典顺序生成由`k`` 0``和`l``1``组成的集合的所有排列？

功能next_perm01应该这样工作：next_perm01(permutation_{i})=next_perm01(permutation_{i-1})我发现，用于产生一组不同的元素的所有排列唯一方法。

来源

2013-03-01 Qbik

这是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)); 
}

输出对我来说是：

来源

2013-03-01 14:30:34

开始与具有l 1在它最低的数字： (1 << l) - 1

然后应用NextBitPermutation，直到达到最高号码，即lowest << k。

来源

2013-03-01 14:34:12 harold

以k 0s和l 1s的排列开始。重复此步骤，而可以：

查找一个0之前和之后用r 0 q 1秒（Q > 0）的最右边拉伸（R > = 0）。全部替换为1，然后是（r + 1）0s，然后是（q-1）1s。这将是你的下一个排列。

来源

2013-03-01 14:42:20

如果我理解正确的话，那么对于一个字符串的一般算法可能是：

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

*由于N.M.指出我的错误。

来源

2013-03-01 15:38:20

如何从'0011'得到'1001'年初D.E.Knuth

见算法L（字典排列代）？ – 2013-03-02 08:41:27

@ n.m。我的算法将从'0011'变为'0101'。你为什么要从'0011'去'1001'？ – 2013-03-02 14:36:53

我不希望它直接从'0011'到'1001'，我希望它最终到达那里。它会永远吗？ – 2013-03-02 14:46:29