Note: All the code given in this post will be Python, though it should be fairly easy to rewrite it in your language of choice.
Problem: Given x items, each of which can take on y different values, iterate over all permutations.
As an example, say our items are animals and that we have 3 (x) of them.
An animal in this situation can be a bird, a cat, or a dog (i.e. 3 different values – this is y).
If you work it out, the possibilities are (B = bird, C = cat, D = dog):
BBB
CBB
DBB
BCB
CCB
DCB
BDB
CDB
DDB
BBC
CBC
DBC
BCC
CCC
DCC
BDC
CDC
DDC
BBD
CBD
DBD
BCD
CCD
DCD
BDD
CDD
DDD
But how do we, in code, iterate all these permutations? Our code is going to need to be be quite generalized, so that if we suddenly change the number of animals we can have, or a new type of animal is discovered, updating the code will be a breeze.
Imagine, now, that we have an array of animal types:
animal_types = ["Bird", "Cat", "Dog"]
We could change our table of permutations to one where we use 0, 1 & 2 instead of B, C & D. These numbers then represent an index in animal_types:
000
100
200
010
110
210
020
120
220
001
101
201
011
111
211
021
121
221
002
102
202
012
112
212
022
122
222
Representing them as numbers may make it clearer how we’re going to go about finding all these permutations.
A first attempt may look like:
animal_types = ["Bird", "Cat", "Dog"]
num_types = len(animal_types)
for a in range(num_types):
for b in range(num_types):
for c in range(num_types):
print animal_types[a], animal_types[b], animal_types[c]
It works perfectly – the output is:
Bird Bird Bird
Bird Bird Cat
Bird Bird Dog
Bird Cat Bird
Bird Cat Cat
Bird Cat Dog
Bird Dog Bird
Bird Dog Cat
Bird Dog Dog
Cat Bird Bird
Cat Bird Cat
Cat Bird Dog
Cat Cat Bird
Cat Cat Cat
Cat Cat Dog
Cat Dog Bird
Cat Dog Cat
Cat Dog Dog
Dog Bird Bird
Dog Bird Cat
Dog Bird Dog
Dog Cat Bird
Dog Cat Cat
Dog Cat Dog
Dog Dog Bird
Dog Dog Cat
Dog Dog Dog
Which is all of the permutations.
If we suddenly decide to add a new type of animal – say, elephants, all we have to do is modify the animal_types array:
animal_types = ["Bird", "Cat", "Dog", "Elephant"]
If we run it again, it still works.
But this approach has a problem – what if we now have 10 animals (rather than 3)?
Using the same approach, we’d create the code:
animal_types = ["Bird", "Cat", "Dog", "Elephant"]
num_types = len(animal_types)
for a in range(num_types):
for b in range(num_types):
for c in range(num_types):
for d in range(num_types):
for e in range(num_types):
for f in range(num_types):
for g in range(num_types):
for h in range(num_types):
for i in range(num_types):
for j in range(num_types):
print animal_types[a], animal_types[b], animal_types[c], animal_types[d], animal_types[e], animal_types[f], animal_types[g], animal_types[h], animal_types[i], animal_types[j]
Which, frankly, is stupid.
So what else could we try that will scale nicely?
RECURSION!
Let’s try harnessing the power of recursion to write the code.
If you haven’t heard of it, recursion is basically a method calling itself. A classic example to demonstrate recursion is calculating the number at a given index in the Fibonacci sequence:
def fib(i):
if i <= 1:
return 1
return fib(i - 2) + fib(i - 1)
And if you don’t know the Fibonacci sequence, Wikipedia can help you.
Alright anyway, back to our fancy new recursive approach.
I can’t think of any more preamble, so here’s the code. Take it. ..Please.
animal_types = ["Bird", "Cat", "Dog", "Elephant"]
num_types = len(animal_types)
num_animals = 10
def iter(i, perm=[]):
if i == num_animals + 1:
return
if i == num_animals:
print perm
for x in range(num_types):
newPerm = perm[:]
newPerm.append(animal_types[x])
iter(i + 1, newPerm)
iter(0)
This is incredibly easy to extend. Adding/removing animal types is done the same way as before, but changing the number of animals is where this new approach really shines over the previous one. All you do is change num_animals. As well as being easy to change, it means that we can have loads of animals without having nest a ridiculous number of loops.
————-
Why does anyone give a damn how to iterate over stuff like this?
Well, the reason I made this post is because I just came across this problem when creating a semi-imaginary program. OK, that sounds stupid. Let me explain.
I was browsing Reddit, when I came across this comment:
I figured it was an interesting idea, so I decided to go about making a quick implementation in Python. It does the same thing as our shiny recursive method, but with a couple of small changes. Instead of the types of animal you can have, it deals with colors. And instead of the number of animals, it’s the number of pixels. Here it is:
# When you say 65536 colors, # I'm assuming you mean using # the 16-bit RGB 565 format # which gives 5 bits for red # and green, and 6 bits for # green. # # => Total colors = # 2**5 * 2**5 * 2**6 # = 2**16 # = 65536 # # If this isn't the case, # just modify the initialization # of the colors array.
colors = []
for r in range(2**5):
for g in range(2**6):
for b in range(2**5):
colors.append((r, g, b))
width, height = 640, 480
num_colors = len(colors) num_pixels = width * height
def iter(i, perm=[]):
if i == num_pixels + 1:
return
if i == num_pixels:
make_image(perm)
for x in range(num_colors):
newPerm = perm[:]
newPerm.append(colors[x])
iter(i + 1, newPerm)
# My image handling is using
# an imaginary framework.
# I've done this so that it's
# clear what's going on, and
# you can apply it to whatever
# graphics handling library
# you want to be using.
#
# The imaginary framework:
#
# img = new_bitmap()
# --creates a blank image
# img.set_pixel(x, y, col)
# --sets the color of the
# --pixel at a given position
# img.save()
# --saves the image
def make_image(perm):
img = new_bitmap()
for x in range(width):
for y in range(height):
i = y * width + x
col = perm[i]
img.set_pixel(x, y, col)
img.save()
iter(0)
Now, this does have a couple problems.
The first one is to do with recursion. The same thing that made this all possible also stabs us in the back. In a 640×480 image, there are 307200 pixels. The issue lies in how recursion works. Let’s take a detour for just a moment:
When we call a function, our current place in the program is “pushed” onto the call stack. The function is then invoked. When the function returns, we “pop” where we were off the stack, and resume whatever it was we were doing when the function call happened. This is effectively putting in a bookmark, going off to read a different section of a book, then (once you’re done with the new section) going back to where the bookmark is and continuing reading from there. The function we called may itself call a function, and so it does the same thing – note down what was happening, do the function, and then go back to what was happening. The problem lies in the fact that we only have a limited bookmarks – there is a maximum amount of times we can push our state onto the call stack and go off to do something else. This means recursive methods can only go down to a certain “depth”.
Aaaaaaaaand back from the unscheduled detour. Basically, the maximum recursion depth we can go to isn’t very big. You can check what yours is with:
print sys.getrecursionlimit()
On my machine, it prints 1000. That’s not going to be anywhere near enough – we need it to be over 300000!
Now, there is a workaround for when you hit the maximum recursion depth:
sys.setrecursionlimit(310000)
Really though, if you want to go down past 1000 you should probably be looking into a different language. Python is bad at deep recursion. Its stackframes can be large, meaning you’ll quickly run headfirst into a MemoryError. These occur if you go into deep recursion because Python (like a lot of humans) can only remember so much. Going back to the bookmark analogy from the detour, it’s as if we’ve put in so many bookmarks that when we go to put in a new one, we’ve simply got no more room in our head (memory) to keep track of what’s going on. At this point, Python throws a MemoryError at us, exclaiming “You’re asking me to do way too much!”. Given a computer with sufficient memory, this, of course, stops being a problem. But that aside, there are many languages that are simply better at recursion. Some of them can do a clever thing called tail-recursion, which means recursion depth stops being an issue completely. You can go as deep as you want.
The other issue isn’t to do with the actual implementation, it’s inherent in the task itself. Like Morinaka says in his comment, there is a huge number of possible permutations. This issue won’t cause you any errors about hitting the maximum recursion depth, or running out of memory. This just means that you’re going to need to wait a long time to go through all of them.
When I say a long time, I mean a long time. There are 65536^307200 permutations in total. It’s kind of hard to comprehend the size of this number. If it helps give some sense of scale, estimates give the age of the universe to be on the order of 10^17 seconds. Basically, it’s completely unfeasible for this to work in practice, unless an additional algorithm were to be put in place to cut down the permutations to “interesting” ones.
But that doesn’t mean we can’t dream about the results we’d get if it were feasible.
