如何編寫'n'字符串的所有組合？重複：C = n！/（n-k）！

Question

對不起，如果問題不清楚，我想知道如何用C++編寫一個程序，它可以輸出所有句子的組合，使用公式C=n!/(n-k)!。例如，這是我想已打印的那種東西：

combination no 1: sentence1 sentence2 sentence3 sentence4 

combination no 2: sentence1 sentence2 sentence4 sentence3 

combination no 3: sentence1 sentence3 sentence2 sentence4 

combination no 4: sentence1 sentence3 sentence4 sentence2 

combination no 5: sentence1 sentence4 sentence3 sentence2 

combination no 6: sentence1 sentence4 sentence2 sentence3 

And so on... 

而且，是有可能有高達1十億組合的或有一些限制？

編輯。

我試過下面的程序，但是我找不到方法來改變上面公式中的「k」變量。

// next_permutation example 
#include <iostream>  // std::cout 
#include <algorithm> // std::next_permutation, std::sort 
#include <string>  // std::string 
#include <vector>  // std::vector 

int main() { 
    std::string sentence1 = " A Sentence number one "; 
    std::string sentence2 = " B Sentence number two "; 
    std::string sentence3 = " C Sentence number three "; 
    std::string sentence4 = " D Sentence number four "; 

    // Store all the elements in a container (here a std::vector) 
    std::vector<std::string> myVectorOfStrings;  
    // In the vector we add all the sentences. 
    // Note : It is possible to do myVectorOfStrings.push_back("Some sentence"); 
    myVectorOfStrings.push_back(sentence1); 
    myVectorOfStrings.push_back(sentence2); 
    myVectorOfStrings.push_back(sentence3); 
    myVectorOfStrings.push_back(sentence4); 

    // The elements must be sorted to output all the combinations 
    std::sort (myVectorOfStrings.begin(),myVectorOfStrings.end()); 


    std::cout << "The 4! possible permutations with 4 elements:\n"; 
    do { 
    //This printing can be improved to handle any number of sentences, not only four. 
    std::cout << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 
    } while (std::next_permutation(myVectorOfStrings.begin(),myVectorOfStrings.end())); 

    std::cout << "After loop: " << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 

    return 0; 
} 

Answer 1

您可以使用next_permutation來做到這一點。

Answer 2

你可能表示你想要所有'n'字符串的可能組合。 還有n！可能的情況。 可以使用std::next_permutation 方法如下：

我想，所有的句子中的std :: string這樣的：

// next_permutation example 
#include <iostream>  // std::cout 
#include <algorithm> // std::next_permutation, std::sort 
#include <string>  // std::string 
#include <vector>  // std::vector 

int main() { 
    std::string sentence1 = " A Sentence number one "; 
    std::string sentence2 = " B Sentence number two "; 
    std::string sentence3 = " C Sentence number three "; 
    std::string sentence4 = " D Sentence number four "; 

    // Store all the elements in a container (here a std::vector) 
    std::vector<std::string> myVectorOfStrings;  
    // In the vector we add all the sentences. 
    // Note : It is possible to do myVectorOfStrings.push_back("Some sentence"); 
    myVectorOfStrings.push_back(sentence1); 
    myVectorOfStrings.push_back(sentence2); 
    myVectorOfStrings.push_back(sentence3); 
    myVectorOfStrings.push_back(sentence4); 

    // The elements must be sorted to output all the combinations 
    std::sort (myVectorOfStrings.begin(),myVectorOfStrings.end()); 


    std::cout << "The 4! possible permutations with 4 elements:\n"; 
    do { 
    //This printing can be improved to handle any number of sentences, not only four. 
    std::cout << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 
    } while (std::next_permutation(myVectorOfStrings.begin(),myVectorOfStrings.end())); 

    std::cout << "After loop: " << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 

    return 0; 
} 

這是打印一個簡單的例子。 如果你有超過4串時，do-while循環中，你會使用類似this

的do-while循環將被：

do { 
    //Print all the sentences in my vector : 
    for(auto i = myVectorOfStrings.begin(); i != myVectorOfStrings.end(); ++i) 
    std::cout << *i << ' '; 
    // Go to the next line 
    std::cout << std::endl; 
} while (std::next_permutation(myVectorOfStrings.begin(),myVectorOfStrings.end())); 

而且，是有可能有高達10億的組合還是有 有一些限制？

唯一的限制是內存。 在這個例子中，你只有1個存儲所有字符串的向量。 所以如果你有10個字符串，你會有10個！ = 3,628,800種不同的組合，但內存本身只是你的矢量使用的有10個字符串的內存。