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

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.

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

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

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.

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

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
}

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

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.

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?