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.