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

[user2988]

Hello, I'm trying to have a program that prints all the possible combinations of some strings, where order matters and so following the formula: C= n!/(n-k)!.
Now, I wrote this code with which I can have all the combinations, but not for "n" different from "k", what instead I'm actually looking for.
Here is the code:

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

int main () {
std::string sentence1 = " Sentence number one ";
std::string sentence2 = " Sentence number two ";
std::string sentence3 = " Sentence number three ";
std::string sentence4 = " 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;
}

Sorry if I make this message even longer, but just to clarify, that is an example of what I'm having:

1) string1 string2 string3 string4 string5 string6 string7 string8 string9 string10
2) string1 string2 string3 string4 string5 string6 string7 string8 string10 string9 
3) string1 string2 string3 string4 string5 string6 string7 string9 string8 string10
4) string1 string2 string3 string4 string5 string6 string7 string9 string10 string8 
....

while that is the kind of thing I'm trying to obtain:

1)  string1 string2 string3 string4 string5 
2)  string1 string2 string3 string4 string6 
3)  string1 string2 string3 string4 string7 
4)  string1 string2 string3 string4 string8 
5)  string1 string2 string3 string4 string9 
6)  string1 string2 string3 string4 string10 
7)  string1 string2 string3 string5 string4 
8)  string1 string2 string3 string5 string6
9)  string1 string2 string3 string5 string7
10) string1 string2 string3 string5 string8
11) string1 string2 string3 string5 string9
12) string1 string2 string3 string5 string10
....

As you can see, in the first one n=10 and k=10; in the second, n=10 but k=5 (5 "spaces").

Thank you in advance!

[giblit]

Are you trying to do combinations or permutations? The title and info says combination but in your code it looks like you are trying to get the permutations..
There is a difference fyi. Permutations order DOES matter and combination order does NOT matter.

If you are doing permutations maybe check out
http://www.cplusplus.com/forum/beginner/102375/#msg550608

[tntxtnt]

have a look at http://msdn.microsoft.com/en-us/library/aa289166.aspx

here is my Combination class (I tried to make it look like next_permutation) translated from the above article:

#include <iostream>
#include <vector>
#include <sstream>

class Combination
{
public:
    Combination(int n=1, int k=1);
    bool next_combination();
    int operator[](int i)const { return data[i]; }
private:
    int n;
    int k;
    std::vector<int> data;
};

Combination::Combination(int n, int k) : n(n), k(k)
{
    if (n<=0 || k<=0) n = k = 1;
    if (n<k) n = k;
    for (int i=0; i<k; ++i)
        data.push_back(i);
}

bool Combination::next_combination()
{
    if (n-k == data[0]) return false;
    int i = k-1;
    while (i>0 && data[i]==n-k+i) { --i; }
    ++data[i];
    for (int j=i; j<k-1; ++j)
        data[j+1] = data[j] + 1;
    return true;
}

int main()
{
    std::vector<std::string> mystrings;
    mystrings.push_back("string1");
    mystrings.push_back("string2");
    mystrings.push_back("string3");
    mystrings.push_back("string4");
    mystrings.push_back("string5");
    mystrings.push_back("string6");
    mystrings.push_back("string7");
    mystrings.push_back("string8");
    mystrings.push_back("string9");
    mystrings.push_back("string10");
    
    int n = mystrings.size();   // 10
    int k = mystrings.size()/2; // 5
    
    Combination mycombinator(n,k);
    int line = 1;
    
    do {
        std::cout << line++ << ") ";
        for (int i=0; i<k; ++i)
            std::cout << mystrings[ mycombinator[i] ] << " ";
        std::cout << "\n";
    } while (mycombinator.next_combination());
}

run: http://ideone.com/owhZO6

[user2988]

Yes, sorry. I just read the discussion you posted and I meant permutations then, I didn't know about the difference.
So now I could just use the last code you wrote and replace boolean with string, right? Should I make more changes to make it work properly?
Thanks.

[giblit]

Yeah if you are using permutations. If you are using combinations then go to that link tntxtnt sent or check out his code. Your assignment looks like it wants that even though in your code you are doing permutations.

[user2988]

Sorry tntxtnt, I didn't see your reply.
That is exactly what I was hoping to have as a result!

Thank you both for the help. :)

[user2988]

Sorry giblit,you're right, again...I just feel so stupid. I also said I would have modified the code myself, but I tried and I saw I'm not capable of doing it yet (I'm really new at C++). I got that I should modify some parts of your code and replace them with ones already in mine, but then there are things like "boolalpha" that I never heard about and I don't know how to handle...sorry if I'm annoying you.

[TheIdeasMan]

The reference info on this site (top left of this page) might help :

http://www.cplusplus.com/reference/algorithm/next_permutation/

Look at the example on how to deal with other types.

There is a wealth of info in the reference section & and the articles, & the tutorial in the documentation - I recommend reading up on it. Especially the reference for all the functions / algorithms / containers you might use.

[JLBorges]

> I'm trying to have a program that prints all the possible combinations of some strings,
> where order matters and so following the formula: C= n!/(n-k)!.
...
> and I saw I'm not capable of doing it yet (I'm really new at C++).

When in doubt, use brute force. - Ken Thompson

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <iomanip>

int main()
{
    std::vector<std::string> seq { "abc", "def", "abc", "ghi", "def", "abc" } ;
    std::sort( seq.begin(), seq.end() ) ;

    std::set< std::vector<std::string> > unique_permutations ;

    do unique_permutations.emplace( seq.begin(), seq.end() ) ;
    while( std::next_permutation( seq.begin(), seq.end() ) ) ;

    for( const auto& seq : unique_permutations )
    {
        static int n = 0 ;
        std::cout << std::setw(3) << ++n << ". " ;
        for( const auto& str : seq ) std::cout << str << ' ' ;
        std::cout << '\n' ;
    }
}

http://ideone.com/lSX8S8 (GCC 4.7, so without emplace() )