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, 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? Continue reading...
