Я пытаюсь сгенерировать все возможные последовательности из наборов, которые частично перекрываются. Позвольте мне объяснить на примере. Допустим, у меня есть dict:
Код: Выделить всё
number_per_slot = {0: {0,1,2,3,4},
1: {2,3,4},
2: {4},
}
и я хотел бы сгенерировать все возможные последовательности длины 1, 2 и 3. Для последовательностей длины 2 я бы взял один элемент из number_per_slot[0] и один из number_per_slot[1], и аналогично для последовательностей длиной 3. Элементы не могут повторяться в последовательности, поэтому для приведенного выше dict я ожидаю получить на выходе:
{0} , {1}, {2}, {3}, {4}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1, 4}, {2,3}, {2,4}, {3,4}, {0,2,4}, {0,3,4}, {1,2,4}, {1,3, 4}, {2,3,4}.
Что я пытался сделать:
Код: Выделить всё
sequences = set()
for k in number_per_slot:
if k == 0:
sequences = {frozenset({i}) for i in number_per_slot[k]}
else:
new_sequences = {frozenset(seq.union({i})) for seq in sequences for i in number_per_slot[k]}
sequences.update(new_sequences)
В этом игрушечном примере это работает нормально, но если приведенный выше текст больше, это займет много времени. Например, если я переопределю dict как
Код: Выделить всё
TOTAL_NUMBERS = 150
number_per_slot = {0: {i for i in range(TOTAL_NUMBERS)},
1: {i for i in range(10,TOTAL_NUMBERS)},
2: {i for i in range(25,TOTAL_NUMBERS)},
3: {i for i in range(35,TOTAL_NUMBERS)},}
Тогда общее вычисление последовательности занимает около одной минуты. Есть ли способ сделать это более эффективно? Обратите внимание: мне не обязательно получать выходные данные в формате set[frozenset], но я думал, что это будет быстрее, чем использование списков или кортежей.
Подробнее здесь:
https://stackoverflow.com/questions/790 ... -from-sets