pythonalgorithmpermutation

Efficiently Filter List of Permutations

I would like to efficiently generate a list of "valid" permutations from a given list.

By way of simple example, suppose I would like to generate the permutations of [1,2,3] where 3 is in one of the first two positions. My return result would then be [[3,1,2], [3,2,1], [1,3,2],[2,3,1]]

Currently, I can solve this problem by filtering each permutation in a loop. I don't need to generate all permutations as I can use a bijection from integers to a permutation, just to save on memory.

In any case, this method is not really feasible once my list starts to grow - there are simply too many permutations to loop through.

A more realistic example is that I would like to generate the permutations of [1,2,...20] with length 10 (20 permute 10), where my rules are something like [1,2] must appear in the first three places (in any order), [3,4] must finish in the first 5 places (in any order), and so on (for any reasonable user input).

There are 6.704425728 E+11 values to check in the loop here, so really just too much.

My initial thoughts are that there could be two ways to go about this:

  1. Generate only valid permutations by using the rules to generate sub-permutations, and then combine them.
  2. Somehow represent the permutations in a tree, and apply filtering down the tree. That way, if a node fails a rule, then all children of that node will also fail the rule. This would allow drastically cutting down the checking in a lot of cases (depending on the rules).

Has anyone had any experience doing something like this and could provide any guidance? Or is this simply a tricky problem that requires monumental compute?

Solution

  • You'll need a custom solution for that, covering all the types of constraints that you could have.

    In your examples I can see two types of constraints:

    In Python you could think of a class that manages the conditions, and continue as follows:

    class Condition:
    def __init__(self, values, start, end):
        self.originalset = set(values)
        self.currentset = set(values)
        self.start = start
        self.end = end
        self.stack = []
    
    def assign_value(self, index, value):
        if value not in self.currentset:
            # can still consume all conditioned values within the condition's range?
            return not self.currentset or len(self.currentset) < self.end - index
        if index < self.start or len(self.currentset) > self.end - index:
            return False  # occurs out of range or too many values remaining
        # ok
        self.currentset.remove(value)
        self.stack.append((index, value))
        return True

    def unassign(self, index):
        if self.stack and self.stack[-1][0] == index:
            self.currentset.add(self.stack.pop()[1])


def permutations(values, conditions, size):
    n = len(values)
    perm = []
    
    def recur():
        k = len(perm)
        if k == size:
            yield perm[:]
            return
        for i in range(k, n):
            take = values[i]
            if all(condition.assign_value(k, take) for condition in conditions):
                perm.append(take)
                values[i] = values[k]
                yield from recur()
                perm.pop()
                values[i] = take
            for condition in conditions:
                condition.unassign(k)
    
    if size <= n:
        return recur()

    For a reduced example I took these requirements:

    Generate the permutations of [1,2,...8] with length 6, where [1,2] must appear in the first three places (in any order), [3,4] must finish in the first 4 places (in any order).

    Here is how you would run that:

    # input:    
values = list(range(1, 8))
conditions = [Condition([1,2], 0, 3), 
              Condition([3,4], 0, 4)]
size = 6
# generate and print the corresponding permutations
for perm in permutations(values, conditions, size):
    print(perm)

    This outputs 72 permutations:

    [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 6, 7]
[1, 2, 3, 4, 7, 6]
[1, 2, 3, 4, 7, 5]
[1, 2, 4, 3, 5, 6]
[1, 2, 4, 3, 5, 7]
[1, 2, 4, 3, 6, 5]
[1, 2, 4, 3, 6, 7]
[1, 2, 4, 3, 7, 6]
[1, 2, 4, 3, 7, 5]
[1, 3, 2, 4, 5, 6]
[1, 3, 2, 4, 5, 7]
[1, 3, 2, 4, 6, 5]
[1, 3, 2, 4, 6, 7]
[1, 3, 2, 4, 7, 6]
[1, 3, 2, 4, 7, 5]
[1, 4, 2, 3, 5, 6]
[1, 4, 2, 3, 5, 7]
[1, 4, 2, 3, 6, 5]
[1, 4, 2, 3, 6, 7]
[1, 4, 2, 3, 7, 6]
[1, 4, 2, 3, 7, 5]
[2, 1, 3, 4, 5, 6]
[2, 1, 3, 4, 5, 7]
[2, 1, 3, 4, 6, 5]
[2, 1, 3, 4, 6, 7]
[2, 1, 3, 4, 7, 6]
[2, 1, 3, 4, 7, 5]
[2, 1, 4, 3, 5, 6]
[2, 1, 4, 3, 5, 7]
[2, 1, 4, 3, 6, 5]
[2, 1, 4, 3, 6, 7]
[2, 1, 4, 3, 7, 6]
[2, 1, 4, 3, 7, 5]
[2, 3, 1, 4, 5, 6]
[2, 3, 1, 4, 5, 7]
[2, 3, 1, 4, 6, 5]
[2, 3, 1, 4, 6, 7]
[2, 3, 1, 4, 7, 6]
[2, 3, 1, 4, 7, 5]
[2, 4, 1, 3, 5, 6]
[2, 4, 1, 3, 5, 7]
[2, 4, 1, 3, 6, 5]
[2, 4, 1, 3, 6, 7]
[2, 4, 1, 3, 7, 6]
[2, 4, 1, 3, 7, 5]
[3, 2, 1, 4, 5, 6]
[3, 2, 1, 4, 5, 7]
[3, 2, 1, 4, 6, 5]
[3, 2, 1, 4, 6, 7]
[3, 2, 1, 4, 7, 6]
[3, 2, 1, 4, 7, 5]
[3, 1, 2, 4, 5, 6]
[3, 1, 2, 4, 5, 7]
[3, 1, 2, 4, 6, 5]
[3, 1, 2, 4, 6, 7]
[3, 1, 2, 4, 7, 6]
[3, 1, 2, 4, 7, 5]
[4, 2, 1, 3, 5, 6]
[4, 2, 1, 3, 5, 7]
[4, 2, 1, 3, 6, 5]
[4, 2, 1, 3, 6, 7]
[4, 2, 1, 3, 7, 6]
[4, 2, 1, 3, 7, 5]
[4, 1, 2, 3, 5, 6]
[4, 1, 2, 3, 5, 7]
[4, 1, 2, 3, 6, 5]
[4, 1, 2, 3, 6, 7]
[4, 1, 2, 3, 7, 6]
[4, 1, 2, 3, 7, 5]