генерировать все перегородки набора

Question

Для набора A = {1, 2, 3, ..., n}. Это называется разбиением множества A, набор k<=n элементов, которые соблюдают следующие теоремы:

а) объединение всех разделов A является A

б) пересечение 2 перегородок A является пустое множество (они не могут использовать одни и те же элементы).

Например. A = {1, 2,... n} У нас есть разделы: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

Эти теоретические концепции представлены в моем учебнике алгоритмов (кстати, этот подраздел является частью «по отслеживанию» главы). Я должен найти алгоритм для генерации всех разделов данного набора. Я боролся с этой проблемой весь день, и я не мог найти решение. Можете ли вы объяснить мне, как работает этот алгоритм? Кроме того, можете ли вы дать мне псевдо-кодовый эскиз алгоритма?

Answer 1

Вы можете попробовать рекурсивный ответ, если ваш набор не большой (или еще стека использования):

Принцип заключается в следующем, у вас есть функция, которая отплатить:

rec_func(SET) = List of List of Set 

И работать следующим образом:

rec_func(SET) = 
    if SET = {empty}: 
    // if no element, easy to give the answer 
    return([[]]) 
    else: 
    // 1. Remove one element from the set : 'a' to this set 
    a = SET.pop() 
    // 2. Call rec_func : 
    list_of_list_of_set = rec_func(SET\'a') 
    response = [] 
    // 3. For every possibilities given by the function add the element 'a' : 
    For every list_of_set in list_of_list_of_set : 
     // Case 1, you add 'a' to list_of_set 
     response.push([{'a'} + list_of_set]) 
     // Case 2, for every set, you create a copy where you add 'a' 
     for every set in list_of_set: 
      response.push([{set,'a'} + list_of_set\set]) 

    // The function return the list of list of set created.   
    return(response) 

Answer 2

Существует важное наблюдение (в комментарии), что разбиение множества n элементов могут быть представлены в виде целого последовательности форма [p , & hellip; р п], где р я это номер раздела элемента я. Для такой последовательности, чтобы быть действительным, он должен подчиняться правилам, которые р является 1, и для каждого J где 1 < J ≤ п, есть некоторые я < J такое, что р _J≤ р_i + 1. Или, другими словами, в любом префиксе последовательности никакое целое число не пропускается.

В настоящее время, существует стандартный алгоритм для перечисления ограниченных последовательностей в лексикографическом порядке, который состоит из следующих действий:

• Start с наименьшей последовательности.
• Чтобы найти следующую последовательность в лексикографическом порядке:
  • сканирование в обратном направлении по последовательности и найти самый правый «incrementable» элемент. (Инкрементный элемент - это такой элемент, что существует некоторый более крупный элемент, который может быть заменен для этого элемента, а полученная подпоследовательность до этой точки является префиксом по меньшей мере одной допустимой последовательности.)
  • Измените этот элемент на следующий более крупный элемент, который является жизнеспособным (т. е. приводит к действительному префиксу, как указано выше), а затем заполняет оставшиеся элементы справа (если есть) с наименьшими возможными значениями.
  • Если нет добавочного элемента, то перечисление завершается.

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

Чтобы применить этот алгоритм к мы наблюдаем следующее:

1. Наименьшая возможная последовательность [1, & hellip; 1]
2. Элемент р_я является incrementable при условии, что:
   • р_я < н
   • Существует несколько J < я такой, что p_i & equals; р_J
3. Самый маленький суффикс жизнеспособного префикса [1, & hellip; 1]

Другой способ задания состояния при наблюдении 2 является то, что элемент является incrementable, если его значение не п или это первый элемент в последовательности с ее значением.Мы можем сделать это определение в O (1), если мы также сохраним последовательность [m , & hellip; м п], где м равно 0, а м я это максимум м_{я -1} и р_{я -1}. м тривиально поддерживать, и это позволяет нам переписать условие incrementability как просто р_я ≤ м_я.

Легко видеть, что Следующая Partition могут быть реализованы в O (п) времени, но, как это бывает и так, что он амортизируется время O (1). Грубо говоря, это потому, что в большинстве случаев последний элемент последовательности является инкрементальным.

Answer 3

Я работал над эффективным алгоритмом, который создает все разделы набора, как описано выше, на основе подхода ключевого слова, определяемого @rici. Следующий алгоритм, написанный на python, делает это, и есть еще возможность оптимизации. Я нахожусь на нем. Как вы знаете, эта проблема NP-полная! Из-за оптимизации есть, может быть, какая-то странная нотация, например try/except. Тем не менее, переменные n и k должны определять через n, сколько разных элементов имеет множество, а k - количество различных классов, которым разрешено иметь множество. INFO: алгоритм генерирует ВСЕ разделы до количества разных классов не только этих классов !!!

def partitions(): 
     global n 
     global k 
     codeword = [1 for digitIndex in range(0, n)] 
     while True: 
       print codeword 
       startIndex = n - 1 
       while startIndex >= 0: 
         maxValue = max(codeword[0 : startIndex]) 
         if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k: 
           codeword[startIndex] = 1 
           startIndex -= 1 
         else: 
           codeword[startIndex] += 1 
           break 

n = 12 
k = 2 
try: 
     partitions() 
except: 
     pass