std :: next_permutation缺少一個條目

以下程序缺少一個置換條目。std :: next_permutation缺少一個條目

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main (int argc, char **argv) { 
    std::vector<int> temp; 
    temp.push_back(10); 
    temp.push_back(2); 
    temp.push_back(4); 
    temp.push_back(4); 

    do { 
     std::copy(temp.begin(),temp.end(),std::ostream_iterator<int>(std::cout," ")); 
     std::cout << std::endl; 
    }while (std::next_permutation (temp.begin(), temp.end())); 
}

以下是節目

10 2 4 4 
10 4 2 4 
10 4 4 2

的輸出爲什麼它缺少一個條目，這是

2 4 4 10

來源

2011-12-27 Avinash

這是因爲置換是列表中的第一順序你擁有的數量。您需要對原始數組進行排序，然後這個排列將被列爲第一個排列。

std::vector<int> temp; 
temp.push_back(10); 
temp.push_back(2); 
temp.push_back(4); 
temp.push_back(4); 
std::sort(temp.begin(),temp.end());

或者，你可能只是在推有序的元素，但爲了實用的目的，你應該總是排序，如果你想生成所有可能的排列。

來源

2011-12-27 06:53:16

另一種方法是使用適當的數學公式計算應該有多少置換，然後只是多次迭代，而忽略來自next_permutation的返回值。 – 2011-12-27 06:56:34

如果您知道它已經分類，則不應該對容器進行排序。 – wilhelmtell 2011-12-27 06:56:51

@KarlKnechtel由於整數溢出，這可能不是微不足道的。 – wilhelmtell 2011-12-27 06:58:16

它實際上缺少一些其他有效的置換：例如，2 10 4 4和2 4 10 4和4 4 10 2。

至於他們爲什麼丟失：它說，那裏的文檔中：

返回值 true如果函數能重新排列對象作爲字典順序排列更大。否則，該函數返回false以指示排列不大於前一個，但是最小（按升序排序）。

所以while循環10 4 4 2結束後，因爲那是最偉大的字典序排列（一說是「最大的」，當你比較他們左到右，即一個是按降序排列）。在打印那個之後，next_permutation不能進入'下一個'置換，並且回到2 4 4 10的「開始」置換;但是不會打印，因爲函數也返回false。

來源

2011-12-27 06:55:16

std :: next_permutation缺少一個條目

回答

相關問題