Генерация всех подмножеств множества мощности n,которые не содержат соседних элементов

Предположим у меня есть множество A={1,2,...,n}.(длинна n известна)
Как мне сгенерировать все подмножества,которые не содержат соседних елементов?" (к примеру,если я беру элемент 2 из A, то то элементы 1 и 3 я взять уже не могу)
P.S:Сначала думал просто сгенрировать все подмножества, а потом выбрать те,которые не содержат соседних элементов.Но такой подход очень не эффективен.
P.P.S.:рекурсией пользоваться нельзя

Ответ

Стоит начать с того, что максимальная мощность такого подмножества будет 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])]
`