Эффективное создание комбинаций без дублированных подмножеств - PullRequest
Новая
       5

Эффективное создание комбинаций без дублированных подмножеств

0 голосов
/ 26 ноября 2018

Учитывая, что у меня есть N (1 ≤ N) чисел, 1 .. N, эффективно генерирует максимальное количество возможных L (1 ≤ L ≤ N) размеров комбинаций с ограничением на то, что любое подмножество длины U комбинации (1 ≤ U ≤ L) появляется только один раз в результате.Обычно есть много результатов, удовлетворяющих ограничениям - подойдет любой результат.

Например, если N равно 5, L равно 3 и окончательное ограничение отбрасывается (т. Е. Ответом являются только комбинации), то имеем: 

123,124,125,134,135,145,234,235,245,345;

Как только ограничение U равно 2, любая из этих строк является приемлемым решением при условии, что оно генерируется эффективно: 

123,145;
123,245;
123,345;
124,135;
124,235;
124,345;
125,134;
125,234;
125,345;

идеальное время выполнения - O (size_of_output).В моем случае N всегда намного (на порядок или больше), чем L, поэтому все, что быстрее, чем вычисление всех комбинаций, будет улучшением того, что я придумал (что слишком медленно): 

import itertools

def unique_combinations(population, length, unique):
    seen = set()
    for r in itertools.combinations(range(population), length):
        u = set(itertools.combinations(r, unique))
        if not (u & seen):
            yield r
            seen |= u

Бонусные баллы за предоставление способа детерминистически выбрать любое решение из списка действительных.Например, было 9 действительных решений для примера (N=5,L=3,U=2) выше.Было бы здорово иметь дополнительный параметр 1 .. 9 для выбора возвращаемого значения.

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

1 Ответ

0 голосов
/ 27 ноября 2018

Это комментарий, вставленный в ответ, потому что он слишком велик для комментария.

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

Так что, если ОП может объяснить параметр U, чтобы я мог его понять, то я могу видеть,моя идея работает, и если так, отправьте ответ и объясните это здесь.Но если ОП не помогает мне помочь ему, то ответ может быть сметен в песках времени.

Для первой части 

comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-
    N>0,
    N1 is N-1,
    comb(N1,T,Comb).
comb(N,[_|T],Comb) :-
    N>0,
    comb(N,T,Comb).

когда пробег вернется 

?- comb(3,[1,2,3,4,5],C).
C = [1, 2, 3] ;
C = [1, 2, 4] ;
C = [1, 2, 5] ;
C = [1, 3, 4] ;
C = [1, 3, 5] ;
C = [1, 4, 5] ;
C = [2, 3, 4] ;
C = [2, 3, 5] ;
C = [2, 4, 5] ;
C = [3, 4, 5] ;
false.
...