permutations
Write the recursive function permutations(a, k), which modifies the recursive permutations function from the course notes so that it returns all the permutations of length k from the elements in the list a, or the empty list [] if no such permutations exist. For example, permutations([1,2,3,4], 2) would return some ordering of this list:
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
We say "some ordering" because your list must include the correct permutations, but in any order. And, once again, your solution must be recursive, and in fact it must be an obvious adaptation of the code in the course notes.
For your testing purposes, it might be helpful to use Pythons built-in permutations function. For example, this might be helpful (it generates the solution above):
import itertools
a = [1,2,3,4]
print [list(x) for x in itertools.permutations(a, 2)]
Hint: do not worry about the case where the original list contains duplicate values.
Note: regarding efficiency, your code should compute the 870-item result to permutations(range(30), 2) almost instantly, and the 117,600-item result to permutations(range(50),3) with at most a couple of seconds delay.
Most solutions that are not efficient enough will run much too long on these examples. The reason: generally, one way or another, they will create lots of "extra" permutations and then slice, pop, or remove their way down to the required size. For example, this modification of the permutation code is not acceptable:
def permutations(a, k):
# inefficient version that uses permutations code from class, unmodified,
# and then, assuming len(a)>=k, uses only first k elements of each permutation,
# ignoring the rest (which is not ok). This also produces some duplicates,
# so either have to remove all the duplicates at the end (which is also not ok),
# or add an expensive O(n) check inside our loop to check if a permutation
# is already in our list (which is also not ok).
result = [ ]
allPerms = allPermutations(a)
for fullLengthPerm in allPerms:
perm = fullLengthPerm[0:k] # not ok: essentially "removes" (n-k) elements
if perm not in result: # also not ok
result += [perm]
print "len(allPerms) = ", len(allPerms)
print "len(result) = ", len(result)
return result
def allPermutations(a):
# renamed permutations code from class notes
# returns a list of all permutations of the list a
if (len(a) == 0):
return [[]]
else:
allPerms = [ ]
for subPermutation in allPermutations(a[1:]):
for i in xrange(len(subPermutation)+1):
allPerms += [subPermutation[:i] + [a[0]] + subPermutation[i:]]
return allPerms
Why is this unacceptable? Well, say we are finding permutations(range(9), 2). The answer contains 72 permutations of two numbers each. However, the code above will generate all 362,880 permutations of length 9 to find these 72 permutations. This huge amount of extra work makes it intractable to use this code to compute permutations(range(30),2), let alone permutations(range(50),3). Try it, if you want to wait a very, very long time!
Big Hint: one way to solve this is to modify the permutations code from class to take a second parameter, k, and to return all the permutations of a that are no larger than length k. This still requires a non-recursive wrapper function (like above) that drops all the permutations that are not of length k, but since we never produce any permutations larger than length k, this is much, much faster than the code above.