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.
