Question: 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:  Generate only valid permutations by using the rules to generate sub-permutations, and then combine them. 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?

Answer: 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:  A constraint whereby all values in a given set must occur in a certain range (start, end) The size of the produced partial permutations  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]