Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 11:44
Оценка: 36 (2)
Товарищу Pushkin'у, я так полагаю, просто сны снятся про полимино. Вот ему некоторые результаты:

Степень, количество вместе с поворотами и отражениями, и количество без поворотов и отражений.

 1:      1,     1
 2:      2,     1
 3:      6,     2
 4:     19,     5
 5:     63,    12
 6:    216,    35
 7:    760,   108
 8:   2725,   369
 9:   9910,  1285
10:  36446,  4655
11: 135268, 17073


И тут же вопрос: является ли это полимино?
***
* *
***


P.S. В слове полимино на какой слог ударение?
Re: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 11:52
Оценка:
Здравствуйте, RS, Вы писали:

RS>Товарищу Pushkin'у, я так полагаю, просто сны снятся про полимино. Вот ему некоторые результаты:



Я тоже было начал, но не успел, там до фига работы, если хочешь серьёзной цифры достигнуть.
Обязаюсь на трёх ближайших выходных тоже что-нить выдать.
Гей, программеры, не всё вам за мимозой бегать, подсоединяйтесь !

RS> 7: 760, 108


У Гарднера 105.
Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.
ххх
х х
хх


RS>И тут же вопрос: является ли это полимино?

RS>
RS>***
RS>* *
RS>***
RS>


Думаю, да. Зачем искусственно усложнять себе жизнь.

RS>P.S. В слове полимино на какой слог ударение?


Логично как в домино — на последний.
Re[2]: <3^N
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 11:56
Оценка:
P>Здравствуйте, RS, Вы писали:

Кстати, я получил теоретический результат.

Для больших N число полимино растет как k^N, где 2<k<3
Re[2]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 12:03
Оценка:
Здравствуйте, Pushkin, Вы писали:

Вопрос то про полимино встал, когда нужно было придумать способ сгенерить все лабиринты из N клеток. Можно сделать это так:

Берем каждую полимино из N клеток, каждую клетку рассматриваем как взвешенный неориентированный граф из четырех вершин и четырех ребер, у каждого ребра вес равен единице (граф в виде квадрата, думаю, это понятно). Объединяем графы каждой клетки полимино по следующему правилу:
множество вершин — объединение множеств вершин графов каждой клетки,
множество ребер — объединение множеств ребер графов каждой клетки,
вес ребра — сумма весов этого ребра в каждом графе клеток полимино.

Тогда ребра с весом 1 — граница лабиринта (стопудовая стенка),
ребра с весом 2 — стенка может быть, может не быть. Вот это и надо перебирать, проверяя для каждого варианта доступность всех клеток.
Если ребро имеет вес, меньший единицы или больший двух, напиши жалобное письмо Б.Гейтсу на хинди или китайском
Re[2]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 12:39
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>У Гарднера 105.

P>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

А кто это? И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 12:45
Оценка:
Здравствуйте, RS, Вы писали:

P>>У Гарднера 105.

P>>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.
RS>А кто это? И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)

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

Кстати, сколько байт нужно твоей софтине, чтобы хранить все 108 ?
Re[4]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 13:00
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Кстати, сколько байт нужно твоей софтине, чтобы хранить все 108 ?


Во первых, софтин две. Одна генерит и пишет в compound file storage (StgCreateDocfile). И вот ей не хватило памяти (320 Мб) для 13-ой степени. Начинала по-черному свопиться, и я ее убил . А вторая открывает сгенеренный файл и рисует полимино, сгруппированные по 1-8 штук (повороты и отражения) на каждой отдельной emf. Эта софтина загнулась на 12-й степени, когда писала ~60000-ый файл.
Ну а во-вторых, чтобы просто хранить все 108, ей надо 760*7*2 байт, плюс издержки std::set. Группировка повернутых/отраженных производится при сохранении.
Re[5]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 13:24
Оценка:
Здравствуйте, RS, Вы писали:

RS>Во первых, софтин две. Одна генерит и пишет в compound file storage (StgCreateDocfile). И вот ей не хватило памяти (320 Мб) для 13-ой степени. Начинала по-черному свопиться, и я ее убил

RS>Ну а во-вторых, чтобы просто хранить все 108, ей надо 760*7*2 байт,

Многовато.
Думаю, это центральный вопрос всей задачи.
Re[3]: <5^N :)
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 06:49
Оценка: 6 (1)
Здравствуйте, Pushkin, Вы писали:

P>Кстати, я получил теоретический результат.

P>Для больших N число полимино растет как k^N, где 2<k<3

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

2<k<5

С точки зрения математики результат собственно не изменился.
Сам факт степенного роста замечательно подтверждился результатами RS.
Экстраполировав отношения величин в соседних строчках, имеем

k ~ 4
Re[2]: Количество полимино
От: MichaelP  
Дата: 06.03.03 06:50
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, RS, Вы писали:



RS>> 7: 760, 108


P>У Гарднера 105.

P>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

У RS все данные правильные см. здесь

А вот формулы Puskin-а по оценке количества полимино расходятся с мировой научной мыслью

Как выглядят полимино вплоть до 8-го порядка можно посмотреть здесь.
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 07:01
Оценка:
Здравствуйте, RS, Вы писали:

RS>Здравствуйте, Pushkin, Вы писали:


P>>У Гарднера 105.

P>>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

RS>А кто это?


Вчера не заметил этого просто неприличного на данном форуме вопроса.
Мартин Гарднер один из самых известных, по крайней мере у нас, "заниматетьных математиков". Он долгое время вёл колонку в уважаемом Scientific American и написал уйму книжек на эту тему. Совсем недавно здесь переиздали три, по-моему, штуки. Очень занимательное чтение, почти детектив.

Кстати, у него есть и собственные научные успехи. Например, он был один из тех, кто научился разрезать квадрат на неповторяющиеся квадраты. (То, что это сильно нетривиальная задача, видно хотя бы из того, что сделали её только во второй половине 20 века, и не потому что не хотели).

RS>И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)


Каюсь, память подвела. Вчера посмотрел — действительно 108, включая одну дырявую. Так что вплоть до N=7 твои результаты можно считать верными. Весьма вероятно, что и дальше тоже.
Re[4]: Количество полимино
От: mrhru Россия  
Дата: 06.03.03 07:16
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>>>У Гарднера 105.


RS>>А кто это?


P>Вчера не заметил этого просто неприличного на данном форуме вопроса.


и так:

P>Мартин Гарднер один из самых известных, по крайней мере у нас, "заниматетьных математиков". Он долгое время вёл колонку в уважаемом Scientific American и написал уйму книжек на эту тему. Совсем недавно здесь переиздали три, по-моему, штуки. Очень занимательное чтение, почти детектив.




У меня дома, издания выпуска 196.. года и если не ошибаюсь, их периодически переиздавали раз в десятилетие.
Евгений
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 07:22
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>У RS все данные правильные см. здесь

MP>А вот формулы Puskin-а по оценке количества полимино расходятся с мировой научной мыслью

А клёво я успел поправиться за минутту до того, как ты меня вывел на чистую воду
Хорошая ссылка, спасибо. На том же самом сайте, золотая жила однако
Выходит у меня всё правильно было, только границы для k можно ещё сжать.
Я кстати удивлён, что так широко они продолжают стоять.
У меня была иллюзия, что только лень не даёт мне получить ТОЧНОЕ значение для k.
Там надо перебирать чёртову прорву вариантов, но всё же вроде как конечное число.
Попробую поколдовать ещё, вдруг удастся двинуть вперёд мировую научную мысль

PS
Я так и не понял, для какого максимального N получено F(N)

PPS
А вообще-то ты нам конкурс тут не порть!
Когда ответы известны, глупо как-то напрягаться...
Re[4]: Количество полимино
От: MichaelP  
Дата: 06.03.03 07:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Я так и не понял, для какого максимального N получено F(N)


До 28. Вторая таблица содержит непроверенные данные.
Re: Я дошёл до N=20
От: Pushkin Россия www.linkbit.com
Дата: 11.03.03 08:37
Оценка: 60 (4)
Йессс, я сделал это!
С самого начала поставил себе этот рубеж как предел мечтаний,
и вот наконец после 6 часов раздумий мой Celeron 1300 выдал строку
N=20: 2870671950


Именно столько уникальных полимино 20-го порядка существует с точностью до отражений.
Кто пытался что-то колдовать на эту тему, поймёт, что дойти до N=20 не просто.
Дело в том, что число позиций нарастает примерно вчетверо с каждым следующим N.
Случай N=12, на котором засвопилась прога уважаемого RS, у меня считается менее секунды.
С другой стороны максимально известный результат N=28 потребует 50 лет моего счёта,
так что явно есть куда расти

Помимо итогового результата перечислю ещё несколько вкусностей своего алгоритма.
(Могу я доставить себе удовольствие после двухдневного трещания мозгами? )

— Только проц! Совсем не нужно памяти (кроме нескольких килобайт "на текущие нужды") На самом деле, если хранить уже найденные полимино, то даже при нереальной упаковке каждого из них в 1 байт суммарный размер достигнет гигабайт — придётся с диском работать, и конечно не закончить в разумные времена.

Линейная зависимость от окончательного числа вариантов. Иными словами, прога выдаёт сто с чем-то тысяч уникальных полимино в секунду, а уж сколько их окажется всего — это не от неё зависит. (На самом деле производительность чуть падает, что связано с увеличением каждой полимино, так что правильнее говорить, что прога выдаёт два с чем-то миллиона клеток в секунду)

Прямой счёт нужного N без подсчёта всех предыдущих.

Неиспользование стандартных библиотек - всё своё ношу с собой.

— Вполне себе коротенький текст - 3 функции, 3 страницы.

— Алгоритм явно можно ещё ускорить в разы, а то и на порядки.

Теперь вкратце кому интересно, как оно работает.
(Для тех, кто лучше читает прямо на Си, внизу весь код.
Его также можно откомпилить и поиграться.)

Основной вопрос — как кодировать одну конфигурацию.
Я искал кратчайшую кодировку для хранения,
а найдя, построил на ней алгоритм вовсе без хранения.
Итак, кодировать одно полимино порядка N будем массивом из N-1 чисел.

Каждое полимино имеет верхнюю строчку. А в ней есть самая левая клетка.
Это старт — поставим там первую клетку полимино.
Все верхние строчки и левую часть этой сразу замажем (запретим).
Из старта можно выйти всего двумя возможностями — вправо и вниз.
Либо полимино для постановки следующей клетки использует первую же возможность,
либо пропускает несколько возможностей.
Число пропущенных возможностей при постановки n+1 клетки и есть n-й элемент массива.

Каждая вновь поставленная клетка замазывает поле и ставит себя в очередь.
Когда до неё дойдут, то она родит 1,2, или 3 (но не больше) возможностей развития,
которые опять же могут быть использованы или пропущены.
Таким образом мы волновым алгоритмом получаем всё полимино по массиву.
Замечательно, что полимино однозначно кодируются и декодируются.

Но не все массивы могут быть декодированы.
Если в нём есть слишком большие числа, особенно в начале,
то это означает требование пропустить много возможностей выхода,
что грозит обрубанием полимино и недостижением проектной величины.
Поэтому мы имеем что-то вроде позиционной системы с N-1 позицией,
вот только основание не константа — каждый раз надо проверять отдельно,
можно ли сейчас увеличить вот эту цифру, раскодируется ли последовательность.

Алгоритм перебора выглядит очень похоже на алгоритм перебора всех 19-значных чисел.
Причём из-за отмеченной выше однозначности мы встретим все полимино и ровно по 1 разу.

Последний вопрос — как отбрасывать отражения.
Очень просто! Надо лишь ввести какое-либо правило, говорящее,
"главное" это полимино или нет среди всех своих отражений.
Например, взять полимино, отразить его 7 раз и выбрать "минимальный" массив (memcmp).
Но есть и гораздо более быстрые простые способы

Ну и наконец, собственно код.
Это не оконнчательный вариант, он в 3 раза медленнее, зато в 5 раз прозрачнее.
Если вдруг найдётся желающий это ускорить, буду очень рад. (А это точно можно —
основная функция Decode() всё время раскрывает почти одно и то же и каждый раз сначала. )


// Polymino.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>

//максимальный порядок полимино
#define N 20

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Decode()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка

int x1,x2,y1,y2; //границы полимино, лежащего в board[][]

//основная функция
//декодирует в board последовательность
//лежащую в массиве pack[n]
//останавливается в конце массива
//или при невозможности двигаться дальше
//в последнем случае возвращает false
//верхняя строка в результирующем board пустая
//вторая сверху строка начинается с клетки N-2
bool Decode(int pack[],int n)
{    
    static int fifo_x[N-1];
    static int fifo_y[N-1];
    static int fifo_tail=0;
    static int fifo_head=0;

    memset(board, 0,sizeof(board));               //заполняем всё туманом
    memset(board,-1,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами

    //поставим первую клетку
    fifo_x[0]=N-2;
    fifo_y[0]=1;
    fifo_tail=1;
    fifo_head=0;
    board[fifo_y[0]][fifo_x[0]]=1; 
    x1=x2=fifo_x[0];
    y1=y2=fifo_y[0];

    //основной цикл декодирования
    int pos=0,count=0;
    while(fifo_tail>fifo_head)
    {
        for(int d=0;d<4;d++)
        {
            int y=fifo_y[fifo_head]+dy[d];
            int x=fifo_x[fifo_head]+dx[d];
                
            if(board[y][x]==0)              //в тумане
            {
                if(count==pack[pos])
                {
                    board[y][x]=1;  //поставили
                
                    //поправим границы
                    if(y>y2)    y2=y;
                    else if(x<x1)    x1=x;
                    else if(x>x2)    x2=x;
                    
                    //переходим к следующему элементу pack
                    if(++pos==n)
                        return true; //если конец - уходим
                    count=0;

                    //помещаем поставленную клетку в очередь 
                    fifo_y[fifo_tail]=y;
                    fifo_x[fifo_tail]=x;
                    fifo_tail++;
                }
                else
                {
                    count++;        //считаем отказы
                    board[y][x]=-1; //помечаем отказ
                }
            }
        }

        fifo_head++; //убираем обработанную клетку из очереди
    }

    return false;
}


//возвращает true если в board находится "правильно" повёрнутая конфигурация 
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно - 
//среди всех 8 отражений должно быть ровно 1 правильное
bool IsMainBoard()
{
    int ny=y2-y1, nx=x2-x1;
    if(nx<ny)
        return false;

    int reflect_impossible[2][2][2]={0};//[x<->y][y<->ny-y][x<->nx-x]
    
    for(int y=0;y<=ny;y++)
    for(int x=0;x<=nx;x++)
    {
        if(1==board[y1+y][x1+x])
        {
            if(1!=board[y1+y   ][x1+nx-x])   reflect_impossible[0][0][1] =1;
            if(1!=board[y1+ny-y][x1+x   ])   reflect_impossible[0][1][0] =1;
            if(1!=board[y1+ny-y][x1+nx-x])   reflect_impossible[0][1][1] =1; if(nx==ny) {
            if(1!=board[y1+x   ][x1+y   ])   reflect_impossible[1][0][0] =1;
            if(1!=board[y1+x   ][x1+nx-y])   reflect_impossible[1][0][1] =1;
            if(1!=board[y1+nx-x][x1+y   ])   reflect_impossible[1][1][0] =1;
            if(1!=board[y1+nx-x][x1+nx-y])   reflect_impossible[1][1][1] =1;            }
        }
        else if(   1==board[y1+y   ][x1+nx-x] && reflect_impossible[0][0][1]==0 ||
               1==board[y1+ny-y][x1+x   ] && reflect_impossible[0][1][0]==0 ||
               1==board[y1+ny-y][x1+nx-x] && reflect_impossible[0][1][1]==0 || nx==ny &&(
               1==board[y1+x   ][x1+y   ] && reflect_impossible[1][0][0]==0 ||
               1==board[y1+x   ][x1+nx-y] && reflect_impossible[1][0][1]==0 ||
               1==board[y1+nx-x][x1+y   ] && reflect_impossible[1][1][0]==0 ||
               1==board[y1+nx-x][x1+nx-y] && reflect_impossible[1][1][1]==0 )           )
        {
            return false;
        }
    }

    return true; 
}


//подсчитывает все полимино порядка n
void Enum(int n, unsigned int& countAll, unsigned int& countMain)
{
    countAll=countMain=0;
    if(n<2)
    {
        if(n==1)
            countAll++,countMain++;
        return;
    }

    int* pack=new int[n-1];
    memset(pack,0,(n-1)*sizeof(int));

    while(1)
    {
        if(Decode(pack,n-1))
        {
            countAll++;          //считает все полимино
            if(IsMainBoard())    
                countMain++; //считает с точностью до отражений
            pack[n-2]++;
        }
        else
        {
            for(int i=n-2;pack[i]==0;i--)
            {
            }    
            if(i==0)
            {
                delete[] pack;  
                return;
            }
            pack[i]=0;
            pack[i-1]++;
        }
    }
}


int main(int argc, char* argv[])
{
    while(1)
    {
        char s[80];
        gets(s);

        if(s[0]=='?' || strlen(s)==0 || strlen(s)>N-1) 
        {
            if(strlen(s)>N-1 || atoi(s+1)>N)
            {
                printf("To work with such big polyminoes change \"#define N ...\" line in code.\n\n");
                continue;
            }
            if(atoi(s+1)<=0)
            {
                printf("Examples:\nEnter ?10 to count polyminos with order 10.\nEnter sequence 0102 to decode it.\n\n");
                continue;
            }
            
            //считает все полимино
            unsigned int countAll,countMain,n=atoi(s+1);
            Enum(n,countAll,countMain);
            printf("N=%u Total=%u Main=%u\n\n",n,countAll,countMain);
        }
        else
        {
            int pack[N-1];
            int n=strlen(s);
            for(int i=0;i<n;i++) //читает набитую последовательность
                pack[i]=s[i]-'0';            

            bool res1=Decode(pack,n),res2=IsMainBoard();
            printf("%s %s\n\n", res1?"OK":"Fails",res1&&res2?" Main":"");
            //говорит, можно ли её декодировать и "правильная" ли она
            
            //затем выводит саму полимино - результат декодирования
            for(int y=0;y<=y2-y1;y++)
            {
                for(int x=0;x<=x2-x1;x++)
                    printf(board[y1+y][x1+x]==1? "\1":" ");
                printf("\n");
            }

            printf("\n\n");
        }
    }

    while(getchar());
    return 0;
}
Re[2]: Re[2]: Я дошёл до N=20
От: mrhru Россия  
Дата: 11.03.03 10:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Йессс, я сделал это!


Йессс, ты сделал это!

Громадьё свершений не позволяют даже в полной мере сразу оценить это!
Евгений
Re[4]: <5^N :)
От: RS Земля ICQ: 148844272
Дата: 11.03.03 10:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>2<k<5


А где выкладки? Очень интересно.
Re[2]: Я дошёл до N=20
От: RS Земля ICQ: 148844272
Дата: 11.03.03 10:12
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Йессс, я сделал это!


Проклятье! А я только до N=15
Re[5]: <5^N :)
От: Pushkin Россия www.linkbit.com
Дата: 11.03.03 12:42
Оценка:
Здравствуйте, RS, Вы писали:

P> 2<k<5

RS>А где выкладки? Очень интересно.

Выкладки, к сожалению, не слишком строги.
Более того, чем дальше, тем менее очевидными они мне кажутся.
Но идея базируется на представлении, предложенном в базовой статье
Автор: Pushkin
Дата: 11.03.03


Любое полимино порядка N получается волновым алгоритмом из массива N-1 чисел.
Поначалу мне казалось, что в этом массиве могут быть только числа 0,1,2.
Действительно, раз мы вошли в клетку через одну стенку, то возможностей для выхода всего 3.
Если учесть ещё максимум 2 упущенных выхода из предпоследней клетки, получается, что всяких цепочек никак не больше, чем 5^N.

Но к сожалению, для разветвлённых полимино легко придумать допустимую последовательность со сколь угодно большими числами. Для этого надо устраивать несколько путей и потом одновременно из зарезать, т.е. устроить "миг упущенных возможностей".

Единственная надежда, что таких специальных полимино с большим количеством одновременно обрубающихся концов статистически мало. Большинство имеет 1-2-3 конца (чтобы не было недоразумений, концом я называю те клетки, которые остались в очереди к моменту исчерпания всех N клеток полимино).

Короче неясно всё...
Re[6]: О базовой статье
От: RS Земля ICQ: 148844272
Дата: 11.03.03 12:51
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Но идея базируется на представлении, предложенном в базовой статье
Автор: Pushkin
Дата: 11.03.03


Не понял я твою базовую статью, да и ручку дома забыл, порисовать нечем
Было бы неплохо, если бы ты ее объяснил поподробнее, не упуская ничего из виду, давая определения своим терминам.

P.S. Я за выходные (вернее ночь с пятницы на субботу) немного усовершенствовал старый алгоритм, но так и не придумал никакого, которому бы не нужна была память (в таких количествах).
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.