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

Ajax1234 · Accepted Answer · 2021-05-24 14:54:15Z

2

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

answered May 24, 2021 at 14:54

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Morgs Over a year ago

Thanks very much for your help, this worked great, and was more efficient that the permutations method.

Guy · Accepted Answer · 2021-05-24 14:37:58Z

2

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))]

answered May 24, 2021 at 14:37

Guy

51.2k10 gold badges49 silver badges96 bronze badges

1 Comment

Morgs Over a year ago

Thanks for your help, this worked well and achieved the desired outcome :)

Collectives™ on Stack Overflow

Python - Creating permutations with output array index constraints

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related