Python - Creating permutations with output array index constraints

user_13340288 0
Viewed 77

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

permutation itertools iteration python
2 Answers

You can use itertools.permutations to create all the possible permutations and then create new list with a check if all the letters are in the correct position

permutations = [p for p in itertools.permutations(ID, len(ID)) if all(i in Index_Options[ID.index(x)] for i, x in enumerate(p))]
user_51680110

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']]
user_73267380
Related