CODEWITHSUNDEEP
pythonperformancepermutation
user1928755
user1928755

Reputation: 11

How to get all permutations of sizes {n, n-1,n-2, ... 1} from list of size n efficiently?

I am trying to find all permutations from a list that are the same size or smaller than the list.

For example:

>>>allPermutations([a,b])
[[a,b], [b,a], [a], [b]]

This is the iterative code I currently have in python. I'm not sure how efficient it currently is.

import itertools

def getAllPossibleSubSchedules( seq ):
    fullSet = set()
    curSet = set()
    curSet.add(tuple(seq))
    for i in reversed(range(1, len(seq) + 1)):
        permutations = set()
        for curTuple in curSet:
            permutationsList = list(itertools.permutations(curTuple, i))
            for permutation in permutationsList:
                permutations.add(permutation)
        curSet = set()
        for permutation in permutations:
            curSet.add(permutation)
            fullSet.add(permutation)
    return fullSet

I'm pretty sure the algorithm will produce the summation of n! from 1 -> n permutations which grows pretty quickly. So far I have created a recursive way to do it that is incredibly slow because it does many repeated operations. I have been trying to do it through iteration but I can't figure out how to limit repeated operations. I am using python but psuedo-code would also help me a lot. Any help would be appreciated. Thanks in advance!

Upvotes: 1

Views: 513

Answers (3)

Floris
Floris

Reputation: 46435

I am pretty sure your permutations.add() and curSet.add() and fullSet.add() calls are going to cause your routine to crawl to a halt very quickly. If you keep changing the size of an array, the memory allocated will "run out of space" and a new location has to be found. This means that the entire array gets copied. And then you add another element - rinse and repeat.

You need to compute the number of elements you need, and pre-allocate the space for that. Thus, if you have 5 elements, you need to allocate ( 5! + 5*4! + 10*3! + 10*2! + 5 ) x 5 elements for the final result - and less for the intermediate results. Then you fill these array without shuffling blocks of memory around; it will make things significantly faster.

Upvotes: -1

Andrew Clark
Andrew Clark

Reputation: 208675

The following should work:

from itertools import permutations

def allPermutations(seq):
    return (x for i in range(len(seq),0,-1) for x in permutations(seq, i))

For example:

>>> list(allPermutations('abc'))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('a',), ('b',), ('c',)]

Upvotes: 4

Jakub M.
Jakub M.

Reputation: 33867

Maybe iterate over all permutations for lists with all possible sizes. To clarify:

def all_permutations(input_list):
    for i in xrange(len(input_list)):
        sublist = input_list[:i]
        for variant in permutations(sublist):
            yield variant

Upvotes: 0

Related Questions