Наиболее эффективный способ создания пар из пар ограничений из списка в Python - PullRequest
Новая
       35

Наиболее эффективный способ создания пар из пар ограничений из списка в Python

0 голосов
/ 01 октября 2019

Мне нужно перебирать пары (a, b) и (c, d) комбинаций длины 2 из списка l элементов со следующими ограничениями:

  1. без повторов в парах: если (a, b) уже появилось, то (b, a) не должно производиться
  2. нет повторений между парами, т. е. пары должны рассматриваться только один раз: если (a, b), (c, d) уже появилось, то (c, d), (a, b) не производится
  3. элементы в двух парах должны быть разными: a != c and a != d and b != c and b != d

Например, с

l = [0, 1, 2, 3, 4]

Пары должны быть: 

(0, 1), (2, 3)
(0, 1), (2, 4)
(0, 1), (3, 4)

(0, 2), (1, 3)
(0, 2), (1, 4)
(0, 2), (3, 4)

(0, 3), (1, 2)
(0, 3), (1, 4)
(0, 3), (2, 4)

(0, 4), (1, 2)
(0, 4), (1, 3)
(0, 4), (2, 3)

(1, 2), (3, 4)
(1, 3), (2, 4)
(1, 4), (2, 3)

Я использовал целые числа в примере, однако меня интересует более универсальное решение (хотя элементы являются списками, в моем конкретном случае).

Вот решение, которое я придумал: 

import itertools

used = set()

for (a, b) in itertools.combinations(l, 2):
    used.add((a, b))
    for (c, d) in itertools.combinations(l, 2):
        if a == c or a == d or b == c or b == d:
            continue
        if (c, d) in used:
            continue
        # do stuff...
        pass

Помимо громоздкого решения, для этого решения требуется дополнительный набор used. В реальной реализации я использовал enumerate(l) вместо l и поместил индексы элементов в кортежи в наборе, и попытался использовать индексы для фильтрации опций раньше ... но мне не удалось это сделатьлучше.

Как я могу сделать его более эффективным и, возможно, более элегантным / Pythonic?

1 Ответ

2 голосов
/ 01 октября 2019

Идея может состоять в том, чтобы сначала сгенерировать все комбинации кортежей, а затем отфильтровать их: 

l = [0, 1, 2, 3, 4]
aa = list(itertools.combinations(list(itertools.combinations(l, 2)), 2))
[(a,b) for a,b in aa if set(a).isdisjoint(b)]
...