How to generate all possible permutations with repetitions?

[darin dimitrov]

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

 

[Michael Mair]

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

 

[Alex Fraser]

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

 

[Flash Gordon]

On 26 Oct 2004 05:51:45 -0700

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

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

 

[darin_dimitrov]

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.