Обрезать список комбинаций на основе наборов

Question

Хотя этот вопрос сформулирован с использованием языка программирования Python, я считаю, что это скорее проблема программирования.

У меня есть список всех возможных комбинаций, а именно: п выбрать K

Я могу подготовить такой список, используя

import itertools 
bits_list = list(itertools.combinations(range(n), k)) 

Если «п» 100 и 'к»5, то длина «bits_list» будет равна 75287520.

Теперь я хочу обрезать этот список, чтобы числа отображались в группах, или нет. Давайте использовать следующие наборы в качестве примера:

Set 1: [0, 1, 2]
набор 2: [57, 58]
Набор 3: [10, 15, 20, 25]
Набор 4: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Здесь каждый набор должен отображаться в любом члене списка бит или вместе.

До сих пор я только мог думать о методе грубой силы if-else для решения этой проблемы, но число условий if-else будет очень большим.

Вот что у меня есть:

bits_list = [x for x in list(itertools.combinations(range(n), k)) 
      if all(y in x for y in [0, 1, 2]) or 
      all(y not in x for y in [0, 1, 2])] 

Теперь это охватывает только набор 1. Я хотел бы сделать это для многих наборов. Если длина набора больше, чем значение k, мы можем игнорировать множество (например, k = 5 и Set 4).

Обратите внимание, что конечная цель состоит в том, чтобы «k» перебирать диапазон, скажем [5:25] и работать над добавленным списком. Размер списка растет экспоненциально здесь, и вычислительно говоря, очень дорого!

С «k» как 10 интерпретатор python прерывает процесс до завершения на любом среднем ноутбуке с 16 ГБ ОЗУ. Мне нужно найти решение, которое подходит для памяти относительно современного сервера (а не кластера или фермы серверов).

Любая помощь с благодарностью!

P.S .: Интуитивно подумайте об этой проблеме как о создании всех возможных случаев для людей, посещающих общественный автобус или систему поездов. Обычно вы садитесь на целую группу, или вы никого не посещаете.

---

ОБНОВЛЕНИЕ:

1. Для заданных наборов выше, если к = 5, то действительный член bits_list будет [0, 1, 2, 57, 58], а именно: сочетание из Set1 и Set2. Если k = 10, то мы могли бы построить Set1 + Set2 + Set3 + NoSetElement в качестве возможного члена. @ Решение DonkeyKong заставило меня понять, что я не упомянул об этом в моем вопросе.

2. У меня много комплектов; Я намерен использовать достаточное количество наборов, чтобы обрезать полный список комбинаций таким образом, чтобы бит_list в конечном итоге вписывался в память.

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

Answer 1

Основываясь на идеях от @Mitch's answer, я создал решение с немного иным мышлением, чем первоначально представлено в вопросе. Вместо того, чтобы создавать список (bits_list) всех комбинаций, а затем обрезать те комбинации, которые не соответствуют перечисленным наборам, я создал bits_list из наборов.

import itertools 
all_sets = [[0, 1, 2], [3, 4, 5], [6, 7], [8], [9, 19, 29], [10, 20, 30], 
      [11, 21, 31], [12, 22, 32], ...[57, 58], ... [95], [96], [97]] 
bits_list = [list(itertools.chain.from_iterable(x)) for y in [1, 2, 3, 4, 5] 
      for x in itertools.combinations(all_sets, y)] 

Здесь, вместо того чтобы найти п выбрать к, а затем цикл для всех к, и найти комбинации, которые соответствуют наборы, я начал из наборов, и даже включены отдельные элементы, как наборы сами по себе и, следовательно, удаление потребность в двух компонентах - непересекающихся и частичных частях - обсуждается в @Mitch's answer.

Answer 2

Более быстрая реализация будет заменить тогда и все() заявления в:

bits_list = [x for x in list(itertools.combinations(range(n), k)) 
      if all(y in x for y in [0, 1, 2]) or 
      all(y not in x for y in [0, 1, 2])] 

с множеством операций isdisjoint() питона и issubset() операций.

bits_generator = (set(x) for x in itertools.combinations(range(n), k)) 
first_set = set([0,1,2]) 
filter_bits = (x for x in bits_generator 
      if x.issubset(first_set) or 
      x.isdisjoint(first_set)) 
answer_for_first_set = list(filter_bits) 

Я могу продолжать с помощью генераторов и генераторов, которые вы не будете запускать из памяти, но вы будете ждать и ускоряя тепловой смерти Вселенной. Не из-за времени выполнения python или других деталей реализации, а потому, что есть некоторые проблемы, которые просто невозможны даже в компьютерное время, если вы выбираете большие значения N и K.

Answer 3

Это все еще раздавлено ошибкой памяти (), в которой я не вижу, как вы уходите, если вы настаиваете на списке) в определенной точке (около n = 90, k = 5), но это намного быстрее, чем ваша текущая реализация. Для n=80 и k=5 у моего рудиментарного бенчмаркинга было мое решение на 2,6 секунды, а ваше - около 52 секунд.

Идея состоит в том, чтобы сконструировать непересекающиеся и подмножество частей вашего фильтра отдельно. Непересекающаяся часть тривиальна, а часть подмножества вычисляется путем принятия itertools.product всех непересекающихся комбинаций длины k - set_len и отдельных элементов вашего набора.

from itertools import combinations, product, chain 
n = 80 
k = 5 
set1 = {0,1,2} 

nots = set(range(n)) - set1 
disj_part = list(combinations(nots, k)) 
subs_part = [tuple(chain(x, els)) for x, *els in 
       product(combinations(nots, k - len(set1)), *([e] for e in set1))] 
full_l = disj_part + subs_part 

Answer 4

Если вы на самом деле представляли свои биты как биты, то есть 0/1 значения в двоичном представлении целого числа п битов длиной с точно установить K бит, объем оперативной памяти вы должны хранить данные будут значительно меньше.

Кроме того, вы сможете использовать битовые операции, чтобы посмотреть и проверить, если все биты в mask фактически установлены (value & mask == mask), или все сняты с охраной (value | ~mask == value).

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

Если вы должны выполнять это часто и быстро, а ваш n - это небольшие сотни или менее, я бы скорее использовал cython для описания алгоритма грубой силы, а не для улучшения алгоритмических улучшений. Современные процессоры могут эффективно работать с 64-битными номерами; вы не выиграете от того, чтобы не сравнивать часть номера.

OTOH, если ваш n действительно большой, а также количество комплектов для сравнения с большим, вы можете разбить свои биты для эффективного сравнения.

Предположим, вы можете эффективно сравнивать кусок 64 бит, а ваши списки бит содержат, например, 100 кусков каждый. Затем вы можете сделать то же самое, что делали бы со строками: сравнить кусок на куске, и если один из кусков не подходит, не сравнивайте остальных.