Группы парных комбинаций, где каждый член появляется только один раз - PullRequest
Новая
       10

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

1 голос
/ 28 мая 2019

У меня есть список уникальных кортежей, каждый из которых содержит 2 элемента от 1 до 10. Общее количество элементов в списке составляет 45. Я хотел бы разделить их на 10 групп, каждая из которых содержит только цифры от 1 до 10.

Я попытался решить мою проблему, используя этот ответ: python получает группы комбинаций, каждый член которых появляется только один раз

питон: 

from itertools import combinations, chain
l = ['A','B','C','D','E', 'F', 'G','H','I','J']
c = list(combinations(l,2))
[set(i) for i in list(combinations(c,5)) if (len(set(l) & set(chain(*i))) == len(l))]

Но я получаю повторения, вот так: 

[{('A', 'B'), ('C', 'D'), ('E', 'F'), ('G', 'H'), ('I', 'J')},
 {('A', 'B'), ('C', 'D'), ('E', 'F'), ('G', 'I'), ('H', 'J')},...]

1 Ответ

0 голосов
/ 28 мая 2019

не 10 пар, но есть 945 таких пар, которые удовлетворяют вашим условиям

То, что я сделал, получить всю перестановку чисел, создать словарь, который сохраняет все комбинации в качестве ключа.

теперь для каждого элемента перестановки я взял их в паре 2 ie [1,2,3,4] is [(1,2),(2,3),(3,4)]

это создаст список

Теперь для всех таких списков и их элементов я сравнил их по словарю независимо от того, присутствуют они в словаре или нет.

пс. это долгое и трудоемкое решение, с помощью теории графов мы можем значительно уменьшить размер. 

from itertools import combinations, permutations
l=['A','B','C','D','E','F','G','H','I','J']
c=list(permutations(l))
d=list(combinations(l,2))
from collections import defaultdict

dic = defaultdict(int)

for i in d:
    dic[i]=1


new =[]
for i in c:
    tmp=[]
    for j in range(1,len(i),2):
        tmp.append((i[j-1],i[j]))
    new.append(tmp)


final =[]

for i in new:
    flag =True
    count =0 
    for j in i:
        try:
            if dic[j]:
                count+=1
                pass

        except:
            flag=False
            count=0
            break
    if flag and count==5:
        final.append(i)

final2 = [tuple(sorted(i)) for i in final]   

solution = list(set(final2))
print(solution)

будет 945 таких пар значений, которые существуют таким образом

...