Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Swapping elements iteratively, not recursively

element recursive

  • Please log in to reply
3 replies to this topic

#1 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 15 March 2012 - 01:13 AM

Let's say I have 3 groups of letters, AB, CD and EF. Each group has 2 letters. Now I want to generate all combinations of the groups and the letters within, and I'll use two for loops for this. The outer for loop runs through the groups and thus goes from 0 to 2 inclusive, and the inner loop runs through the letters in group, thus goes from 0 to 1 inclusive.

So the outer loop starts off being 0, and the inner loop is also 0, so I swap the first letter with the second in the first group, like this:

BA CD EF

The outer loop is now 1, and the inner loop becomes 0 again, so this happens:

BA DC EF

The outer loop is 2, and the inner loop again 0, so now it looks like this:

BA DC FE

The inner loop now becomes 1, so the letters in the third group are swapped again.

BA DC EF

The inner loop now exits, and it returns to the outer loop being 1. In this loop the inner loop increments to 1, so the letters in the second group are swapped.

BA CD EF

Now it enters the inner loop for group 3 again and swaps the two letters like this:

BA CD FE.

I hope this illustrates my point. That I need an inner loop for each number in the outer loop. Thus I would need 3 inner loops, one for each group. I could just make one outer loop and 3 inner loops, each of the inner ones going from 0 to 1 inclusive. But these numbers will change, so I need a solution that allows me to make the right amount of inner loops at run time.

One way I could resolve this, would be to use recursion, by using the number of the outerloop as a parameter for my function. But in this case recursion is not an option. So my question is if anyone has an idea of how this can be done iteratively?
  • 0

#2 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 15 March 2012 - 05:54 AM

Your description above on how an outer and inner loop iterates seems a little off. The inner loop would run from 0 to 1 for each successive iteration of the outer loop, so your transition from step 1 to step 2 seems like you skipped the 2nd iteration of the inner loop.

Also it would help if you provide the pseudocode for your algorithm instead of just describing what happens after each loop iteration.

Just for the sake of clarity, here's how a nested loop structure would iterate: (in pseudocode)
For i from 0 to 2:
    For j from 0 to 1:
        Print "outer loop: " + i + " inner loop: " + j
    Next j.
Next i.
The output of the above algorithm would be:
outer loop: 0 inner loop: 0
outer loop: 0 inner loop: 1
outer loop: 1 inner loop: 0
outer loop: 1 inner loop: 1
outer loop: 2 inner loop: 0
outer loop: 2 inner loop: 1
The inner loop iterates through its full range before the outer loop increments, then the inner loop "resets" and starts again.
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid


#3 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 19 March 2012 - 07:46 AM

No, I didn't skip a step. Perhaps this is best explained by showing how I would do it recursively.

main() {
  outer(0);
}

void outer(int i) {
  if (i == 3) {
    // Swap
  }
  else {
    for (int j = 0; j < 2; j++) {
      outer(i + 1);
    }
    // Swap
  }
}

But now I want to do this exact thing iteratively.
  • 0

#4 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 19 March 2012 - 08:38 AM

Edit: I was wrong in my previous post. Let me think about this for a minute.

What's the code for "// Swap"?
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid






Also tagged with one or more of these keywords: element, recursive

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download