Solved

Recursion Question -

Posted on 2003-10-25
7
220 Views
Last Modified: 2010-04-15
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
Comment
Question by:guitardude101
  • 3
  • 3
7 Comments
 
LVL 1

Author Comment

by:guitardude101
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 45

Expert Comment

by:Kdo
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

by:guitardude101
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 45

Accepted Solution

by:
Kdo earned 100 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

by:guynumber5764
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

by:guitardude101
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 45

Expert Comment

by:Kdo
ID: 9670382

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

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now