I am currently working on a program in C, that needs to calculate the permutations
of a n integer array. The approach that I have taken is using recursion, using a n-element array of counters incrementing the correct value each recursion,
so the subroutine calls itself x (x being the max # of permutations) number of times returning the next permutation.

For example: Information known ahead of time: n = 3(could be any value); n_array[0] = 3 (could be any value from 1 to 9), n_array[1] = 3, n_array[2] = 3:
so first permutation (does not have to be in this order):
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 1
1 1 1 etc.
That being said, I attempted to write a loop within the recursive function that looks like this,

for(i = 0; i <n; i++) {
     if(i == n-1) {
            count[i]++;
      }
      if(count[i] == n_array[i]) {
            count[i] = 0;
            count[i-1]++;
       }
}

which gives the following:
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
0 3 0 -> incorrect
1 0 1
1 0 2 etc.
I realize what my loop is doing, but I can't think of a way to fix
it, any fresh ideas would be appriciated. Thanks in advance.

this would be in the daniweb code snippet section.

Under what listing, I went through all snippets, and I did not see what I was looking for.

Not what I am looking for, look at my first post.

So, your example don't even make sense

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1 <- Why the repeat
1 0 1 <-Why the repeat
1 1 1

In fact your example doesn't even exhibit behaviour you would expect when using the word 'permutation'

So, your example don't even make sense

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1 <- Why the repeat
1 0 1 <-Why the repeat
1 1 1

In fact your example doesn't even exhibit behaviour you would expect when using the word 'permutation'

I sorry, that line is a typo, and it should not be repeated, and yeah I know permutation is not the best word, for what I am doing, combinations, would probably be better.

it should be:
100
101
102
110
etc.

Ok, so do you mean the mathematical definition of the word combination.


Or are you going to change your mind again.

Ok, so do you mean the mathematical definition of the word combination.


Or are you going to change your mind again.

Yes, all of the mathematical combinations, per my fixed example.

Yes so your example neither generates permuations or combinations. HAve you realised this yet?

#include <iostream>

using namespace std;

int main()
{
    char crap[100] = "012";
    
    for ( int a = 0; a < 3; a++ )
    {
        for ( int b = 0; b < 3; b++ )
        {
            for ( int c = 0; c < 3; c++ )
            {
                cout << crap[a] <<" "<<crap[b]<<" "<<crap[c];
                cout <<"\n";
            }
        }
    }
    cin.get();
}

output:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

Essentially what you are looking for is something that simulates an arbitary number of nested loops using tail recursion.

http://people.cs.uchicago.edu/~jhr/papers/2002/hosc-lcps.pdf

Ok problem solved, and I feel like an idiot because the solution was stairing me in the face all along, talk about overthinking things :) , sorry for the confusion. Anyways thanks for the help.

This article has been dead for over six months. Start a new discussion instead.