Эффективно генерирующие «цепи вычитания»

Question

Я отправил another question раньше, если вы хотите какой-то контекст. Похоже, что с этим подходом я ошибался.

Addition chains может использоваться для сведения к минимуму количества умножений, необходимых для повышения числа. Например, для требуется четыре умножения. Два вычислить = а × а и = а × в , и еще два, чтобы вычислять = а × × а.

Аналогичным образом, я пытаюсь создать все возможные «цепи вычитания» для набора чисел. Например, учитывая набор чисел {1, 2, 3}, я пытаюсь сгенерировать следующие перестановки.

{1, 2, 3} 

{1, 2, 3}, {1, 2} 
{1, 2, 3}, {1, 2}, {1} 
{1, 2, 3}, {1, 2}, {2} 
{1, 2, 3}, {1, 2}, {1}, {2} 

{1, 2, 3}, {1, 3} 
{1, 2, 3}, {1, 3}, {1} 
{1, 2, 3}, {1, 3}, {3} 
{1, 2, 3}, {1, 3}, {1}, {3} 

{1, 2, 3}, {2, 3} 
{1, 2, 3}, {2, 3}, {2} 
{1, 2, 3}, {2, 3}, {3} 
{1, 2, 3}, {2, 3}, {2}, {3} 

{1, 2, 3}, {1, 2}, {1, 3} 
{1, 2, 3}, {1, 2}, {1, 3}, {1} 
{1, 2, 3}, {1, 2}, {1, 3}, {2} 
{1, 2, 3}, {1, 2}, {1, 3}, {3} 
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2} 
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3} 
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3} 
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3} 

# and so on... 

где каждый элемент в перестановке (помимо {1, 2, 3}) может быть найден путем удаления одного элемента из другого множества в перестановке.

Например, перестановка {1, 2, 3}, {1} недействительна, так как {1} не может быть сконструирован путем удаления одного элемента из {1, 2, 3}.

Есть ли известный алгоритм для поиска этого подмножества силового набора силового набора? Моя реализация будет в Python, но вопрос - агностик. Кроме того, я действительно не хочу, чтобы перестановки, содержащие набор с одним элементом (например, {1, 2, 3}, {1, 2}, {1}), потому что они соответствуют случаю «диктатора», который не представляет интереса.

Answer 1

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

Вот реализация в Python, как функция генератора, без большой оптимизации. Кажется, теперь это работает очень хорошо, создавая все подмножества без каких-либо дубликатов.

def generate_sets(sets, min_num=2): 
    yield sets 
    added = set() # new sets we already generated in this iteration 
    for set_ in sets: 
     # only if the current set has the right length 
     if min_num < len(set_) <= len(sets[-1]) + 1: 
      for x in set_: 
       # remove each element in turn (frozenset so we can put in into added) 
       new = set_.difference({x}) 
       # prevent same subset being reachable form multiple sets 
       frozen = frozenset(new) 
       if frozen not in added: 
        added.add(frozen) 
        # recurse only if current element is "smaller" than last 
        if (len(new), sorted(new)) < (len(sets[-1]), sorted(sets[-1])): 
         for result in generate_sets(sets + [new], min_num): 
          yield result 

Для generate_sets([{1,2,3}], min_num=2) это порождает следующие списки:

[{1, 2, 3}] 
[{1, 2, 3}, {2, 3}] 
[{1, 2, 3}, {2, 3}, {1, 3}] 
[{1, 2, 3}, {2, 3}, {1, 3}, {1, 2}] 
[{1, 2, 3}, {2, 3}, {1, 2}] 
[{1, 2, 3}, {1, 3}] 
[{1, 2, 3}, {1, 3}, {1, 2}] 
[{1, 2, 3}, {1, 2}] 

Для generate_sets([{1,2,3}], 1), в общей сложности 45 списков множеств генерируются.

Однако, я не вижу связи с предыдущим вопросом: не следует ли {1, 2, 3}, {1, 2}, {1, 2, 3}, {1, 3} и {1, 2, 3}, {2, 3} считать эквивалентными?