• C

# Recursion Question -

I need a C function that takes an N size array and iterates through every possible combination. N will be less than 50. Array data type does not matter ints are ok.
I would prefer a recursive function to do this.

for example
Pass in array N 4 elements
the output would be:

0 1 2 3   1 0 2 3   2 0 1 3   3 0 1 2
0 1 3 2   1 0 3 2   2 0 3 1   3 0 2 1
0 2 1 3   1 3 0 2   2 3 1 0   3 2 1 0
0 2 3 1   1 3 2 0   2 3 0 1   3 2 0 1
0 3 1 2   1 2 3 0   2 1 3 0   3 1 2 0
0 3 2 1   1 2 0 3   2 1 0 3   3 1 0 2
LVL 1
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
I have the entire rest of the program written.
The function is going to passed an array of ints and number of elements

Then function then needs to go through every possible ordering of the array.
During each iteration the array is going to be passed to another funtion .

Is it not clear or is this harder than I think.

psuedo code

void iteratearray(int* array, int numelements)
{
do
{
callexternalfunction(array, numelements);
reorderarray();
} while every posible combination not called
}

DBACommented:

Hi guitardude101,

From your example, I believe that you're looking for permutations, not combinations.  (Statasticians will tell you that there is a huge difference -- and they're right.)

This sounds like homework, so I'll gladly tell you how to do this and let you produce the code.  :)

It's a simple case of swapping elements.  Given the initial value of :

A B C D

swap elements 2 and 3 (relative 0), giving:

A B D C

Now from the original list, swap elements 1 and 2, giving:

A C B D

then from the new list, swap elements 2 and 3, giving:

A C D B

Back to the original list, swap elements 1 and 3, giving:

A D C B

the from the new list, swap elements 2 and 3, giving:

A D B C

You've now generated the 6 permutations that are possible from 3 elements.  (Keeping "A" in the first position reduces the problem to a manageable example.)  To complete the list of permuations from "A B C D", iterate the other 3 letters into the first position.

Good Luck,
Kent
Author Commented:
Thanks Kent,  it has started me in a diffenrt direction for it but it is still not right, or I implimented it incorectly
It turns out the first call to this function gets a 25 element array. This would be so much easier if the array size would not change.

Could you please explain it with psuedo code or real code so I can see how you set your loops up?
DBACommented:

Hi guitardude101,

Let's assume that we want to generate our permutations by changing the rightmost characters first.  Then the first thing that needs to be done is to recursively move to the end of the string.  Then, as the recursion pops back up the stack, perform the swaps and repeat the recursion.  Two functions, one for the "general purpose" API call, and another for the recursion will do nicely.  That way we can start the whole thing with:

PermuteString ("ABCD");

This is a simple function that just initiates the recursion:

void PermuteString (char *string)
{
PermuteSubstring (string, 0);
}

All of the work is done in the recursive funciton.  But it too, is pretty short.

void PermuteSubstring (char *string, int position)
{
int idx;

if (string[position+1] == 0)  /*  We're at the end of the string so print what we have  */
{
fprintf (string);
return;
}
PermuteSubstring (string, position+1);  /*  Advance to the next position in the string  */

/*  At this point in the function, we want to swap the character at string[position] with a character further down the string.  */

for (idx = position+1; string[idx]; idx++)
{
/*  Swap string[position] with string[idx];  */
PermuteSubString (string, position+1);
/*  To maintain the integrity (order) of our permutations, swap string[position] and string[idx] back to their original location  */
}
}

Something very close to that should do nicely,

Good Luck!
Kent

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
Alternately...

Lets suppose that we're permuting a 5 character string ("ABCDE")

What if we say that all of the permutations can be obtained by taking
each letter as the first letter and tacking on all permutations of the remaining letters....

Permutations(5, "ABCDE")
{
"A" & Permutations(4, "BCDE")
"B" & Permutations(4, "ACDE")
etc.
}
When you reach Permutations(1,...) you have a complete permutation and can output it.  Of course, due to the recursion you either need to pass your partially built permutation down the tree (as Kent does) or just dump it somewhere until you need it.

so more generally

Permutations(N,  string)
{
if (N=1)
SetPrintPosition(1,string[1])
PrintPermutation()
else
for i=1 to N
SetPrintPosition(N,i)
newstring = MakeSubstring(i, string)    // removes ith character from string
Permutations((N-1), newstring)
endfor
endif
}

The only tricks left are a trivial print buffer (SetPritPosition and PrintPermutation) and that MakeSubstring() function.
Author Commented:
Thanks...
This is NOT homework in fact I am 40 years young. I asked this because of the lack of time that I have.
DBACommented:

A fourty year young guitardude, huh?  Cool....  :)
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.