Pushkin, ты вроде большой спец по полимино..
От: Linuxoid  
Дата: 02.04.03 12:56
Оценка:
Спрошу еще здесь на всякий случай — в "Алгоритмах" никто ничего толкового не сказал.
Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).
Re: Pushkin, ты вроде большой спец по полимино..
От: Кодт Россия  
Дата: 02.04.03 13:39
Оценка:
Здравствуйте, Linuxoid, Вы писали:

L>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).


Сначала определим, сколько и каких вариантов бывает вообще.

Повороты и отражения совершаются с помощью матрицы преобразования координат. M=((x1,y1),(x2,y2)).

Сколько таких матриц всего?
Z = ((+/-1, 0), (0, +/-1)) -- отражения
R = ((0, +/-1), (+/-1, 0)) -- поворот на 90 + отражения
итого 8 вариантов.

Для фигуры определим ее размеры по X и по Y.
Если X != Y --- то варианты R отпадают, это очевидно.

Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино).
Получаем вектор из 8 (или 4) булевских значений.

Поэлементная конъюнкция векторов для всех точек полимино покажет, какие варианты совпали с оригиналом, т.е. где есть симметрия.
Теперь считаем 8 — число симметрий.
Это и будет число вариантов.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Pushkin, ты вроде большой спец по полимино..
От: Кодт Россия  
Дата: 02.04.03 14:00
Оценка: 10 (1)
И, естественно, программу можно оптимизировать.
Вот как это выглядит на Ц++

class Figure
{
public:
  int w() const;
  int h() const;

  bool at(int x, int y) const;
};

enum Transforms
{
  t_h = 1 << 0, // flip horizontal
  t_v = 1 << 1, // flip vertical
  t_c = 1 << 2, // flip central (h+v) = turn 180
  t_r = 1 << 3, // turn right
  t_l = 1 << 4, // turn left
  t_t = 1 << 5, // transpose \ = turn right + flip hor
  t_d = 1 << 6, // transpose / = turn right + flip ver

  t_flips = 0x7,
  t_turns = 0x78,
  t_all = 0x7F,
  t_none = 0,
};

unsigned examine(const Figure& fig) // return combination of Transforms
{
  int w = fig.w(), h = fig.h();
  unsigned t = (w == h) ? t_all : t_flips;
  
  int x, y;
  for(x = 0; x < w; ++x) for(y = 0; y < h; ++y)
  {
    if(!fig.at(x,y)) continue; // check only present cells

    if((t & t_h) && !fig.at(w-x,  y)) t &= ~t_h;
    if((t & t_v) && !fig.at(  x,h-y)) t &= ~t_v;
    if((t & t_c) && !fig.at(w-x,h-y)) t &= ~t_c;
    if((t & t_r) && !fig.at(w-y,  x)) t &= ~t_r;
    if((t & t_l) && !fig.at(  y,h-x)) t &= ~t_l;
    if((t & t_t) && !fig.at(  y,  x)) t &= ~t_t;
    if((t & t_d) && !fig.at(w-y,h-x)) t &= ~t_d;

    if(t == 0) return 0;
  }

  return t;
}
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Pushkin, ты вроде большой спец по полимино..
От: Linuxoid  
Дата: 02.04.03 14:09
Оценка:
Здравствуйте, Кодт, Вы писали:

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


L>>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).


[]

К>Поэлементная конъюнкция векторов для всех точек полимино покажет, какие варианты совпали с оригиналом, т.е. где есть симметрия.

К>Теперь считаем 8 — число симметрий.
К>Это и будет число вариантов.

Я не совсем понял ответ (вернее, совсем не понял ), но по-моему, вопрос был немного о другом.
Например, для квадрата число видов — 1, для прямой полоски — 2, и т.д.
Re: Pushkin, ты вроде большой спец по полимино..
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 14:13
Оценка:
Здравствуйте, Linuxoid, Вы писали:

L>Спрошу еще здесь на всякий случай — в "Алгоритмах" никто ничего толкового не сказал.

L>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).

Переделка функции IsMainBoard() отсюда
Автор: Pushkin
Дата: 14.03.03
даёт.

Нижеследующий код неверен. Правильный вариант приведён в одном из постов дальше.

char board[NY][NX];
// полимино 
// 1 - клетка заполнена
// 0 - клетка не заполнена

//возвращает число разных видов полимино, лежащего в board
int PolyminoReflections()
{
    //сначала найдём границы и центр тяжести - это может быть уже и готовым
    int x1,x2,y1,y2; //границы полимино, лежащего в board[][]
    int x0=0,y0=0;   //суммы всех x и y для вычисления среднего
    int count=0;
    for(int y=0;y<NY;y++)
    for(int x=0;x<NX;x++)
    if(board[y][x])
    {
        x0+=x;
        y0+=y;
        
        if(count++==0)
        {
            x1=x2=x;
            y1=y2=y;
        }
        else
        {
            if(x<x1) x1=x;
            if(x>x2) x2=x;
            if(y<y1) y1=y;
            if(y>y2) y2=y;
        }
    }        
    if(count==0)
        return 0;
        
    //найдём положение центра тяжести относительно границ полимино
    int bx=x0*2-(x1+x2)*count;
    int by=y0*2-(y1+y2)*count;

    if(bx==0 && by<0)
    {
        //проверка, а не симметричная ли фигура относительно вертикали
        int ny=y2-y1, nx=x2-x1;
        for(int y=0;y<=ny;y++)
        for(int x=0;x<(nx+1)/2;x++)
        if(board[y1+y][x1+x] != board[y1+y][x1+nx-x])
            return 8; //несимметрична
        return 4;    //симметрична
    }

    else if(bx<0 && by==bx)
    {
        //проверка, а не симметричная ли фигура относительно диагонали
        int ny=y2-y1, nx=x2-x1;
        if(nx!=ny)
            return 8;

        for(int y=0;y<=ny;y++)
        for(int x=0;x<y;x++)
        if(board[y1+y][x1+x] != board[y1+x][x1+y])
            return 8; //несимметрична
        return 4;    //симметрична
    }

    //основная проверка - когда центр тяжести попадает в центр объемлющего прямоугольника
    //если скорость не важна, можно выкинуть вообще мороку с центром тяжести и оставить только это
    else if(bx==0 && by==0) 
    {
        int reflect_impossible[2][2][2]={0};//[x<->y][y<->ny-y][x<->nx-x]

        int ny=y2-y1, nx=x2-x1;
        if(nx!=ny)
        {
            reflect_impossible[1][0][0] =1;
            reflect_impossible[1][0][1] =1;
            reflect_impossible[1][1][0] =1;
            reflect_impossible[1][1][1] =1;                
        }
        
        for(int y=0;y<=ny;y++)
        for(int x=0;x<=nx;x++)
        if(board[y1+y][x1+x])
        {
            if(!board[y1+y   ][x1+nx-x]) reflect_impossible[0][0][1] =1;
            if(!board[y1+ny-y][x1+x   ]) reflect_impossible[0][1][0] =1;
            if(!board[y1+ny-y][x1+nx-x]) reflect_impossible[0][1][1] =1; if(nx==ny) {
            if(!board[y1+x   ][x1+y   ]) reflect_impossible[1][0][0] =1;
            if(!board[y1+x   ][x1+nx-y]) reflect_impossible[1][0][1] =1;
            if(!board[y1+nx-x][x1+y   ]) reflect_impossible[1][1][0] =1;
            if(!board[y1+nx-x][x1+nx-y]) reflect_impossible[1][1][1] =1;            }
        }

        //сколько симметрий осталось допустимыми
        count=0;
        for(int a=0;a<2;a++)
        for(int b=0;b<2;b++)
        for(int c=0;c<2;c++)
        if(!reflect_impossible[a][b][c])
            count++;

        return  count==0? 8: 
                count==1? 4:
                count==2? 4:
                count==4? 2:
                count==8? 1:0;//0 невозможен
    }

    //почти всегда доходим до этого места, особенно для больших полимино
    return 8; 
}
Re[2]: Pushkin, ты вроде большой спец по полимино..
От: Linuxoid  
Дата: 02.04.03 14:16
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


P>Переделка функции IsMainBoard() отсюда
Автор: Pushkin
Дата: 14.03.03
даёт.


[]

Спасибо. Попробую дома вникнуть.
Re[2]: Pushkin, ты вроде большой спец по полимино..
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 14:17
Оценка:
Здравствуйте, Кодт, Вы писали:


К>Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино).

К>Получаем вектор из 8 (или 4) булевских значений.



К>Теперь считаем 8 — число симметрий.

К>Это и будет число вариантов.

Например, если число симметрий равно 8 (квадрат), вариантов 0
Re[3]: Pushkin, ты вроде большой спец по полимино..
От: Кодт Россия  
Дата: 02.04.03 14:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

К>>Теперь считаем 8 — число симметрий.

К>>Это и будет число вариантов.

P>Например, если число симметрий равно 8 (квадрат), вариантов 0


У меня в школе было от 2 до 5 по арифметике
"Математичка обурела: сказала, что я нихрена не знаю, и поставила в дневник какую-то цифру".

8 симметрий, включая самого себя
Естественно, что сам с собой — всегда совпадет.

Ну, в общем, под вечер туплю, формула не выводится... где-то 7-8.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Pushkin, ты вроде большой спец по полимино..
От: Linuxoid  
Дата: 02.04.03 14:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


P>

К>>Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино).
К>>Получаем вектор из 8 (или 4) булевских значений.

P>


К>>Теперь считаем 8 — число симметрий.

К>>Это и будет число вариантов.

P>Например, если число симметрий равно 8 (квадрат), вариантов 0

Наверное, все-таки 8 / число симметрий.
Re[2]: Pushkin, ты вроде большой спец по полимино..
От: Кодт Россия  
Дата: 02.04.03 14:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

P> //сначала найдём границы и центр тяжести — это может быть уже и готовым


Центр тяжести для подсчета отражений не нужен: достаточно только найти границы по X,Y.

А вот для тетриса — центр тяжести пригодится
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[4]: Pushkin, ты вроде большой спец по полимино..
От: Linuxoid  
Дата: 02.04.03 14:30
Оценка:
Здравствуйте, Кодт, Вы писали:

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


К>>>Теперь считаем 8 — число симметрий.

К>>>Это и будет число вариантов.

P>>Например, если число симметрий равно 8 (квадрат), вариантов 0


Сори, не въехал
посчитал минус за тире
Re[4]: Pushkin, ты вроде большой спец по полимино..
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 14:50
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Ну, в общем, под вечер туплю, формула не выводится... где-то 7-8.


Я тупой, я ифами написал
Re[3]: Pushkin, ты вроде большой спец по полимино..
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 14:57
Оценка: 12 (1)
Здравствуйте, Кодт, Вы писали:

К>Центр тяжести для подсчета отражений не нужен: достаточно только найти границы по X,Y.

К>А вот для тетриса — центр тяжести пригодится

Подсчёт центра тяжести существенно ускоряет подсчёт симметрий для больших полимино, т.к. во всех случаях, кроме британского флага сразу даёт ответ "нет симметрий" и таким образом вместо O(N^2) переводит задачу в O(N). Конечно остаётся O(N^2) для подсчёта самого центра, но оно и так возникает при подсчёте границ. А может оно всё и уже где-то лежит. Короче для 20х20 это реально ускоряет в разы, проверено.
Re[3]: Pushkin, ты вроде большой спец по полимино..
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 15:24
Оценка:
Здравствуйте, Кодт, Вы писали:

К>И, естественно, программу можно оптимизировать.

К>Вот как это выглядит на Ц++

В точности то же, что и у меня...
Но изящней...
Но не доведено до конца...
И без подсчёта центра тяжести, что существенно замедляет...
Что делает ненужным колдовство с битами...
Re[3]: Pushkin, ты вроде большой спец по полимино..
От: Кодт Россия  
Дата: 02.04.03 15:26
Оценка:
Здравствуйте, Linuxoid, Вы писали:

L>Я не совсем понял ответ (вернее, совсем не понял ), но по-моему, вопрос был немного о другом.

L>Например, для квадрата число видов — 1, для прямой полоски — 2, и т.д.

А, Семен Семеныч!!! Конечно же, повернутые виды тоже могут быть симметричны...
Чешем репу...

1. Определим, какие симметрии присутствуют: H, V, C(central), R(rotation), T(diagonal\), D(diagonal/).
(Эти признаки не ортогональны! H+V == C, R => C, и т.п.)

2. Уникальные варианты
    оси      характерная
 симметрии     фигура       разные отражения  совпадения
h v c r t d                 0 h v c r l t d
- - - - - -      R       8  + + + + + + + +
+ - - - - -      T       4  +     + + +       h=0, v=c, t=l, d=r
- + - - - -      K       4  +     + + +
- - + - - -      Z       4  + + +   +         c=0, l=r, t=r+h, d=r+h
+ + + - - -      H       2  +       +         h=v=c=0, l=t=d=r
- - - - + -    угол Г    4  + + + +           r=v, l=h, t=0, d=c
- - - - - +    угол L    4  + + + +           r=h, l=v, t=c, d=0
- - + + - -   свастика   2  + +
- - + - + -      \       2  + +
- - + - - +      /       2  + +
+ + + + + +      +       1  +

Как это в одну формулу вывести — надо подумать.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re: Новый правильный код
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 05:34
Оценка: 3 (1)
Здравствуйте, Linuxoid, Вы писали:

Пожалуйста, не читайте мой вчерашний код, я бредил
Ниже приведён верный вариант.

1) Я его проверил. Как по картинкам, так и встроив в подсчёт полимино (там гигантские числа, они совпали, это почти гарантия).

2) Перевёл всё на битовое представление Кодта. Помимо общей симпатичности, это даёт удобный способ экстренного выхода.

3) Продолжаю настаивать на крайней полезности простого трюка с центром тяжести. Специальное исследование показало, что для полимино площадью 15 это даёт ускорение подсчёта симметрий в 5 раз. Для больших — больше. Кстати, идея в своё время исходила от MichaelP.

4) Использовал гениальную формулу автора 8/r. Смешно, что нам с Кодтом она в голову сразу не пришла

Итого: "У тебя своего ничего нет. Ты голодранец " (c) Брагинский-Рязанов

char board[NY][NX];
// полимино 
// 1 - клетка заполнена
// 0 - клетка не заполнена

//возвращает число разных видов полимино, лежащего в board
int PolyminoReflections()
{
    //сначала найдём границы и центр тяжести - это может быть уже и готовым
    int x1,x2,y1,y2; //границы полимино, лежащего в board[][]
    int x0=0,y0=0;   //суммы всех x и y для вычисления среднего
    int count=0;
    for(int y=0;y<NY;y++)
    {
        for(int x=0;x<NX;x++)
        if(board[y][x])
        {
            x0+=x;
            y0+=y;
        
            if(count++==0)
            {
                x1=x2=x;
                y1=y2=y;
            }
            else
            {
                if(x<x1) x1=x;
                if(x>x2) x2=x;
                if(y<y1) y1=y;
                if(y>y2) y2=y;
            }
        }

        if(count>0 && y2<y)
             break; //считаем, что полимино связное
    }        
    if(count==0)
        return 0;
        
    //найдём положение центра тяжести относительно границ полимино
    int bx=x0*2-(x1+x2)*k;
    int by=y0*2-(y1+y2)*k;

    //bitset { dyx dy dx d yx y x 1 }
    //в каждом бите can_reflect разрешение соответствующей симметрии для фигуры
    //предполагаем лучшее - изначально всё разрешили, будем постепенно убивать
    unsigned char can_reflect=  
        bx==0 && by==0  ? 0xff: 
        bx==0           ? 0x3:
        by==0           ? 0x5:
        bx==by          ? 0x11:
        bx==-by         ? 0x81:1; 
    
    //центр тяжести НЕ на британском флаге    
    if(can_reflect==1)         
        return 8;
    
    int ny=y2-y1, nx=x2-x1;
        
    if(nx!=ny)
        can_reflect&=0xf; //запрет отражений от диагонали

    if(can_reflect==1)         
        return 8;

    //приступим к настоящей работе
    for(    y=0;y<=ny;y++)
    for(int x=0;x<=nx;x++)
    if(board[y1+y][x1+x])
    {
        if(!board[y1+y   ][x1+nx-x]) can_reflect&=~0x2;
        if(!board[y1+ny-y][x1+x   ]) can_reflect&=~0x4;
        if(!board[y1+ny-y][x1+nx-x]) can_reflect&=~0x8;  if(nx==ny) {
        if(!board[y1+x   ][x1+y   ]) can_reflect&=~0x10;    
        if(!board[y1+nx-x][x1+y   ]) can_reflect&=~0x20;    
        if(!board[y1+x   ][x1+ny-y]) can_reflect&=~0x40;
        if(!board[y1+nx-x][x1+nx-y]) can_reflect&=~0x80;            }

        if(can_reflect==1)
            return 8; //совсем несимметричная, дальше нечего проверять
    }        
        
    for(int r=0;can_reflect;can_reflect>>=1)
        if(can_reflect&1) r++;

    return 8/r;
}
Re[2]: Новый правильный код
От: Кодт Россия  
Дата: 03.04.03 08:25
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>4) Использовал гениальную формулу автора 8/r. Смешно, что нам с Кодтом она в голову сразу не пришла


Да... слишком быстро я отказался от своего же изобретения... А с осями симметрии (http://www.rsdn.ru/Forum/Message.aspx?mid=231431&amp;only=1
Автор: Кодт
Дата: 02.04.03
) эта формула уже не работает.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.