On 0, Glen Wheeler <wheelege@tsn.cc> wrote:
> Hey all,
>
> While fiddling around with maths, I thought it would be nice and cool to get all the possible permutations of a set, taken n at a time. I have been trying to get this to work nicely, but I'm just not familiar enough with recursion to get it to behave.
> For example, if I wanted to get all the permutations of a set ['a','b'] taken three at a time, I would write this :
>
> >>> c = []
> >>> s = ['a', 'b']
> >>> for i1 in range(len(s)):
> ... for i2 in range(len(s)):
> ... for i3 in range(len(s)):
> ... c.append([s[i1], s[i2], s[i3]])
> ...
> >>> for item in c: print item
> ...
> ['a', 'a', 'a']
> ['a', 'a', 'b']
> ['a', 'b', 'a']
> ['a', 'b', 'b']
> ['b', 'a', 'a']
> ['b', 'a', 'b']
> ['b', 'b', 'a']
> ['b', 'b', 'b']
>
> Which is all well and good, but when I want to take them n at a time I
> need more for loops. Thus I thought 'Hmmm, I could get a function which
> calls itself n times...that would work!' - but I'm just too green with this
> sort of programming for it to happen for me.
The way to think about recursion is solving the problem by solving a smaller
version of the problem first, until you get a smaller problem that's easy to
solve. In this case, the reasoning goes something like this:
You can get all the permutations of a list by taking each element in turn,
and then add to that element all the permutations of the *rest* of the list.
That rest is smaller than the list itself. And the problem is trivial for a
list of length 1 or 0. So we can use recursion.
We get something like this:
def permutations(L):
result = []
if len(L) <= 1:
# The single result is the list itself
result.append(L[:])
else:
for i in range(len(L)):
# We pick element i, and combine it with the permutations of the rest
rest = L[:i] + L[i+1:]
for permutation in permutations(rest):
result.append([L[i]]+permutation)
return result
--
Remco Gerlich