How can I write all the combinations of 'n' strings? With Repetition: C=n!/(n-k)!

Question

Sorry if the question is not clear, I was wondering how to write a program in C++ that can output all the combination of some sentences, using the formula C=n!/(n-k)!. For example, that is the kind of thing I'm trying to have printed:

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

Also, is it possible to have up to 1 billion of combinations or there are some restrictions?

EDIT.

I tried the following program, but I can't find a way to change what in the formula above is the "k" variable.

// 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;
}

Just a tip: requests to "please write my whole program for me" are not looked on very favorably. — Jonathan Potter, Jun 19 '13 at 20:24

score 2 · Answer 1 · edited May 23 '17 at 11:44

You probably mean you want all the possible combinations of 'n' strings. There are n! possible cases. You can use the std::next_permutation Here is how :

I suppose that all your sentences are std::string like this :

// 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;
}

This is a simple example for the printing. If you had more than 4 strings, inside the do-while loop you would use something like this

The do-while loop would then be :

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()) );

Also, is it possible to have up to 1 billion of combinations or there are some restrictions?

The only restrictions is the memory. In this example you have only 1 vector that stores all the strings. so if you have 10 strings, you will have 10! = 3,628,800 different combinations , but the memory itself is only the memory used by your vector that has 10 strings.

How can I change the value of what in the formula is k? – user2499266 Jun 19 '13 at 23:42 — user2499266, Jun 19 '13 at 23:42

score 1 · Answer 2 · edited Jun 19 '13 at 20:22

1

You can use next_permutation to do this.

edited Jun 19 '13 at 20:22

user123

8,970
2
31
52

answered Jun 19 '13 at 20:19

zw324

26,764
16
85
118

How can I write all the combinations of 'n' strings? With Repetition: C=n!/(n-k)!

2 Answers2