Arbitrarily Nested Loops

[Limbic~Region]

All,
While this meditation is about arbitrarily nested loops, it has come as a result of a specific problem I was trying to solve. Please try to focus on the meditation and not the specific problem.

Introduction

Many of you know my affinity for challenging problems and puzzles. For me, they are fun ways to expand my knowledge. There is a currently unsolved math problem of an order 10 Perfect Magic Cube. To prove that an order 10 magic cube is not possible by brute force, 1000! permutations of arranging the numbers 1 - 1000 must be tried. I was hoping to find and prove the existence of a cube so I knew that I was going to have to find ways to significantly reduce my search space and hope I got lucky. I succeeded in finding ways to reduce the search space but failed in getting lucky. This meditation is about the methodology I used and not about the problem I was trying to solve. If anyone is interested in a list of techniques I used, /msg me and I will be glad to go over them. What was important to me was the knowledge not the answer.

Explanation of arbitrarily nested loops

If you were trying to figure out how many different outfits you could make with your current wardrobe, you may create the following code:

for my $feet ( qw/black brown sneaker/ ) {
    for my $legs ( qw/shorts dress_pants jeans/ ) {
        for my $torso ( qw/t-shirt dress_shirt sweater/ ) {
            print "$torso $legs $feet\n";
        }
    }
}

Now imagine that you wanted to do the same thing but you were doing it for your upcoming birthday gifts. Since you won't know until the gifts arrive (runtime) what you are going to receive, you can't pre-construct the loops. You know you may need to extend the number of loops to include things like gloves to cover your hands and hats to cover your head and sunglasses for your eyes.

Abritrary nested loops is not knowing in advance the number of loops or the number of items in each loop. It may seem like a difficult problem to solve, but in fact it is quite easy.

How to handle arbitrarily nested loops

Dominus uses the concept of an odometer with dials of different ranges in HOP to give a visual representation of the process. When I first figured out how to it, I thought of a combination lock on a briefcase with different size dials. The idea is the same.

Assume that you have received a list of lists that need to be looped through. Each list represents a dial that must be turned. When you the dial you are turning reaches its maximum value, the dial to its left increments by one and the current one rolls over to the start. When the leftmost dial reaches exceeds its maximum number - you know you are finished.

(black, brown, sneakers), (shorts, dress_pants, jeans), (t-shirt, dres
+s_shirt, sweater)

# Start position
0, 0, 0 = black, shorts, t-shirt
0, 0, 1 = black, shorts, dress_shirt
0, 0, 2 = black, shorts, sweater
0, 1, 0 = black, shorts, t-shirt
0, 1, 1 = black, shorts, dress_shirt
0, 1, 2 = black, shorts, sweater
0, 2, 0 = black, dress_pants, t-shirt
...
2, 2, 2 = sneakers, jeans, sweater

To make this an iterator you need to use closures which I won't cover. Instead of rolling your own you should probably use tye's Algorithm::Loops 'NestedLoops'. There is still value in removing the veil of mystery to understand how it works even if you are not going to implement it yourself.

How to dynamically construct the loops

What if the problem you are trying to solve requires the construction of a loops values to be based off 1 or more of the preceeding values selected? For instance, when you are selecting wardrobes - perhaps you don't want to mix business wear with beach wear. This can be handled with a code ref. In Algorithm::Loops, $_ is the currently selected value immediately to the left of the current dial and @_ is all of the selected values with 0 being the outer most dial.

Now it is a simple matter of checking when a dial rolls over to the beginning if the dial was a fixed list or generated from a code ref. If it was from a code ref, replace the current list with the return value of the the executed code ref.

What else might I want?

This meditation is not intended to be an explanation of Algorithm::Loops. In fact, I rarely grok tye's code and this is no exception. If my explanation fits the Algorithm::Loops code it is not a result of me studying the code. He however does have some great ideas which I shamelessly steal.

You might want the ability to filter out some of the results. We may allow the user to pass in a code ref that we will execute at the end of each dial turn. If the code ref returns a true value we return the list and if not, we spin the dial again - wash, rinse, repeat.

You may also want to execute some arbitrary piece of code after each loop. Again, this is as simple as designing your API such that the user can pass in a code ref that you execute at the end of each dial turn.

Conclusion

Handling arbitrarily nested loops that are dynamically constructed in Perl is fairly simple. This does not mean you should go rolling your own without due cause as Algorithm::Loops is a wonderful module. I needed to for my task because Perl was just too slow. I ended up using C. While I was able to produce some extremely fast code (25-30 million iterations per second), I was unable to make a generic reusable library. Perl rawks!

I didn't want this to be a tutorial showing step by step code for 2 reasons. The first is because there is an existing ready made solution. The second is because one of the best ways to learn is by doing. Try it out, make sure you can do it on your own. You will likely learn something. If you have problems or questions - feel free to reply.

If anyone has the inclination to make this work in C as a reusable library I will be very much interested. See also NestedLoops and the Odometer Model.

[ikegami]

Here's a complete (but untested) solution:

Read more... nested_loops.h (2 kB)
Read more... nested_loops.c (4 kB)
Read more... example.c (3 kB)
Read more... example2.c (2 kB)
Read more... example3.c (4 kB)

The core logic is a direct translation of tye's Algorithm::Loops's NestedLoops.

ug! It would have been much easier in C++!

• Mini objects would replace pads.
• Destructors would handle memory management.
• (*type). would be replaced with type->.
• Most occurances of the word struct could be omitted.
• Wrapper classes would handle type issues.
• Variable declerations wouldn't need to be seperated from their initialisation code.

Optimizing trick: In the last example, you know the maximum size of data, so you could allocate data outside of NestedLoops (and modify range and range_inc accordingly).

Update: Added Perl equivalent to examples.

Update: min's initialization was wrong in both range and range_inc.

[ikegami]

Update: Forget this node. Go see Re: Arbitrarily Nested Loops.

(Moving here what I had on my pad for you.)

---

I wrote this to get the problem clearly in my head. It doesn't really solve anything, since your problem is "...work with element_ptr...". There's also the issue of whether individual elements should be freed. Perl solved both of these problems by using SVs. Your requirement that your lists can contains more than one kind of data complicates things greatly. It would be much simpler if you could deal with a single type at a time (even if the type was different in different calls to NestedLoops). See "Take 2", below, where I came up with something along the lines of a simple SV.

Read more... (3 kB)

---

Take 2.

Much better. ElementType probably should not contain handler, and handler needs more arguments, but you get the idea.

Read more... (6 kB)

[thor]

When the leftmost dial reaches its maximum number

Maybe you meant to say when all the dials reach their respective maxima? Consider two dials, each ranging from 0 to 2. By your original statement, you'd get the following:

0,0
0,1
0,2
2,0

In this, you've missed two combinations ( (2,1) and (2,2) ). I'm sure it was just a type or a mind-o, though. :)

[Limbic~Region]

thor,
No, but there is a typo. The word reaches should have read exceeds. Thanks, I will update the original.

[radiantmatrix]

I ran into a similar challenge a bit ago - the generation of rainbow tables. Yes, there are a number of programs out there that do this, but I was attempting to apply the concept to create a generic module that could use any of the Digest modules. In any case, I didn't know about Algorithm::Loops then, so I reinvented the subset I needed. Whoops. ;-)

The nifty thing about the implementation, though, is that it's restartable -- or, rather, one can start at any state in the series (pre-set the odometer, if you will) and then get results for that and all following states. This is useful if, for example, you need all combinations of a given set of chars that are between 3 and 10 chars long.

Anyhow, I'm posting here because I think my code, being so special-purpose, might be easier to follow than the wonders of Algorithm::Loops (how tye manages to repeatedly pull off such deep magic, I will never know. Go tye!). It's also not complete, production code, so feel free to rip it to shreds (though I'd prefer patches).

Read more... RainbowTable.pm (7 kB)

[dokkeldepper]

A link to more magic.