0

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.

3
Contributors
13
Replies
15
Views
10 Years
Discussion Span
Last Post by merck120
0

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.

0

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'

0

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.

0

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


Or are you going to change your mind again.

0

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.

0

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

0

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.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.