Предположим у меня есть множество A={1,2,...,n}.(длинна n известна)
Как мне сгенерировать все подмножества,которые не содержат соседних елементов?"
(к примеру,если я беру элемент 2 из A, то то элементы 1 и 3 я взять уже не могу)
P.S:Сначала думал просто сгенрировать все подмножества, а потом выбрать те,которые
не содержат соседних элементов.Но такой подход очень не эффективен.
P.P.S.:рекурсией пользоваться нельзя
Ответы
Ответ 1
Стоит начать с того, что максимальная мощность такого подмножества будет ceil(n/2).
Минимальная - единица. Соответсвенно, нужно сгенерировать все подмножества длиной 1,
затем длиной 2, затем ..., и так далее до ceil(n / 2). Суть данного решения в том,
что есть зафиксированные элементы и итератор, который добирает из множества нужное
количество элементов. Например для подмножеств мощностью 2: есть подмножества {1,3},
{1,4}, {1,5}, {1,6}. Фиксированный элемент здесь - 1, и итератор собирает все элементы
последовательно, начиная с 3. Когда итератор дойдет до конца - фиксированный элемент
меняется. Так как подмножества могут быть длиннее, чем 2, то фиксированный элемент
- это тоже множество - переменная subset_base. Для каждого нового "уровня" (для подмножества
с мощностью + 1) - фиксированные элементы не генерируются заново, а берутся прямиком
с предыдущего уровня и затем дополняются. Ключевая строка, пожалуй - это subset_first
= tpl[1] + 2 - именно здесь определяется, что сосед не попадет в подмножество. Можно
изменять слагаемое 2, определяя критерий "соседства".
Необходимо n / 2 раз пройти по всему множеству. Таким образом сложность O(n^2).
import math
A = {1, 2, 3, 4, 5, 6, 7, 8}
subsets = [{elem} for elem in A]
A = sorted(list(A)) # Для удобства
seeker_position = 0
subset_first = 0
subset_length = 2
base_subsets_for_next_level = [({elem}, index) for index, elem in enumerate(A)]
while subset_length <= math.ceil(len(A) / 2):
helper = []
for tpl in base_subsets_for_next_level:
subset_base = tpl[0]
subset_first = tpl[1] + 2
while subset_first < len(A):
subset = subset_base | {A[subset_first]}
subsets.append(subset )
helper.append((subset, subset_first))
subset_first += 1
base_subsets_for_next_level = helper
seeker_position += 1
if seeker_position + 2 * (subset_length - 1) >= len(A):
subset_length += 1
seeker_position = 0
subsets.append({}) # Пустое множество
print(subsets)
Результат: [set([1]), set([2]), set([3]), set([4]), set([5]), set([6]), set([7]),
set([8]), set([1, 3]), set([1, 4]), set([1, 5]), set([1, 6]), set([1, 7]), set([8,
1]), set([2, 4]), set([2, 5]), set([2, 6]), set([2, 7]), set([8, 2]), set([3, 5]),
set([3, 6]), set([3, 7]), set([8, 3]), set([4, 6]), set([4, 7]), set([8, 4]), set([5,
7]), set([8, 5]), set([8, 6]), set([1, 3, 5]), set([1, 3, 6]), set([1, 3, 7]), set([8,
1, 3]), set([1, 4, 6]), set([1, 4, 7]), set([8, 1, 4]), set([1, 5, 7]), set([8, 1,
5]), set([8, 1, 6]), set([2, 4, 6]), set([2, 4, 7]), set([8, 2, 4]), set([2, 5, 7]),
set([8, 2, 5]), set([8, 2, 6]), set([3, 5, 7]), set([8, 3, 5]), set([8, 3, 6]), set([8,
4, 6]), set([1, 3, 5, 7]), set([8, 1, 3, 5]), set([8, 1, 3, 6]), set([8, 1, 4, 6]),
set([8, 2, 4, 6])]
`
