В следующем коде Python используется простой метод для создания случайного разбиения при каждом запуске. Он перетасовывает список из 32 целых чисел (чтобы получить случайный результат), а затем использует метод первого соответствия + обратного отслеживания, чтобы найти первое расположение, которое следует из этого перемешивания. Эффективность. Используемая здесь случайная последовательность Фишера-Йейтса является алгоритмом O (n). Поиск первого расположения в случайном порядке может быть близок к O (n) или может быть намного хуже, в зависимости от исходных чисел и случайного перемешивания, как указано ниже.
Предостережения: в идеале наличие другой случайной последовательности должно приводить к другому разделу. Но этого не может быть, потому что существует намного больше разных перемешиваний, чем разных разделов (возможно, в 10 20 раз больше перемешиваний по сравнению с разделами). Также в идеале каждый возможный раздел должен иметь одинаковую вероятность создания. Я не знаю, так ли это здесь, и даже не знаю, охватывает ли этот метод все возможные разделы. Например, вполне возможно, что некоторые разделы не могут быть созданы методом первого соответствия + обратного отслеживания.
Хотя этот метод генерирует подавляющее большинство своих решений довольно быстро - например, менее чем за миллисекунду - он иногда застревает и тратит много времени из-за конфликтов, возникающих в начале рекурсии, которые не обнаруживаются до нескольких уровней Глубже. Например, время нахождения четырех наборов из 1000 различных решений было 96 с, 166 с, 125 с и 307 с, а время нахождения наборов из 100 различных решений - 56 мс, 78 мс, 1,7 с, 5 с, 50 s.
Некоторые программные примечания: В перемешанном списке s мы сохраняем 2 mn-k вместо k. Работа с данными в виде битовых масок вместо подсчета чисел ускоряет тесты на дубликаты. Экспонент mn-k (в 2 mn-k ) позволяет сортировать массив u так, чтобы вывод был в порядке возрастания. В python # вводит комментарии. Скобки с выражением for внутри представляют «понимание списка», способ представления списка, который может быть сгенерирован с помощью оператора for. Выражение [0]*nc обозначает список или массив nc элементов, изначально все 0.
from random import randint
A = [1,2,3,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,
9,10,10,11,12,13,13,14,14,15,16,17,17] # Original number list
ns = len(A) # Number of numbers
nc = 8 # Number of cells
mc = 4 # Max cell occupancy
rc = range(nc) # [0,1,...nc-1]
mn = max(A) # Max number
s = [ 2**(mn-k) for k in A]
for i in range(ns-1,0,-1):
j = randint(0,i)
s[i], s[j] = s[j], s[i] # Do a shuffle exchange
# Create tracking arrays: n for cell count, u for used numbers.
n = [0]*nc
u = [0]*nc
def descend(level):
if level == ns:
return True
v = s[level] # The number we are trying to place
for i in rc:
if (v & u[i] == 0) and n[i] < mc:
u[i] |= v # Put v into cell i
n[i] += 1
if descend(level+1):
return True # Got solution, go up and out
else:
u[i] ^= v # Remove v from cell i
n[i] -= 1
return False # Failed at this level, so backtrack
if descend(0):
for v in sorted(u, reverse=True):
c = [ mn-k for k in range(mn+1) if v & 2**k]
print (sorted(c))
else:
print ('Failed')
Пример некоторых выходных данных:
[1, 2, 5, 9]
[3, 4, 6, 14]
[4, 5, 6, 10]
[4, 5, 7, 17]
[4, 10, 15, 16]
[5, 7, 8, 17]
[5, 7, 11, 13]
[7, 12, 13, 14]
[1, 4, 7, 13]
[2, 5, 7, 8]
[3, 4, 5, 17]
[4, 5, 6, 14]
[4, 6, 7, 9]
[5, 10, 11, 13]
[5, 10, 12, 16]
[7, 14, 15, 17]