Permutations of an N element array

[merck120]

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.

[iamthwee]

this would be in the daniweb code snippet section.

[merck120]

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.

[iamthwee]

http://www.daniweb.com/code/c.html

[~s.o.s~]

A non recursive way, if it suits your need:

http://www.daniweb.com/code/snippet533.html

[merck120]

A non recursive way, if it suits your need:

http://www.daniweb.com/code/snippet533.html

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

[iamthwee]

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'

[merck120]

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.

[iamthwee]

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

Or are you going to change your mind again.

[merck120]

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.

[~s.o.s~]

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

Hehe, looks like we are not the only ones asking him this question.
There are others out there....

[iamthwee]

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

Er I don't think it is. A combination generator would look something like this:

http://home.att.net/~srschmitt/script_combinations.html

I don't think you even know what you mean.
Ha ha. So I'm out. Sorrie.

[iamthwee]

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

[merck120]

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.