Спрошу еще здесь на всякий случай — в "Алгоритмах" никто ничего толкового не сказал.
Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).
Здравствуйте, 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 — число симметрий.
Это и будет число вариантов.
Перекуём баги на фичи!
Re[2]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Linuxoid, Вы писали:
L>>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).
[]
К>Поэлементная конъюнкция векторов для всех точек полимино покажет, какие варианты совпали с оригиналом, т.е. где есть симметрия. К>Теперь считаем 8 — число симметрий. К>Это и будет число вариантов.
Я не совсем понял ответ (вернее, совсем не понял ), но по-моему, вопрос был немного о другом.
Например, для квадрата число видов — 1, для прямой полоски — 2, и т.д.
Здравствуйте, Linuxoid, Вы писали:
L>Спрошу еще здесь на всякий случай — в "Алгоритмах" никто ничего толкового не сказал. L>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).
Нижеследующий код неверен. Правильный вариант приведён в одном из постов дальше.
char board[NY][NX];
// полимино
// 1 - клетка заполнена
// 0 - клетка не заполнена
//возвращает число разных видов полимино, лежащего в boardint 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, ты вроде большой спец по полимино..
К>Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино). К>Получаем вектор из 8 (или 4) булевских значений.
К>Теперь считаем 8 — число симметрий. К>Это и будет число вариантов.
Например, если число симметрий равно 8 (квадрат), вариантов 0
Re[3]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Pushkin, Вы писали:
К>>Теперь считаем 8 — число симметрий. К>>Это и будет число вариантов.
P>Например, если число симметрий равно 8 (квадрат), вариантов 0
У меня в школе было от 2 до 5 по арифметике
"Математичка обурела: сказала, что я нихрена не знаю, и поставила в дневник какую-то цифру".
8 симметрий, включая самого себя
Естественно, что сам с собой — всегда совпадет.
Ну, в общем, под вечер туплю, формула не выводится... где-то 7-8.
Перекуём баги на фичи!
Re[3]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, Кодт, Вы писали:
P> К>>Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино). К>>Получаем вектор из 8 (или 4) булевских значений.
P>
К>>Теперь считаем 8 — число симметрий. К>>Это и будет число вариантов.
P>Например, если число симметрий равно 8 (квадрат), вариантов 0
Наверное, все-таки 8 / число симметрий.
Re[2]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Pushkin, Вы писали:
К>>>Теперь считаем 8 — число симметрий. К>>>Это и будет число вариантов.
P>>Например, если число симметрий равно 8 (квадрат), вариантов 0
Сори, не въехал
посчитал минус за тире
Re[4]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Кодт, Вы писали:
К>Центр тяжести для подсчета отражений не нужен: достаточно только найти границы по X,Y. К>А вот для тетриса — центр тяжести пригодится
Подсчёт центра тяжести существенно ускоряет подсчёт симметрий для больших полимино, т.к. во всех случаях, кроме британского флага сразу даёт ответ "нет симметрий" и таким образом вместо O(N^2) переводит задачу в O(N). Конечно остаётся O(N^2) для подсчёта самого центра, но оно и так возникает при подсчёте границ. А может оно всё и уже где-то лежит. Короче для 20х20 это реально ускоряет в разы, проверено.
Re[3]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, Кодт, Вы писали:
К>И, естественно, программу можно оптимизировать. К>Вот как это выглядит на Ц++
В точности то же, что и у меня...
Но изящней...
Но не доведено до конца...
И без подсчёта центра тяжести, что существенно замедляет...
Что делает ненужным колдовство с битами...
Re[3]: Pushkin, ты вроде большой спец по полимино..
Здравствуйте, 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 +
Пожалуйста, не читайте мой вчерашний код, я бредил
Ниже приведён верный вариант.
1) Я его проверил. Как по картинкам, так и встроив в подсчёт полимино (там гигантские числа, они совпали, это почти гарантия).
2) Перевёл всё на битовое представление Кодта. Помимо общей симпатичности, это даёт удобный способ экстренного выхода.
3) Продолжаю настаивать на крайней полезности простого трюка с центром тяжести. Специальное исследование показало, что для полимино площадью 15 это даёт ускорение подсчёта симметрий в 5 раз. Для больших — больше. Кстати, идея в своё время исходила от MichaelP.
4) Использовал гениальную формулу автора 8/r. Смешно, что нам с Кодтом она в голову сразу не пришла
Итого: "У тебя своего ничего нет. Ты голодранец " (c) Брагинский-Рязанов
char board[NY][NX];
// полимино
// 1 - клетка заполнена
// 0 - клетка не заполнена
//возвращает число разных видов полимино, лежащего в boardint 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;
}