Solved

Recursion Question -

Posted on 2003-10-25
7
224 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: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
ScreenConnect 6.0 Free Trial

At ScreenConnect, partner feedback doesn't fall on deaf ears. We collected partner suggestions off of their virtual wish list and transformed them into one game-changing release: ScreenConnect 6.0. Explore all of the extras and enhancements for yourself!

 
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

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops 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.

789 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