Перечислить все комбинации, но с ограничением

Я нашел способ перечислить все возможные комбинации из n элементов, сгруппированных в наборы из k элементов. По математике, число легко: n! / (K! * (N-k)!), А код Python действительно прост с использованием itertools:

>>> import itertools
>>> a = [1,2,3,4]
>>> list(itertools.combinations(a,3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

Но как реализовать ограничение типа: перечислять только группы, содержащие только m общих элементов? поэтому в предыдущем примере для m = 1 результат должен быть:

[(1, 2, 3)]

С 5 элементами и m = 1:

>>> b=[1,2,3,4,5]
>>> list(itertools.combinations(b,3))
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

Итак, мой результат:

[(1, 2, 3), (1, 4, 5)]

Практическое применение этого вопроса - как сгруппировать людей, учитывая, что только m человек могут повторяться в группах результатов. Идея состоит в том, чтобы найти группы с разными людьми, чтобы избежать групп «друзей». Представьте себе школьное мероприятие, которое повторяется несколько дней, и мы хотим, чтобы люди как можно больше не повторяли друг друга.


python combinations itertools
person joanba    schedule 04.01.2018    source источник
comment
Все ваши кортежи в примере содержат как минимум два разных элемента.   -  person Klaus D.    schedule 04.01.2018
comment
извини, я ничего не могу поделать, это просто на высоте, @KlausD.   -  person stucash    schedule 04.01.2018
comment
@joanba разные элементы по отношению к чему? Первый кортеж?   -  person Bharath    schedule 04.01.2018
comment
Вы перефразировали это, но яснее не стало.   -  person Klaus D.    schedule 04.01.2018
comment
Вы так быстро отвечаете, просто редактируете пост, чтобы было понятнее   -  person joanba    schedule 04.01.2018
comment
Что делает ваши числа друзьями? Подумайте, как вы задаете свой вопрос! Если люди не могут этого понять, компьютер не поймет и ваши инструкции.   -  person Klaus D.    schedule 04.01.2018
comment
Идея здесь в том, как сгруппировать класс из 20 человек в группы по 5 человек, но разрешить только группы, состоящие только из 2 человек. Не уверен, что это объяснение более понятно.   -  person joanba    schedule 04.01.2018

Ответы (3)


arrow_upward
0
arrow_downward

Вы можете использовать цикл for:

m = 1
combos = list(itertools.combinations(a,3))
result = []
for combo in combos:
    if result:
        if all([sum([1 for item in combo if item in tup]) == 1 for tup in result]):
            result.append(combo)
    else:
        result.append(combo)
result
#[(1, 2, 3), (1, 4, 5)]

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

person zipa    schedule 04.01.2018
comment
@erhesto и совершенно правильно, но я написал новые имена для переменных. - person zipa; 04.01.2018

arrow_upward
1
arrow_downward

Можно использовать цикл for для сравнения первой комбинации с остальной (используя функцию пересечения множества "&"):

def getsets(a, n):              # FUNCTION FOR THIS PURPOSE
    combos = list(itertools.combinations(a,n))  # GET ALL COMBINATIONS
    print(combos[0])            # PRINT FIRST COMBINATION
    for i in combos[1:]:        # FOR EACH OF REST
        if len(set(combos[0]) & set(i)) == 1:       # IF ONLY 1 ITEM COMMON WITH INITIAL
            print(i)            # PRINT IT

Тестирование:

getsets([1,2,3,4], 3)
print("---------")
getsets([1,2,3,4,5], 3)

Выход:

(1, 2, 3)   # INITIAL SET ONLY
---------
(1, 2, 3)   # INITIAL SET
(1, 4, 5)   # ONLY '1' IS COMMON WITH FIRST SET
(2, 4, 5)   # ONLY '2' IS COMMON WITH FIRST SET
(3, 4, 5)   # ONLY '3' IS COMMON WITH FIRST SET
{1, 2, 3}   # ONLY '4' IS COMMON WITH FIRST SET
person rnso    schedule 04.01.2018

arrow_upward
0
arrow_downward

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

a = range(1,6)
shared_elem_count = 1
group_count = 3

combinations = itertools.combinations(a, group_count)
results = []

for combination in combinations:
    res_union = set().union(*results)
    intersection = set(combination).intersection(res_union)
    if len(intersection) <= shared_elem_count:
        results.append(combination)

Как и в вашем примере, кортежи не имеют более m общих элементов с любыми другими доступными. Но, как указано в комментариях, это решение строго связано с порядком операций. Первый кортеж определяет, какие следующие кортежи будут приемлемыми.

Помните, что то, что вы сказали в своем комментарии, является проблемой, которая немного шире: объединение n людей в группы по количеству k, в которых не более m человек, даст значительно больше решений, чем те, которые мы не отфильтровали из'. Например, вы указали, что для m = 1 и a = (1,2,3,4,5) решение:

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

... но на самом деле решений гораздо больше, например:

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

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

person erhesto    schedule 04.01.2018
comment
(2,3,4) не может быть решением, потому что оно имеет 2 общих элемента с исходным решением (1,2,3) - person joanba; 04.01.2018
comment
Вы никогда не говорили что является исходным решением. Если вы заказываете itertools.combinations(a, group_count) другой способ, вы можете получить другое исходное решение. То, что я перечислил в своем ответе, на самом деле является группами решений (каждая группа состоит из 2 элементов), а не дополнительными комбинациями для (1,2,3),(1,4,5). - person erhesto; 04.01.2018