CODEWITHSUNDEEP
calgorithmloopsiterationpermutation
JustaRedShirt
JustaRedShirt

Reputation: 195

iterative solution to permutation calculation in C

I'm working on a problem dealing with iteration. I'm supposed to pass in two ints into a function, which represent a number of N objects and M values that I must find all permutations of. I am also given a sample of what the output is supposed to look like

void perm_iter(int N, int nr_values) and the output this is supposed to print is :

Called : perm_iter(3, 2);

0  0  0
0  0  1
0  1  0
0  1  1
1  0  0
1  0  1
1  1  0
1  1  1

I understand the concept of recursion by using a swap function to change the orders of strings to find all permutations of a string, but I'm unsure of how to use iteration to get the same, or similar result. Is this a case where I need to use the stack and push/pop iteratively to get my answer? I was thinking I could use something like a set of nested loops to take the place of recursion and get something like this output but I'm unsure how to set the loops up to go through every permutation and not just iterate, missing some of the possible permutations.

Any help would be appreciated, and thank you for your time.

Upvotes: 4

Views: 1266

Answers (1)

Stefan Haustein
Stefan Haustein

Reputation: 18793

You just need to count up each "digit" until the max is reached, then reset and increment the next.

Imagine nr_values is 10 (with n=2):

0 0
0 1 
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9 
1 0
1 1 
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

Looks familiar because it's just "regular" counting in this case.

Implement this just like you count up: In each step, increment the leftmost value. If max is reached, reset and increment the next value etc.

void perm_iter(int n, int nr_values) {
  int[] counter = new int[n];
  int i;

  // Clear all values
  for (i = 0; i < n; i++) {
    counter[i] = 0;
  }

  do {
    // Print the current set of values
    for (i = 0; i < n; i++) {
      printf("%n ", counter[i]);
    }
    printf("\n");

    // Keep incrementing while the values overflow,
    // starting at the rightmost counter
    i = n - 1;
    while (i >= 0) {
      counter[i]++;
      if (counter[i] < nr_values) {
        break;
      } 
      counter[i] = 0;
      i--;
    }
    // We are done when the first value overflows
  } while (i >= 0);
}

Upvotes: 2

Related Questions