3

Предположим у меня есть множество A={1,2,...,n}.(длинна n известна)

Как мне сгенерировать все подмножества,которые не содержат соседних елементов?" (к примеру,если я беру элемент 2 из A, то то элементы 1 и 3 я взять уже не могу)

P.S:Сначала думал просто сгенрировать все подмножества, а потом выбрать те,которые не содержат соседних элементов.Но такой подход очень не эффективен.

P.P.S.:рекурсией пользоваться нельзя

6
  • Очень похоже на домашнее задание - что уже было сделано? Какие конкретно проблемы возникли?
    – m9_psy
    7 июн 2016 в 12:00
  • Проблема возникла в том,что бы корректно пройтись по всему множеству,так как выбор каждого елемента вынуждает убирать из множества соседние даному елементы. 7 июн 2016 в 12:10
  • Интересная задача. Первое что пришло в голову, это свести к задаче генерации битовых массивов, таких что нет двух подряд идущих битов 1. Нужно подумать как от этого можно плясать.
    – iksuy
    7 июн 2016 в 12:32
  • А какие ограничения на размер n?
    – iksuy
    7 июн 2016 в 12:45
  • 1
    А почему нельзя рекурсию? Она ж тут просто напрашивается.
    – Yaant
    7 июн 2016 в 12:57

1 ответ 1

4

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

`

4
  • 1
    А почему в результат не попало set([1, 4, 6])?
    – Yaant
    7 июн 2016 в 14:02
  • Ошибочка. Не попало, потому что элементы для фиксированного элемента отбираются через один, а четыре отстоит от единицы на 3 шага. Буду исправлять
    – m9_psy
    7 июн 2016 в 14:05
  • я не специалист в питоне, но идея такая: идём слева, грубо говоря у нас есть 3-х мерный (!) массив. 1 - слой - номер вершины. 2 - слой - массив массивов в ответ. Пересчёт - идём циклом от 1 к N и загоняем в текущую ячейку всё что лежит в массивах от 1 до i-2, добавив текущий во все массивы. Это очень грубый метод но должно хватить.
    – pavel
    7 июн 2016 в 14:15
  • @Yaant, должно быть исправил.
    – m9_psy
    7 июн 2016 в 15:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.