Задачка: петли на решётке (оптимистично звучит, правда?)

[singalen]

Есть у меня задача. Кажется простой, но в подробности можно углупляться долго.

Подсчитать количество разных, несамопересекающихся, неизоморфных петель на квадратной решётке.
Дана длина петли N.

Для N=4 ответ - 1:
 _
|_|

Для 6 - 2:
 __
|__|
 _
| |
|_|

Для 8 - 7.
и те де.

Я пока решаю жёстко заоптимизированным перебором. Время расчёта растёт экспоненциально по N с коэффициентом 6. Но такое счастье нам не надо.

Кто придумает хотя бы идею лучшего решения - с меня пиво. Если это будет работающий код - пива будет много :)

Comments

[http://users.livejournal.com/_gert/]

слушай, или я неправильно понимаю изоморфность, или для N=6 мы имеем два варианта, получаемых простым поворотом, т.е. изоморфных, и для N=8 - три варианта. N=10 - 4. N=12 - 9.

[http://users.livejournal.com/_gert/]

да, есть еще момент зеркального отображения.

так что, плз, дай понятие неизморфности в данном контексте - наклевывается решение

[singalen]

Только сдвигом. Повороты и отражения дают другую петлю.

[singalen]

Но вопрос правильный! Я его задам постановщику задачи :)

[rioman.livejournal.com]

А чистой математикой по индукции не получается?

[singalen]

У меня не получилось. Там начинаются безумные формы петель - вогнутые и всё такое.

Есть кусочек, который я решаю динамическим программированием и мемоизацией, но в основе всё равно перебор 8(

Но если ты придумаешь, как - памятник тебе будет :)

[ln-123.livejournal.com]

А как у вас для n=8 получилось 7 петель?
Я смог придумать только 3 :(
--
| |
| |
--

---
| |
---

-
| |
| |
| |
-

Какую еще можно сделать петлю?

[singalen]

Четыре со вмятинами по углам:

 __
| _|
|_|
 __
|_ |
 |_|

и т.п.

[profuel.livejournal.com]

 -
| |_
|_ _|

[mortang.livejournal.com]

Товарищи с месть посоветовали попробовать поискать по известным результатам.
http://www.research.att.com/~njas/sequences/?q=1%2C2%2C7&sort=0&fmt=0&language=russian&go=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA

[profuel.livejournal.com]

вот это да. спасибо за ссылку, ушел читать!

[singalen]

Вау! Вот спасибо так спасибо! :)

[singalen]

Хит.
Вот оно: http://www.research.att.com/~njas/sequences/A002931
У нас есть первый призёр!

[profuel.livejournal.com]

круто, вот и узнали настоящее название задачи :)

[singalen]

Ну, я её назвал примерно так же.

[profuel.livejournal.com]

а формулу нашел?
так как я кроме данных о кол-вах для размер до 55 (*2) так и не нашел.

[singalen]

Неа. Думаю, там тот же оптимизированный перебор.

[singalen]

Новая ссылка: https://oeis.org/A002931

Вова штурмует

[singalen]

mwg: а есть какая-то индукция между N и N+2 ?
например, если нам добавляют две палочки, то мы можем в каждой из N уже уложенных палочек приделать по выпуклому П-образному прыщичку

чему в среднем равно частное между f(N) и f(N+2) ? (singalen: ~5)

mwg: или, например, так : мы генерим сначала какую-то начальную/отправную петлю, например, прямоугольник единичной высоты, а потом получаем из неё следующие петли той же длины путём некоторого количества элементарных преобразований (доказать, что разных таких преобразований конечное число и что любой контур данной длины может быть сгенерён из любого другого конечным числом таких преобразований) :>

пока что вижу два простых преобразования - вгибание-выгибание угла, и одно посложнее - загиб прямоугольной палки , длина которой >2

два посложнее - ещё разгиб уже согнутой палки :>

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

и вот ещё - покажи значения функции для чуть бОльших аргументов (>8)

вдруг аппроксимацию придумаем ? если, конечно, интересно только количество, а не набор всех форм петель для каждого N.

[ln-123.livejournal.com]

А вот это не смотрели http://otvety.google.ru/otvety/thread?tid=50d3f09ba0be1287&pli=1

[singalen]

Не думаю - во-первых требуется точно подсчитать ВСЕ варианты, во-вторых, структура графа меняется по мере построения петли.

[ln-123.livejournal.com]

Структура графа у вас как раз не меняется т.к. это всегда решетка достаточных размеров для построения самой большой петли т.е. для петли длинной 4 это будет решетка 2Х2 для петли длинной 6 , 3Х3 (или да же меньше наверное n/2 - 1 ) ну и так далее.

[singalen]

Меняется набор рёбер решётки, доступных для построения петли. Заняли вершину - всё, все прилежащие рёбра заняты.

[ln-123.livejournal.com]

Это не важно нам видь нужно кол-во петель, а не сами петли.
Я пока вижу только одну проблему мы можем посчитать кол-во петель проходящих через некую вершину, но как определить кол-во петель которые являются не изоморфными в вашей постановке и не включают данную вершину не понятно :(

[singalen]

Это важно, потому что конфигурация начала петли влияет на это самое количество возможных продолжений.
Представьте себе более длинные петли. Они бывают невыпуклыми.

По незанятому проямоугольнику M*N из угла в угол можно провести 2^M различных линий (если M<N). А по занятому - бывает, можно всего одну, или ни одной. Ну, посчитайте все петли, и разделите на количество изоморфных. В простом варианте их будет 2N.