Limiting permutations using itertools

Question

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?

Do you need `AB CD` as well as `BA CD` or why does combinations not work? — user2390182, Oct 28 '20 at 12:37
Does this answer your question? [How to generate permutations of a list without "reverse duplicates" in Python using generators](https://stackoverflow.com/questions/960557/how-to-generate-permutations-of-a-list-without-reverse-duplicates-in-python-us) — Christopher Peisert, Oct 28 '20 at 12:38
Can you give an example of an output that `combinations` doesn't produce? — kaya3, Oct 28 '20 at 12:40

score 1 · Accepted Answer · answered Oct 28 '20 at 13:16

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)

Limiting permutations using itertools

1 Answers1