Velocity Reviews > How to generate all possible permutations with repetitions?

# How to generate all possible permutations with repetitions?

darin dimitrov
Guest
Posts: n/a

 10-26-2004
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[i];
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
Guest
Posts: n/a

 10-26-2004

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[i];
> 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.

Alex Fraser
Guest
Posts: n/a

 10-26-2004
"darin dimitrov" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> 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[i] = 0;

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

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

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

return 0;
}

Alex

Flash Gordon
Guest
Posts: n/a

 10-26-2004
On 26 Oct 2004 05:51:45 -0700
http://www.velocityreviews.com/forums/(E-Mail Removed) (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

> 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[i];
> 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
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.

darin_dimitrov@hotmail.com
Guest
Posts: n/a

 10-27-2004
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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Edward A. Falk C Programming 1 04-04-2013 08:07 PM sanket C++ 3 11-30-2011 04:55 AM Girish Sahani Python 11 06-26-2006 06:16 PM Maric Michaud Python 0 06-22-2006 10:24 AM OL/2 Perl Misc 2 05-26-2004 04:06 PM