Создать список со списками подмножеств заданного размера набора - PullRequest
Новая
       35

Создать список со списками подмножеств заданного размера набора

0 голосов
/ 05 апреля 2019

Мне нужно написать код, который возвращает подмножества заданного размера набора в списке. Итак, сначала скажем, что я хочу подмножества размера 3 из набора (0,1,2,3,4,5,6,7,8)

И я хочу выписать подмножества в список:

[[0,1,2], [0,2,3], [0,3,4] ....]

И затем я хотел бы пойти с рекурсией и сравнить все элементы, кроме первого, со своим словарем (графиком), чтобы проверить, есть ли в моем значении, которое является списком. Ключ словаря - это первый элемент в моем подмножестве.

Как например:

в [0,1,2]:

равно 1 и 2 на графике [0]?

словарный график имеет вид: {0: [1,2,3,6,7], 1: [0,2,4,6,7] ....}

И если я закончу и все будет готово, я хочу проверить следующее подмножество.

Итак, моя проблема, как я могу поместить это в список? Я знаю, что у меня тоже есть проблема с k, но не знаю, как ее изменить. 

def indep(graph,a,b):
    l=list( itertools.combinations(range(a), b))
    for k in l:
        k=list(k)
        while j<=len(k):
           for j in range(len(k)): 
              if k[j]  in graph[k[j]]:
                 j+=1
              else:
                return "no"

Ответы [ 2 ]

1 голос
/ 05 апреля 2019

Это даст ожидаемый результат

из комбинаций импорта itertools 

original_set = (0,1,2,3,4,5,6,7,8)
final_set = [list(pair) for pair in combinations(l, 3)]

Out[6]: 
[[0, 1, 2],
 [0, 1, 3],
 [0, 1, 4],
 [0, 1, 5],
 [0, 1, 6],
 [0, 1, 7],
 [0, 1, 8],
 [0, 2, 3],
 [0, 2, 4],
 [0, 2, 5],
 [0, 2, 6],
 [0, 2, 7],
 [0, 2, 8],
 [0, 3, 4],
 [0, 3, 5],
 [0, 3, 6],
 [0, 3, 7],
 [0, 3, 8],
 [0, 4, 5],
 [0, 4, 6],
 [0, 4, 7],
 [0, 4, 8],
 [0, 5, 6],
 [0, 5, 7],
 [0, 5, 8],
 [0, 6, 7],
 [0, 6, 8],
 [0, 7, 8],
 [1, 2, 3],
 [1, 2, 4],
 [1, 2, 5],
 [1, 2, 6],
 [1, 2, 7],
 [1, 2, 8],
 [1, 3, 4],
 [1, 3, 5],
 [1, 3, 6],
 [1, 3, 7],
 [1, 3, 8],
 [1, 4, 5],
 [1, 4, 6],
 [1, 4, 7],
 [1, 4, 8],
 [1, 5, 6],
 [1, 5, 7],
 [1, 5, 8],
 [1, 6, 7],
 [1, 6, 8],
 [1, 7, 8],
 [2, 3, 4],
 [2, 3, 5],
 [2, 3, 6],
 [2, 3, 7],
 [2, 3, 8],
 [2, 4, 5],
 [2, 4, 6],
 [2, 4, 7],
 [2, 4, 8],
 [2, 5, 6],
 [2, 5, 7],
 [2, 5, 8],
 [2, 6, 7],
 [2, 6, 8],
 [2, 7, 8],
 [3, 4, 5],
 [3, 4, 6],
 [3, 4, 7],
 [3, 4, 8],
 [3, 5, 6],
 [3, 5, 7],
 [3, 5, 8],
 [3, 6, 7],
 [3, 6, 8],
 [3, 7, 8],
 [4, 5, 6],
 [4, 5, 7],
 [4, 5, 8],
 [4, 6, 7],
 [4, 6, 8],
 [4, 7, 8],
 [5, 6, 7],
 [5, 6, 8],
 [5, 7, 8],
 [6, 7, 8]]
0 голосов
/ 05 апреля 2019 
import itertools
a = [0,1,2,3,4,5,6]

# all sets here.
sets = [list(x) for x in itertools.permutations(a, 3) if x[1]==x[2]-1]

#here are all the sets
#[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 6], [1, 2, 3], [1, 3, 4], [1, 4, 5], [1, 5, 6], [2, 0, 1], [2, 3, 4],
#[2, 4, 5], [2, 5, 6], [3, 0, 1], [3, 1, 2], [3, 4, 5], [3, 5, 6], [4, 0, 1], [4, 1, 2], [4, 2, 3], [4, 5, 6], [5, 0, 1], 
#[5, 1, 2], [5, 2, 3], [5, 3, 4], [6, 0, 1], [6, 1, 2], [6, 2, 3], [6, 3, 4], [6, 4, 5]]

d = dict()
#make your thingy
for i in sets:
    try:
        d[i[0]] = d[i[0]]+i[1:]
    except:
        d[i[0]] = i[1:]

    d[i[0]] = list(set(d[i[0]]))

#output D

{0: [1, 2, 3, 4, 5, 6],
 1: [2, 3, 4, 5, 6],
 2: [0, 1, 3, 4, 5, 6],
 3: [0, 1, 2, 4, 5, 6],
 4: [0, 1, 2, 3, 5, 6],
 5: [0, 1, 2, 3, 4],
 6: [0, 1, 2, 3, 4, 5]}

это то, что вы хотели? : D

...