All the possible combinations of 'n' strings, with repetitions: C= n!/(n-k)!

Question

I'm trying to have something like this:

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...

Now, using the following code, how can I handle what in the formula is the "k" variable? There is something missing? Again, it's about combinations with repetitions so I think the formula is C= n!/(n-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;
}

I know, you're probably right. I tried to read it, but the fact is that it's still too difficult for me. So I was hoping in a easier way to deal with the problem. — user2499266, Jun 20 '13 at 03:21

score 0 · Answer 1 · answered Jun 20 '13 at 04:34

The k which you are saying is handled automatically. Suppose, if instead you insert two similar sentences into the vector, say there are 4 sentences and two of them are same. Then the total number of permutations are 4!/2!=12. So, the function only prints 12 permutations, (not 24). See the output of your modified code with similar sentences here:

All the possible combinations of 'n' strings, with repetitions: C= n!/(n-k)!

1 Answers1