# All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k'

This is a discussion on All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k' within the C++ Programming forums, part of the General Programming Boards category; Hello, I'm trying to make a program that prints all the possible permutations of some strings, where order matters and ...

1. ## All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k'

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

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 = " 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;
}

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

Code:
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:

Code:
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").

2. You need to add the code to do combinations. You can try to figure this out for yourself, or do a web search for "next combination", or I can post example code if you still need help.

3. Thank you for the reply, an example would be very helpful.

4. Example code to do all combinations and permutations for n integers 0 to n-1. In this example, doc() generates the combinations, dop() generates the permutations, and showp() displays a permutation of integers. Change or replace the code to use the integers as indexes to the strings. This is C code, but easily converted to C++.

Code:
#include <stdio.h>
#include <malloc.h>

/* set to 0 to do only combinations */
#define DOPERM 1

static int n = 5;                       /* n integers */
static int k;                           /* taken k at a time */

static int *c;                          /* combinations */
static int *p;                          /* permutations */

static void doc(void);
static void dop(void);
static void swap(int, int);
static void showp(void);

/*----------------------------------------------------------------------*/
/*      main                                                            */
/*----------------------------------------------------------------------*/
int main(int argc, char *argv[])
{
c = malloc(n *  sizeof(int));       /* allocate arrays */
p = malloc(n *  sizeof(int));

for(k = 1; k <= n; k++)             /* n things k at a time */
doc();

free(p);                            /* free arrays */
free(c);

return(0);                          /* return */
}

/*----------------------------------------------------------------------*/
/*      doc         do combinations                                     */
/*----------------------------------------------------------------------*/
static void doc()
{
int i, j;

for (i = 0; i < k;  i++)            /* generate initial combination */
c[i] = i;

dop();                              /* do permutations */

while(1)                            /* generate next combination */
{
i = k-1;                        /* find next element to increment */
while(c[i] == (n-k+i))
--i;
if (i < 0)                      /* return if done */
return;
++c[i];                         /* increment element */

for(j = i+1; j < k; j++)        /* create increasing string */
c[j] = c[i]+j-i;

dop();                          /* do permutations */
}
}

/*----------------------------------------------------------------------*/
/*      dop         do permutations                                     */
/*----------------------------------------------------------------------*/
static void dop()
{
int i;
#if DOPERM
int j;
#endif

for (i = 0; i < k;  i++)            /* initial perm = comb */
p[i] = c[i];
printf("\n");
showp();                            /* show permutation */

#if DOPERM

if(k < 2)                           /* return if only 1 element */
return;

while(1)                            /* generate next permutation */
{

/*      scan backwards as long as p[] order is reversed */

i = k-2;                        /* scan backwards until */
while(p[i] >= p[i+1])           /* p[i] < p[i+1] */
i--;
if (i < 0)                      /* return if done (all reversed) */
return;

/*      p[i] is left most integer to swap */
/*      scan from right end until p[j] > p[i] is found */

j = k-1;                        /* scan backwards until */
while (p[j] <= p[i])            /* p[j] > p[i] */
j--;

/*      p[j] is right most integer to swap */

swap(i, j);                     /* swap elements */

/*      reverse p[] from p[i+1] to p[k-1] */

i++;                            /* reverse elements */
j = k-1;
while (i < j)
{
swap(i, j);
i++;
j--;
}

showp();                        /* show permutation */
}
#endif                                  /* #if DOPERM */
}

/*----------------------------------------------------------------------*/
/*      swap two elements of p                                          */
/*----------------------------------------------------------------------*/
static void swap(int i, int j)
{
int temp;

temp = p[i];
p[i] = p[j];
p[j] = temp;
}

/*----------------------------------------------------------------------*/
/*      showp       show permutation                                    */
/*----------------------------------------------------------------------*/
static void showp(void)
{
int i;

for (i = 0; i < k; i++)
printf(" %1d", p[i]);
printf("\n");
}

5. That's a pretty long example. I have a feeling a more minimal example would have been better.
It also does not do any justice in that it uses global arrays and malloc and free where C++ would not.
I can understand you want to show an example you would have lying around (if you wrote it from scratch, it really should be in C++), but this is a little extreme. It focuses on too much C than C++ alternatives, drawing a lot of attention from the logic to maintaining the correctness in the code due to low-level code.

6. Originally Posted by Elysia
That's a pretty long example.
The only code needed to be added to get combinations is this part. I added input parameters for this version (I think the syntax is correct, c should be a reference to an integer array).

Code:
/*----------------------------------------------------------------------*/
/*      doc         do combinations                                     */
/*----------------------------------------------------------------------*/
static void doc(int (&c)[], int k, int n)
{
int i, j;

for (i = 0; i < k;  i++)            /* generate initial combination */
c[i] = i;

dop();                              /* do permutations */

while(1)                            /* generate next combination */
{
i = k-1;                        /* find next element to increment */
while(c[i] == (n-k+i))
--i;
if (i < 0)                      /* return if done */
return;
++c[i];                         /* increment element */

for(j = i+1; j < k; j++)        /* create increasing string */
c[j] = c[i]+j-i;

dop();                          /* do permutations */
}
}

7. Originally Posted by rcgldr
The only code needed to be added to get combinations is this part. I added input parameters for this version (I think the syntax is correct, c should be a reference to an integer array).
Correction, c should be a pointer to integer.

8. Some braces are missing from the code above on the while loops that include check for i < 0. Here's the fixed code for the combination function doc():

Code:
//----------------------------------------------------------------------//
//      doc         do combinations                                     //
//----------------------------------------------------------------------//
static void doc(int *c, int k, int n)
{
int i, j;

for (i = 0; i < k;  i++)            // generate initial combination
c[i] = i;

dop(c, k);                          // do permutations

while(1)                            // generate next combination
{
i = k-1;                        // find next element to increment
while(c[i] == (n-k+i)){
--i;
if (i < 0)                  // return if done
return;
}
++c[i];                         // increment element

for(j = i+1; j < k; j++)        // create increasing string
c[j] = c[i]+j-i;

dop(c, k);                      // do permutations
}
}

9. Example program:

Code:
//----------------------------------------------------------------------//
//      cmbprmv.cpp  combinations and permutations example              //
//----------------------------------------------------------------------//
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int next_combination(vector <int> &, int, int);

//----------------------------------------------------------------------//
//      main                                                            //
//----------------------------------------------------------------------//
int main(int argc, char **argv)
{
string s = "string x";                  // numbered string
int n = 4;                              // n things k at a time
int i, k;

vector <string> vs(n);              // create vector of strings
for(i = 0; i < n; i++){
s[s.size()-1] = '0'+i;
vs[i] = s;
}

vector <int> c(n);                  // combination array

for(k = 1; k <= n; k++){            // n things k at a time
for(i = 0; i < k;  i++)         // create initial combination
c[i] = i;
do{                             // do combination
do{                         //    do permutation
for(i = 0; i < k; i++)
cout << vs[c[i]] << " ";
cout << endl;
}
while(next_permutation(c.begin(), c.end()));
cout << endl;
}
while(next_combination(c, k, n));
}

return(0);
}

//----------------------------------------------------------------------//
//      next_combination                                                //
//----------------------------------------------------------------------//
int next_combination(vector <int> &c, int k, int n)
{
int i, j;

i = k-1;                            // find next element to increment
while(c[i] == (n-k+i)){
--i;
if (i < 0)                      // return if done
return(0);
}

c[i] += 1;                          // increment element

for(j = i+1; j < k; j++)            // create increasing string
c[j] = c[i]+j-i;

return(1);                          // return with new combination
}

10. Fixed the example program (the parameters passed to next_permutation()). Updated next_combination() to set initial combination when done, similar to next_permutation() which sets the original permutation when done.

Code:
//----------------------------------------------------------------------//
//      cmbprmv.cpp  combinations and permutations example              //
//----------------------------------------------------------------------//
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int next_combination(vector <int> &, int, int);

//----------------------------------------------------------------------//
//      main                                                            //
//----------------------------------------------------------------------//
int main(int argc, char **argv)
{
string s = "string x";                  // numbered string
int n = 4;                              // n things k at a time
int i, k;

vector <string> vs(n);              // create vector of strings
for(i = 0; i < n; i++){
s[s.size()-1] = '0'+i;
vs[i] = s;
}

vector <int> c(n);                  // combination array

for(k = 1; k <= n; k++){            // n things k at a time
for(i = 0; i < k;  i++)         // create initial combination
c[i] = i;
do{                             // do combination
do{                         //    do permutation
for(i = 0; i < k; i++)
cout << vs[c[i]] << " ";
cout << endl;
}
while(next_permutation(c.begin(), c.begin()+k));
cout << endl;
}
while(next_combination(c, k, n));
}

return(0);
}

//----------------------------------------------------------------------//
//      next_combination                                                //
//----------------------------------------------------------------------//
int next_combination(vector <int> &c, int k, int n)
{
int i, j;

i = k-1;                            // find next element to increment
while(c[i] == (n-k+i)){
--i;
if (i < 0){                     // if done, ...
for(i = 0; i < k;  i++)
c[i] = i;
return(0);                  // ... return with initial combination
}
}

c[i] += 1;                          // increment element

for(j = i+1; j < k; j++)            // create increasing string
c[j] = c[i]+j-i;

return(1);                          // return with new combination
}

11. Four posts in a row without any input from the OP. Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?

12. Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?
O_o

I wonder what response we will get this time:

1): I know this is not homework, so posting complete solutions isn't a problem.
2): Posting complete solutions is how it is done at other forums I visit.
3): I don't value other people's education.

I'm thinking #4: all of the above.

Soma

13. Originally Posted by Elysia
That's a pretty long example. ... not C++ ... a more minimal example would have been better.
Originally Posted by Elysia
Four posts in a row without any input from the OP. Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?
The OP's code just uses next_permutation(), it's not like he's writing his own permutation code, and the OP could have just done a web search as I suggested to find a next_combination() function almost identical to the one I wrote, but the OP asked for example code.

I was just trying to create a minimal example (as you mentioned) of a C++ next_combination() function similar to the next_permutation() function that the OP uses in his code, except I'm not aware how to implement a generic next_combination() function that doesn't require a sequential sequence of integers 0 to n-1.

Sorry it took four posts to get it right. two of those posts were from intermediate and faulty versions where I copied to make a backup in the wrong direction in one or both cases and didn't notice this until it was too late to edit. I was tired and busy with other stuff. Next time I'll just wait a day when I have the proper amount of time to get it right before posting anything.

14. No one expects you to write bug-free code. No one expects you to post perfect code.
In fact, if you even embed some bugs in your code, it could serve as an exercise to the OP to find and fix them. I'm just saying it seems like you are throwing too much at the OP with too little sign of effort from the OP's side. Remember that we are also answering for their sake.

15. Originally Posted by Elysia
No one expects you to write bug-free code. No one expects you to post perfect code. In fact, if you even embed some bugs in your code, it could serve as an exercise to the OP to find and fix them. I'm just saying it seems like you are throwing too much at the OP with too little sign of effort from the OP's side. Remember that we are also answering for their sake.
OK, again I'm used to standard from another forum (physics forum). So when posting here, even when it's not homework, I should always ignore requests for example code until the OP has shown some effort to produce the code on his/her own and only post hints or corrections?

Page 1 of 2 12 Last