Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Recursion Question -

Posted on 2003-10-25
Medium Priority
229 Views
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
0
Question by:guitardude101
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 3

LVL 1

Author Comment

ID: 9633059
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
}

0

LVL 46

Expert Comment

ID: 9634224

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
0

LVL 1

Author Comment

ID: 9640961
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?
0

LVL 46

Accepted Solution

Kent Olsen earned 400 total points
ID: 9641951

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

0

LVL 3

Expert Comment

ID: 9647080
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.
0

LVL 1

Author Comment

ID: 9665552
Thanks...
This is NOT homework in fact I am 40 years young. I asked this because of the lack of time that I have.
0

LVL 46

Expert Comment

ID: 9670382

A fourty year young guitardude, huh?  Cool....  :)
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Â This address might be address of another variable/address of devices/address of fuâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month6 days, 2 hours left to enroll