Solved

Recursion Question -

Posted on 2003-10-25
7
227 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
[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
  • Learn & ask questions
  • 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:Kent Olsen
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 45

Accepted Solution

by:
Kent Olsen 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:Kent Olsen
ID: 9670382

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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
Suggested Courses

617 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