Цикл различных наборов уникальных перестановок

Question

Мне трудно начать работу с макетом кода для этой проблемы.

У меня фиксированное количество случайных чисел, в данном случае 8 чисел. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Это будет помещено в 3 набора чисел, с единственным ограничением, что каждый набор содержит минимум одно значение, и каждое значение может использоваться только один раз. Редактировать: должны использоваться все 8 чисел

Например:

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

Мне нужно пройтись по всем возможным комбинациям набора R1, R2, R3. Порядок не важен, поэтому, если приведенный выше пример произошел, мне не нужно

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

Что такое хороший метод?

Answer 1

Передо мной Кнут Кут Том 4, Fascicle 3, Генерация всех комбинаций и разделов , раздел 7.2.1.5 Генерация всех установленных разделов (стр. 61 в брошюре).

Сначала он детализирует Алгоритм H, Ограниченные строки роста в лексикографическом порядке из-за Джорджа Хатчинсона. Это выглядит просто, но я не собираюсь углубляться в это только сейчас.

На следующей странице под описанием Серые коды для заданных перегородок Обдумывает:

Предположим, однако, что нас не интересуют все разделов; мы могли бы хотеть только те, которые имеют m блоков. Можем ли мы выполнить это через меньшую коллекцию ограниченных строк роста, все еще меняя одну цифру за раз?

Затем он детализирует решение из-за Фрэнка Руски.

Простое решение (и определенно верное) состоит в кодировании алгоритма H фильтрации на разделах, где m==3 и ни один из разделов не является пустым набором (в соответствии с вашими установленными ограничениями). Я подозреваю, что Алгоритм H работает невероятно быстро, поэтому стоимость фильтрации не будет большой.

Если вы реализуете это на 8051, вы можете начать с алгоритма Ruskey, а затем фильтровать только те разделы, которые содержат пустой набор.

Если вы реализуете это для чего-то меньшего, чем значение 8051 и миллисекунды, вы можете заполнить каждый из трех разделов уникальным элементом (простой вложенный цикл из трех уровней), а затем увеличить, разделив на оставшиеся пять элементы для m==3 с использованием алгоритма Ruskey. Вам не нужно ничего фильтровать, но вы должны отслеживать, какие пять элементов остаются в разделе.

Хорошая особенность фильтрации по общему алгоритму заключается в том, что вам не нужно проверять собственную хитрость, и вы позже передумаете о своих ограничениях, не пересматривая свою хитрость.

Возможно, я даже найду решение позже, но пока это все.

P.S. для гуппи Java: я обнаружил поиск в «строках с ограниченным ростом Джорджа Хатчисона» определенного пакета ca.ubc.cs.kisynski.bell с документацией для метода growthStrings (), который реализует алгоритм Хатчисона.

Появляется доступным в http://www.cs.ubc.ca/~kisynski/code/bell/

Answer 2

Переверните проблему с ног на голову, и вы найдете простое решение. У вас есть 8 номеров, каждый из которых должен быть присвоен только одной группе; «Решение» является решением, только если каждой группе присвоен хотя бы один номер.

Тривиальная реализация будет включать 8 для циклов и несколько IF (псевдокод):

for num1 in [1,2,3]
  for num2 in [1,2,3]
    for num3 in [1,2,3]
      ...
        if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3))
          Print Solution!

Он также может быть реализован рекурсивно, с использованием двух массивов и пары функций. Гораздо приятнее и проще для отладки / отслеживания (псевдокод):

numbers = [1, 2, 3, 4, 5, 6, 7, 8]
positions = [0, 0, 0, 0, 0, 0, 0, 0]

function HandleNumber(i) {
  for position in [1,2,3] {
    positions[i] = position;
    if (i == LastPosition) {
        // Check if valid solution (it's valid if we got numbers in all groups)
        // and print solution!
      }
    else HandleNumber(i+1)
  }      
}

Третья реализация не будет использовать рекурсию и немного возврата. Псевдокод, опять же:

numbers = [1,2,3,4,5,6,7,8]
groups = [0,0,0,0,0,0,0,0]

c_pos = 0 // Current position in Numbers array; We're done when we reach -1
while (cpos != -1) {
  if (groups[c_pos] == 3) {
      // Back-track
      groups[c_pos]=0;
      c_pos=c_pos-1
    }
  else {
     // Try the next group
     groups[c_pos] = groups[c_pos] + 1
     // Advance to next position OR print solution
     if (c_pos == LastPostion) {
         // Check for valid solution (all groups are used) and print solution!
       }
     else
       c_pos = c_pos + 1
    }
}

Answer 3

Вероятно, не лучший подход, но он должен работать.

Определите количество комбинаций из трех чисел, которые составляют 8:

1,1,6
1,2,5
1,3,4
2,2,4
2,3,3

Чтобы найти вышесказанное, я начал с:

6,1,1 then subtracted 1 from six and added it to the next column...
5,2,1 then subtracted 1 from second column and added to next column...
5,1,2 then started again at first column...
4,2,2 carry again from second to third
4,1,3 again from first...
3,2,3 second -> third
3,1,4 

зная, что меньше половины - это 2, все комбинации должны быть найдены ... но так как список не длинный, мы могли бы также пойти до конца.

Теперь сортируйте каждый список из 3 от наибольшего к наименьшему (или наоборот) Теперь отсортируйте каждый список из 3 относительно друг друга. Скопируйте каждый уникальный список в список уникальных списков. Теперь у нас есть все комбинации, которые добавляют к 8 (думаю, пять списков).

Теперь рассмотрим список в указанном выше наборе

6,1,1 все возможные комбинации находятся по:

8 выбор 6, (так как мы выбрали шесть, остается только 2, чтобы выбрать из) 2 выбора 1, 1 выбор 1 который работает до 28 * 2 * 1 = 56, стоит знать, сколько существует возможностей, чтобы вы могли проверить.

n выберите r (выберите r элементов из n вариантов)

n C r = n! / [(н-р)! r!]

Итак, теперь у вас есть общее количество итераций для каждого компонента списка, для первого - 28 ...

Выбор 6 элементов из 8 - это то же самое, что создать список из 8 минус 2 элементов, но какие два элемента?

Хорошо, если мы удалим 1,2, то получится 3,4,5,6,7,8. Давайте рассмотрим все группы по 2 ... Начиная с 1,2, следующая будет 1,3 ... так что следующее читается столбец за столбцом.

12
13 23 
14 24 34
15 25 35 45
16 26 36 46 56
17 27 37 47 57 67
18 28 38 48 58 68 78

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

Я знаю, что это не детальный алгоритм, но я надеюсь, что вы сможете начать.

Answer 4

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

Вот реализация Python:

def combinations(source, n):
  def combinations_helper(source, subsets, p=0, nonempty=0):
    if p == len(source):
      yield subsets[:]
    elif len(source) - p == len(subsets) - nonempty:
      empty = [subset for subset in subsets if not subset]
      for subset in empty:
        subset.append(source[p])
        for combination in combinations_helper(source, subsets, p+1, nonempty+1):
          yield combination
        subset.pop()
    else:
      for subset in subsets:
        newfilled = not subset
        subset.append(source[p])
        for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled):
          yield combination
        subset.pop()

  assert len(source) >= n, "Not enough items"
  subsets = [[] for _ in xrange(n)]
  for combination in combinations_helper(source, subsets):
    yield combination

И тест:

>>> for combination in combinations(range(1, 5), 2):
...   print ', '.join(map(str, combination))
... 
[1, 2, 3], [4]
[1, 2, 4], [3]
[1, 2], [3, 4]
[1, 3, 4], [2]
[1, 3], [2, 4]
[1, 4], [2, 3]
[1], [2, 3, 4]
[2, 3, 4], [1]
[2, 3], [1, 4]
[2, 4], [1, 3]
[2], [1, 3, 4]
[3, 4], [1, 2]
[3], [1, 2, 4]
[4], [1, 2, 3]
>>> len(list(combinations(range(1, 9), 3)))
5796