group-telegram.com/compmathweekly/17
Last Update:
дайджест комментариев: разбиения на доминошки
коллеги, спасибо большое за содержательные комментарии и вообще
1.
С.Шашков сделал веб-версию перемешивания ацтекского брильянта: https://shashkovs.ru/i/Aztec.html
Нравится и как конкретно это выглядит, и вообще идея превращения таких программ в веб-страницы — особ. удобно, если хочется поделиться на кружке, докладе и т.п.
Переход от несложного питона к джаваскрипту выглядит посильным — мб попробую при случае что-то сделать и на джаваскрипте.
2.
Л.Петров обращает внимание на то, что случайное разбиение ацтекского брильянта на доминошки радикально быстрее генерировать не применяя много случайных флипов, а при помощи domino shuffling.
В качестве популярного введения — советую видео https://youtu.be/Yy7Q8IWNfHM Mathologer'а. Для тех, кто читал брошюру Е.Смирнова про ацтекские брильянты, — это примерно то же, что описанное там «расширение площадей».
3.
Р.Гусарев напоминает, что разбиения квадрата 8×8 на доминошки намного быстрее считать не в лоб, а «динамикой по профилю».
Эту идею давайте в таком виде упакую. Если считать просто разбиения прямоугольника, say, 3×N, то эти числа P(n) никакой очевидной рекурренте не удовлетворяют. Почему? Ну просто потому, что если мы выкидываем все доминошки, покрывающие последний столбец, то остается не прямоугольник, а прямоугольник с дырками в самом правом столбце. Но это значит, что если думать про тройку (P(n),Q(n),P(n-1),Q(n-1)), где Q(n) — количество разбиений прямоугольника 3×N без верхней правой клетки, P(n-1) — количество разбиений без всего правого столбца, S(n-1) — только с одной клеткой в самом правом столбце, то следующая четверка линейно выражается через предыдущую!
Реализовал это вот так (и теперь, действительно, даже разбиения прямоугольника 8×64 считаются мгновенно):
def is_good(mask,n):
# mask кодирует последовательность из n нулей и единиц
# функция проверяет, можно ли замостить нули доминошками
if mask == 0:
return n%2 == 0
if mask%4 == 0:
return is_good(mask>>2,n-2)
if mask%4 == 2:
return False
return is_good(mask>>1,n-1)
def tilings(n,m):
ext = [ [1 if mask&perp==0 and is_good(mask+perp,n) else 0
for perp in range(2**n)] for mask in range(2**n)]
# ext[mask][perp]: можно ли положить перпендикулярные
# нашему ряду доминошки, чтобы не задеть маску,
# а остаток чтобы разбился на доминошки в ряду
ans = [1 if mask==0 else 0 for mask in range(2**n)]
for _ in range(m):
newans = [0] * (2**n)
for mask in range(2**n):
for oldmask in range(2**n):
newans[mask] += ext[mask][oldmask]*ans[oldmask]
# видно, что шаг есть умножение матрицы на вектор
ans = newans
return ans[0]
print(tilings(8,64))
BY Компьютерная математика Weekly
Share with your friend now:
group-telegram.com/compmathweekly/17