Prev_permutation vs Next_permutation難度

我正在嘗試一個示例程序來掌握prev和next排列之間的區別。但是，我的程序似乎不能正常工作。我通過詢問陣列中元件的數量啓動該程序並我建立與一個簡單的陣列，用於循環Prev_permutation vs Next_permutation難度

for(i = 0; i < x; i++) 
     ptr[i] = i; 

cout << "Possible permuations using prev_permutation: " << endl; 
    do{ 
     for(i = 0; i < x; i++) 
      cout << ptr[i] << " "; 
     cout << endl; 
    } while(prev_permutation(ptr, ptr+x)); 

cout << "Possible permuations using next_permutation: " << endl; 
do{ 
    for(i = 0; i < x; i++) 
     cout << ptr[i] << " "; 
    cout << endl; 
} while(next_permutation(ptr, ptr+x));

當運行具有3種元素的樣品的代碼，（0，1，2）。 prev_permutation給我（0，1，2和多數民衆贊成它）。然後next_permutation給我（2，1，0）。但是，當我評論prev_permutation部分的代碼時，只有在next_permutation正在運行時，我才能得到6個不同的集合排列（0,1,2）。我似乎無法理解發生了什麼。

來源

2012-09-01 Josh

prev_permutation和next_permutation生成詞典編纂所有排列（「字母」），爲了和它們返回false一旦週期已經完成（即，如果在第一置換，或在最後一個調用next_permutation後調用prev_permutation後）。

會發生什麼情況是，您按字典順序排列第一個排列，然後調用prev_permutation。然而，這是第一個，因此prev_permutation將數組設置爲最後一個排列並返回false，因此您退出循環。

現在你輸入next_permutation循環，但數組的當前內容是字典順序中的最後一個排列，所以next_permutation將設置第一個並且將返回false。

如果您刪除prev_permutation部件，但next_permutation的循環將從第一個開始，因此在返回false之前它將正確生成所有6個排列。

您可以可視化考慮，以便與當前的配置在這個列表中的指針中列出的所有排列的效果：

0-1-2 << you start here 
0-2-1 
1-0-2 
1-2-0 
2-0-1 
2-1-0

調用next_permutation當你向下移動，通話prev_permutation你動起來的時候。當超出列表時，這兩個函數都會將指針移動到另一端，並將返回false來通知您這一事實。

如果你開始prev你移動到2-1-0和函數返回false，然後調用next和功能轉移到0-1-2並再次返回false。

使用例如不是0，1和2的排列兩個零點和三一的詞典式排序是：

0-0-1-1-1 
0-1-0-1-1 
0-1-1-0-1 
0-1-1-1-0 
1-0-0-1-1 
1-0-1-0-1 
1-0-1-1-0 
1-1-0-0-1 
1-1-0-1-0 
1-1-1-0-0

於是枚舉所有的人都需要從0-0-1-1-1啓動和使用next_permutation或您需要從1-1-1-0-0開始並使用prev_permutation。

在這種情況下，呼籲最後一個1-1-1-0-0next_permutation將改變爲第一0-0-1-1-1並且將返回false;以類似的方式在0-0-1-1-1上調用prev_permutation將更改爲1-1-1-0-0並且由於翻轉將返回false。

來源

2012-09-01 19:39:25 6502

我有一個簡單的問題。當你說，名單按照字典順序排列，這是否意味着價值？例如，我用輸入（1 1 1 0 0）運行了另一個prev_permutation示例。在我運行這個之後，我得到了所有可能的排列，但我不明白prev和next會如何確定下一個排列是什麼。謝謝。 – Josh

字典順序意味着要決定一個順序是在一個順序之前還是之後，首先比較第一個元素，如果它不同，那麼第一個元素決定順序......如果它們相等，那麼你移動到第二個元素，等等。在三個1和兩個零的置換中，置換'（1 1 1 0 0）'是字典順序中的最後一個，所以你可以從那裏使用'prev_permutations'循環所有的排列。第一個是'（0 0 1 1 1）'，你可以使用'next_permutation'從它開始循環所有的排列。 – 6502

感謝您的澄清！是否有可能通過next_permutation運行一組（0 0 0 1 1），然後獲得FINAL結果並運行prev_permutation以獲取0 0 0 1 1？所以，如果我將值存儲在一個數組中，這個函數是否會改變數組的值。 – Josh

由prev_permutation和next_permutation兩者考慮的所有排列具有明確定義的字典順序。您提供給他們的數組在這個順序中有一些位置。

這就是爲什麼這兩個函數都不能保證提供所有排列。

如果您向prev_permutation提供了第一種可能的排列方式，那麼在排除它之前不會有排列組合。同樣，如果你的數組被定義爲（2,1,0），next_permutation不會提供任何新的排列。

如果您需要某些集合的所有排列，您首先需要sort集合，然後使用next_permutation。

來源

2012-09-01 19:40:07

Prev_permutation vs Next_permutation難度

回答

相關問題