def perm(ni):
result = []
# Base case: The list length is zero. The only possible permutation is as well
# an empty array.
if len(ni) == 0:
result.append([])
return result
# Get all possible permutations for the tail of the list.
subresult = perm(ni[1:])
# Get each possible value for the head and concat with each permutation
# previously computed.
for i in range(ni[0]):
for array in subresult:
result.append([i] + array)
return result
if __name__ == "__main__":
l = [2, 3, 4]
print perm(l)
Refactorings
No refactoring yet !
Maciej Piechotka
October 7, 2008, October 07, 2008 14:34, permalink
You looking for cartesian product. Here is a simle solution using generators.
Be aware that the generator is returned not a list (to save memory).
def cart(*lists):
if not lists:
for x in L:
yield [x]
else:
for x in L:
for y in cart(lists[0], *lists[1:]):
yield [x] + y
def perm(arg):
if len(arg) == 0:
return [[]]
a = []
for i in arg:
a.append(xrange(i))
return cart(*a)
Auron
October 7, 2008, October 07, 2008 14:44, permalink
Excellent! I have to recognize that using both recursion and the yield statement is a bit tricky to me, and I'm having a bad time trying to fully understand your code. I've changed the variable names in order to clarify it a bit, but is not trivial at all :)
def cart(posValuesHead, *posValuesTail):
if not posValuesTail:
for posValue in posValuesHead:
yield [posValue]
else:
for posValue in posValuesHead:
for subresult in cart(posValuesTail[0], *posValuesTail[1:]):
yield [posValue] + subresult
def perm(maxList):
posValues = [] # posValues stands for possible values.
for max in maxList:
posValues.append(xrange(max))
return cart(*posValues)
if __name__ == "__main__":
l = [2, 3]
print list(perm(l))
Auron
October 8, 2008, October 08, 2008 16:55, permalink
My second proposal is based in an idea from a peer at work, so credits for him, please. I've just adapted it to Python. I think it uses a very intelligent point of view, and resolves the problem elegantly and without recursion, which is great.
def cart(maxs):
"""
Compute each new result as it if was a number where digit i is of
base maxs[i]. As it happens with natural numbers, we add one to the
least significant digit in order to obtain the next number. If the
digit is above a limit, it turns out zero, and we instead add one to
the next significant digit, and so on and so for:
... 1 8 ---> 1 9 ---> 2 0 (In base 10, we reset 9 to 0
(+1) (+1) and add one to the next digit)
The results of this fuction are very similar, but each digit is of
a different base.
"""
# The first result will be a list of zeroes, that's for sure.
result = [0 for i in xrange(len(maxs))]
yield result[:] # You can't yield the result as it is, because the
# result reference will be used along the function.
# Hence, we return a copy.
# Get the number of different results we will obtain.
numResults = reduce(lambda x,y: x * y, maxs)
# Now, get each result.
for n in xrange(1, numResults):
for i in xrange(len(maxs) - 1, -1, -1):
if i == len(maxs) - 1:
result[i] = result[i] + 1
elif result[i + 1] >= maxs[i + 1]:
result[i + 1] = 0
result[i] = result[i] + 1
else:
break
yield result[:]
if __name__ == "__main__":
l = [3, 4]
print list(cart(l))
Leif Ryge
October 22, 2008, October 22, 2008 04:55, permalink
[edit: redacted, sorry]
Hugh Brown
March 5, 2010, March 05, 2010 22:38, permalink
Simple code using generators. Useful pattern to memorize for use in other python programs.
def permiter(ni):
if not ni:
yield []
else:
left, right = ni[0], ni[1:]
for i in range(left):
for array in permiter(right):
yield [i] + array
if __name__ == "__main__":
l = [2, 3, 4]
print [p for p in permiter(l)]
Boys and girls, it's time to PYTHON!!! The following piece of code computes, given a list of numbers where each value represent the upper limit an element of a list of the same size can reach, all lists that is possible to build.
Sorry, my English is a bit crappy, but the problem is not as difficult to understand as it may seem. Let's say I have the following list of size 2:
[2, 3]
I want all the possible lists of size 2 (the same length of the original list) where the first element can be 0 or 1 and the second and last element can be 0, 1 or 2. The result should be:
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]]
That's what the following function does. It is actually based on recursion, but I think it can be do better. What do you think?