Комбинаторика

[MadReason]

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

например:


получено 3 контура

разобрался с алгоритмом 1xN
F(ni)=F(ni-1)+ni

function F(n:byte):cardinal;
begin
if n=1 then result:=1 else
result:=f(n-1)+n;
end;

и с алгоритмом 2xN
kont:=x*f(y)+y*f(x)+1+fact(x)*fact( y);

где f() предыдущая функция и либо x, либо y должны быть равны 2

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

[Prime123]

Контуры только прямоугольной и квадратичной формы?Или любые?

[MadReason]

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

[Z1000000]

Если условия задать в виде графа, то задача формулируется:
Найти Все циклы в графе.

Вот что пишет народ в Инете.

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

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

[MadReason]

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