CODEWITHSUNDEEP
pythonpython-itertools
GalacticPonderer
GalacticPonderer

Reputation: 547

Limiting permutations using itertools

I am writing a tool that is looking to generate all possible pairs of pairs from a list 13 chars long. Each pair must have their second element swapped. i.e. from the list ABCDEFGHIJKLM I want to generate pairs such as AB CD, AB CE, or CD GK.

I am using itertools.permutations to do this and it works:

perm_pairs = itertools.permutations(my_list, 4)

I am planning on iterating over perm_pairs and use the pairs in a seperate program. However, as order is unimportant and the subsequent process has high time complexity, I want to increase efficiency by preventing pair inversions. i.e. if I have already had AB CD I do not want to generate CD AB.

itertools.combinations() does not produce all the required pairs, but itertools.permeations() generates 4x more pairs than are required to iterate over.

Is there a "middle way" where I can avoid generating inversions?

Upvotes: 0

Views: 70

Answers (1)

Djaouad
Djaouad

Reputation: 22776

You could use a itertools.permutations for each pair of letters, and then, check if the inverse of pair of pairs doesn't already exist in some set (perm_pairs):

from itertools import permutations

my_list = "ABCDEFGHIJKLM"

perm_pairs = set()

for pair_1 in permutations(my_list, 2):
  for pair_2 in permutations((c for c in my_list if c not in pair_1), 2):
    if pair_2 + pair_1 not in perm_pairs:
      perm_pairs.add(pair_1 + pair_2)

Upvotes: 1

Related Questions