如何按字典順序生成由`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