Python - Creating permutations with output array index constraints

Question

I want to create all possible permutations for an array in which each element can only occur once, with constraints on the element array index position.

ID = ["A","B","C","D","E","F","G","H","I","J"]

I want to create all possible permutations of the original_array, however the positions of each element are restricted to index positions given by:

ID = ["A","B","C","D","E","F","G","H","I","J"]

Index_Options=[]
for i in range(len(ID)):
    List1=[]
    distance=3
    value = i - distance
    for j in range((int(distance)*2)):
        if value < 0 or value > len(ID):
            print("Disregard") #Outside acceptable distance range
        else:
            List1.append(value)
        value=value+1
    Index_Options.append(List1)
    print(Index_Options)

#Index_Options gives the possible index positions for each element. ie "A" can occur in only index positions 0,1,2, "B" can occur in only index positions 0,1,2,3 ect.

I'm just struggling on how to then use this information to create all the output permutations.

Any help would be appreciated

Answer 1

You can use a recursive generator function to build the combinations. Instead of generating all possible permutations from ID and then filtering based on Index_Options, it is much more efficient to produce a cartesian product of ID by directly traversing Index_Options:

ID = ["A","B","C","D","E","F","G","H","I","J"]
def combos(d, c = [], s = []):
  if not d:
     yield c
  else:
     for i in filter(lambda x:x not in s and x < len(ID), d[0]):
        yield from combos(d[1:], c=c+[ID[i]], s=s+[i])

print(list(combos(Index_Options)))

Output (first ten combinations produced):

[['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'I'], ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'I', 'H', 'J'], ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'I', 'J', 'H'], ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'J', 'H', 'I'], ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'J', 'I', 'H'], ['A', 'B', 'C', 'D', 'E', 'F', 'H', 'G', 'I', 'J'], ['A', 'B', 'C', 'D', 'E', 'F', 'H', 'G', 'J', 'I'], ['A', 'B', 'C', 'D', 'E', 'F', 'H', 'I', 'G', 'J'], ['A', 'B', 'C', 'D', 'E', 'F', 'H', 'I', 'J', 'G']]