1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
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
1 rating.
Login to rate!
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).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
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 8, 2008, October 08, 2008 16:55, permalink
No rating.
Login to rate!
My second proposal is based in an idea of 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
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 forth: ... 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 yield result[:] if __name__ == "__main__": l = [2, 3] print list(cart(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?