How to generate all possible permutations with repetitions?

Discussion in 'C Programming' started by darin dimitrov, Oct 26, 2004.

  1. Hello,

    I need help with an algoritm that given a set of "n" distinct
    numbers will
    generate all the possible permutations of fixed length "m" of these
    numbers WITH repetitions (a total of n^m possibilities). For example:

    given the set {1, 2} would output: 111,112,121,122,211,212,221,222 if
    we fix m=3.

    What I could do so far is an iterative algorithm which could be used
    only if we know before runnin the program "m" and "n" which is not
    often the case :)

    int n=2; //stores the numebr of elements in the set
    int m=3; //stores the length of the desired permutation
    char s[] = "12"; //stores our set of numbers
    char s1[] = new char[m]; //will store every permutation generated (of
    length 3)
    int i, j, k; // loop variables

    for (i=0; i<length(s); i++) { // first loop
    for (j=0; j<length(s); j++) { // second loop
    for (k=0; k<length(s); k++) { // third loop
    // this code is executed 2^3=8 times
    s1[0] = s;
    s1[1] = s[j];
    s1[2] = s[k];
    printf("%s\n", s1); // print the permutation
    }
    }
    }


    How can I generalize this for any m and n? I suppose some sort of a
    recursive algorithm should be used (I don't believe this can be done
    by simply iterating). Unfortunately I don't feel much confortable with
    recursion. In fact what I am looking for is what would be the
    recursive version of the following multiple loops algorithm:

    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    for (k=0;k<n;k++)
    for (l=0;l<n;l++)
    etc... (m times)
    // Do something here
    }
    }
    }
    }


    Could you help me with some pseudo code please? And please appologize
    me if the term "permutation" that I used here is not correct.

    Thanks,
    Darin
     
    darin dimitrov, Oct 26, 2004
    #1
    1. Advertising

  2. darin dimitrov

    Michael Mair Guest

    darin dimitrov wrote:
    > Hello,
    >
    > I need help with an algoritm that given a set of "n" distinct
    > numbers will
    > generate all the possible permutations of fixed length "m" of these
    > numbers WITH repetitions (a total of n^m possibilities). For example:
    >
    > given the set {1, 2} would output: 111,112,121,122,211,212,221,222 if
    > we fix m=3.
    >
    > What I could do so far is an iterative algorithm which could be used
    > only if we know before runnin the program "m" and "n" which is not
    > often the case :)
    >
    > int n=2; //stores the numebr of elements in the set
    > int m=3; //stores the length of the desired permutation
    > char s[] = "12"; //stores our set of numbers
    > char s1[] = new char[m]; //will store every permutation generated (of

    new is C++, not C: Use malloc()
    > length 3)
    > int i, j, k; // loop variables
    >
    > for (i=0; i<length(s); i++) { // first loop
    > for (j=0; j<length(s); j++) { // second loop
    > for (k=0; k<length(s); k++) { // third loop
    > // this code is executed 2^3=8 times
    > s1[0] = s;
    > s1[1] = s[j];
    > s1[2] = s[k];
    > printf("%s\n", s1); // print the permutation
    > }
    > }
    > }

    Your C++ code lacks a delete s1 here, in C: a free() call.

    > How can I generalize this for any m and n? I suppose some sort of a
    > recursive algorithm should be used (I don't believe this can be done
    > by simply iterating). Unfortunately I don't feel much confortable with
    > recursion. In fact what I am looking for is what would be the
    > recursive version of the following multiple loops algorithm:
    >
    > for (i=0;i<n;i++)
    > for (j=0;j<n;j++)
    > for (k=0;k<n;k++)
    > for (l=0;l<n;l++)
    > etc... (m times)
    > // Do something here
    > }
    > }
    > }
    > }
    >
    >
    > Could you help me with some pseudo code please? And please appologize
    > me if the term "permutation" that I used here is not correct.


    You need a depth counter to find out in which "loop" you are,
    then you run the respective loop.
    Try this:

    #include <stdio.h> /* puts, fputs; stderr, stdout */
    #include <stdlib.h> /* malloc, exit */
    #include <string.h> /* strlen */

    void permutate_n_plus (char *str, size_t n, const size_t maxdepth,
    const char *baseset, const size_t numbase)
    {
    size_t i;
    char *currpos = &str[n-1];
    const char *currchar = baseset;

    if (n<maxdepth) { /* We are in an outer loop */
    /* run through the baseset for the current depth,
    ** call permutate_n_plus() for greater depths */
    for (i=0; i<numbase; i++) {
    *currpos = *currchar++;
    permutate_n_plus(str, n+1, maxdepth, baseset, numbase);
    }
    }
    else { /* We are in the innermost (output) loop */
    /* run through the baseset for the current depth,
    ** write out the result */
    for (i=0; i<numbase; i++) {
    *currpos = *currchar++;
    fputs(str, stdout);

    /* Uncomment this for immediate output
    fflush(stdout);
    */
    }

    }
    }

    int main (int argc, char **argv)
    {
    char *string, *baseset;
    size_t maxdepth;
    unsigned long tmp;

    if (argc!=3) {
    puts("Usage:\n\t<program> baseset width");
    exit(EXIT_SUCCESS);
    }

    baseset = argv[1];
    if ( (tmp = strtoul(argv[2],NULL,10)) == 0 )
    exit(EXIT_SUCCESS);

    if ( (maxdepth = (size_t) tmp) != tmp ) {
    fputs("width too large", stderr);
    exit(EXIT_FAILURE);
    }

    if ( (string = malloc(maxdepth + 2)) == NULL ) {
    fputs("cannot allocate memory for output string", stderr);
    exit(EXIT_FAILURE);
    }

    /* insert separator and terminate string */
    string[maxdepth] = '\t';
    string[maxdepth+1] = '\0';

    permutate_n_plus(string, 1, maxdepth, baseset, strlen(baseset));
    puts("");

    free(string);
    exit(EXIT_SUCCESS);
    }

    -------
    BTW: You do not need recursion. If the overall number of runs through
    the second-to-innermost loop is less than ULONG_MAX, you can use one
    loop index to designate the position to be changed.
    Another way is creating an array of depth counters each of which runs
    through the number of different characters just in the way it would
    happen when you were using the recursive call. And so on... :)


    Cheers
    Michael
    --
    E-Mail: Mine is a gmx dot de address.
     
    Michael Mair, Oct 26, 2004
    #2
    1. Advertising

  3. darin dimitrov

    Alex Fraser Guest

    "darin dimitrov" <> wrote in message
    news:...
    > I need help with an algoritm that given a set of "n" distinct
    > numbers will
    > generate all the possible permutations of fixed length "m" of these
    > numbers WITH repetitions (a total of n^m possibilities). For example:
    >
    > given the set {1, 2} would output: 111,112,121,122,211,212,221,222 if
    > we fix m=3.

    [snip code that wasn't quite C anyway]
    > How can I generalize this for any m and n? I suppose some sort of a
    > recursive algorithm should be used (I don't believe this can be done
    > by simply iterating).


    #include <stdio.h>
    #include <stdlib.h>

    int main(void) {
    int i, n, m;
    int *a;
    char s[] = "12";

    n = sizeof s - 1;
    m = 3;

    a = malloc(m * sizeof *a);
    if (!a) abort();
    for (i = 0; i < m; ++i)
    a = 0;

    do {
    for (i = m - 1; i >= 0; --i)
    putchar(s[a]);
    putchar('\t');

    for (i = 0; i < m; ++i)
    if (++a < n) break; else a = 0;
    } while (i < m);

    putchar('\n');
    free(a);

    return 0;
    }

    Alex
     
    Alex Fraser, Oct 26, 2004
    #3
  4. darin dimitrov

    Flash Gordon Guest

    On 26 Oct 2004 05:51:45 -0700
    (darin dimitrov) wrote:

    > Hello,
    >
    > I need help with an algoritm that given a set of "n" distinct
    > numbers will
    > generate all the possible permutations of fixed length "m" of these
    > numbers WITH repetitions (a total of n^m possibilities). For example:
    >
    > given the set {1, 2} would output: 111,112,121,122,211,212,221,222 if
    > we fix m=3.
    >
    > What I could do so far is an iterative algorithm which could be used
    > only if we know before runnin the program "m" and "n" which is not
    > often the case :)


    You can run iterative algorithms where you only know the number of
    iterations at run time.

    > int n=2; //stores the numebr of elements in the set


    // comments are not recommended on Usenet since even if you use a
    language where they are supported (which means C99 on this group) they
    don't survive line wrapping. So you should stick to /* */ style
    comments for posting.

    > int m=3; //stores the length of the desired permutation
    > char s[] = "12"; //stores our set of numbers
    > char s1[] = new char[m]; //will store every permutation generated (of


    You seem to be talking a foreign language here. comp.lang.c++ is just
    down the hall on the right. We only talk C here.

    > length 3)


    See, the comment wrapped.

    > int i, j, k; // loop variables
    >
    > for (i=0; i<length(s); i++) { // first loop
    > for (j=0; j<length(s); j++) { // second loop
    > for (k=0; k<length(s); k++) { // third loop


    You could use a block of indexes and only one loop and increment the
    indicies them like you do digits in a number when counting. I.e. when
    one of them you keep going to you get to it's last valid value then next
    time reset it an increment the next 1.

    > // this code is executed 2^3=8 times
    > s1[0] = s;
    > s1[1] = s[j];
    > s1[2] = s[k];


    The above would then be a loop.

    > printf("%s\n", s1); // print the permutation
    > }
    > }
    > }


    <snip>

    > Could you help me with some pseudo code please? And please appologize
    > me if the term "permutation" that I used here is not correct.


    I've given you some hints. If you want to discuss algorithms further
    then please take it to somewhere like comp.programming and if you want
    to discuss problems with coding in C++ take it to comp.lang.c++. If, you
    decide to implement it using C instead (using malloc/free instead of
    new/delete, then once you have some code you can bring it here to
    discuss it. I also suggest reading the FAQ (google for comp.lang.c FAQ).
    --
    Flash Gordon
    Sometimes I think shooting would be far too good for some people.
    Although my email address says spam, it is real and I read it.
     
    Flash Gordon, Oct 26, 2004
    #4
  5. darin dimitrov

    Guest

    Thanks to all of you who responded to my request despite the fact that
    I posted some C/C++ mixture that wasn't very useful. The code I posted
    was just to show my point (I never wrote in an editor). In fact I was
    looking for the algorithm, more than its implementation and I should
    have posted my question in comp.programming. But your posts were
    excellent and helped me so much so I don't regret posting here. Flash,
    I have taken into consideration your remarks.
     
    , Oct 27, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Girish Sahani
    Replies:
    11
    Views:
    1,630
    Boris Borcic
    Jun 26, 2006
  2. Maric Michaud
    Replies:
    0
    Views:
    385
    Maric Michaud
    Jun 22, 2006
  3. Branka
    Replies:
    4
    Views:
    898
    benben
    Apr 4, 2006
  4. sanket
    Replies:
    3
    Views:
    514
  5. OL/2
    Replies:
    2
    Views:
    131
Loading...

Share This Page