Генерация всех «уникальных» подмножеств набора (не powerset)

Question

Допустим, у нас есть набор S, который содержит несколько подмножеств:

- [a,b,c]
- [a,b]
- [c]
- [d,e,f]
- [d,f]
- [e]

Скажем также, что S содержит шесть уникальных элементов: a, b, c, d, e и f.

Как мы можем найти все возможные подмножества S, которые содержат каждый из уникальных элементов S ровно один раз?

Результат функции / метода должен быть примерно таким:

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

Есть ли лучшая практика или какой-либо стандартный способ добиться этого?

Буду признателен за пример псевдокода, Ruby или Erlang.

Answer 1

Звучит так, как будто вы ищете разделы набора / массива.

Один из способов сделать это рекурсивно:

• a1 элемент массива [x] имеет ровно один раздел
• , если x является массивом вида x = [head] + tail, то разделы x генерируются путем взятия каждого раздела tail и добавления головы к каждомувозможный.Например, если мы генерировали разделы из [3,2,1], то из раздела [[2,1]] из [2,1] мы можем добавить 3 к [2,1] или как отдельный элемент, что дает нам 2 раздела [[3,2,1] или [[2,1], [3]] из 5, которые [1,2,3] имеют

Реализация rubyвыглядит немного как

def partitions(x)
  if x.length == 1
   [[x]]
  else
    head, tail = x[0], x[1, x.length-1]
    partitions(tail).inject([]) do |result, tail_partition|
      result + partitions_by_adding_element(tail_partition, head)
    end
  end
end

def partitions_by_adding_element(partition, element)
  (0..partition.length).collect do |index_to_add_at|
    new_partition = partition.dup
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element]
    new_partition
  end
end

Answer 2

Почему бы не использовать жадный алгоритм?

1) сортировать набор S по убыванию с использованием длины подмножеств
2) let i: = 0
3) добавить S [i] к решению
4) найти S [j], где j> i, например, содержащий элементы, которых нет в текущем решении
5) если вы не можете найти элемент, описанный в 4, тогда
5.a) ясное решение
5.b) увеличить i
5.c), если i> | S |затем прервитесь, решение не найдено; (5.d) перейдите к 3

РЕДАКТИРОВАТЬ
Хмм, прочитайте еще раз ваш пост и придите к выводу, что вам нужен Best-Firstпоиск .Ваш вопрос на самом деле не является проблемой разбиения, потому что то, что вам нужно, также известно как проблема изменения , но в последнем случае самое первое решение принимается как лучшее - вы на самом деле хотите найти все решения иВот почему вы должны выбрать подход «лучшая стратегия поиска».

Answer 3

посмотрите здесь: https://github.com/sagivo/algorithms/blob/master/powerset.rb
это простой алгоритм, который я построил, чтобы найти powerset массива.

Answer 4

генерирует все подмножества

def allSubsets set
    combs=2**set.length
    subsets=[]
    for i in (0..combs) do
        subset=[]
        0.upto(set.length-1){|j| subset<<set[j] if i&(1<<j)!=0}
        subsets<<subset
    end
    subsets
end

Answer 5

Это похоже на классическое упражнение "backtrack".

• # 1: упорядочите свои наборы среди eacother, чтобы backtrack не давал решения дважды.
• # 2: current_set= [], set_list = []
• # 3: цикл Проходит через весь набор, который имеет метку более низкого порядка, чем последний в списке set_list, (или все, если set_list пуст).Давайте назовем его set_at_hand
• # 4: если set_at_hand не имеет пересечения с current_set
• # 4 / true / 1: объединить его в current_set, также добавить в set_list.
• #4 / true / 2: текущий_сет завершен?true: добавить set_list в список правильных решений.false: возврат к # 3
• # 4 / true / 3: удаление set_at_hand из current_set и set_list
• # 5: конец цикла
• # 6: возврат