![](https://habrastorage.org/webt/59/f0/a5/59f0a58e22ba0685844423.png)
Меня всегда привлекали элементарные алгоритмы, с помощью которых можно создавать сложные паттерны. Есть в таких алгоритмах что-то фундаментальное. Один из таких алгоритмов — Perfect Shuffle. Посмотрим на его необычные свойства, а также попробуем нарисовать несколько впечатляющих фракталов с помощью этого алгоритма.
Дальше много картинок, gif-анимации и немного музыки.
Perfect Shuffle известен в среде фокусников-картежников. Называют они его Faro Shuffle. Недавно тоже захотел научиться показывать карточные фокусы. С чего начинаются фокусы? С развития ловкости рук. Повертев неделю колоду карт, освоил основные способы тасовки — «Riffle Shuffle», «Faro Shuffle», «Charlier Pass». Тренируясь делать Faro Shuffle, однажды упорядочил колоду так, чтобы все черные масти находились в начале колоды, а красные — в конце. Сделав несколько раз Faro Shuffle, обратил внимание на необычный порядок карт в колоде. Карты отложил и сел программировать.
Данный алгоритм меняет порядок элементов в массиве (перемешивает массив). Сей алгоритм элементарен:
1. Делим массив на две равные части.
2. Элементы из первой половины массива размещаем на четных позициях. Из второй — на нечетных.
Наглядно:
![](https://habrastorage.org/webt/59/f0/c2/59f0c258689be693972011.png)
Еще наглядней:
function shuffle(array){
var half=array.length/2; //здесь мы смело делим длину массива пополам
var temparray=[];
for(var i=0;i<half;i++){
temparray[i*2]=array[i+half]; //и используем в качестве индекса
temparray[i*2+1]=array[i];
}
return temparray;
}
var array=[1, 2, 3, 4, 5, 6, 7, 8];
array=shuffle(array);
console.log(array); // [5, 1, 6, 2, 7, 3, 8, 4]
![](https://habrastorage.org/webt/59/f0/c6/59f0c6f0c9e5a145424353.png)
Как видим, крайние элементы остаются на своих позициях, а середина массива перемешивается тем же in-shuffle. Вариант out-shuffle далее не рассматриваем.
Кроме того, не рассматриваем вариант, когда количество элементов в массиве нечетное — последний элемент в массиве остается на своей позиции.
У алгоритма есть несколько примечательных свойств. Если перемешать массив несколько раз — через n итераций все элементы вернутся в исходную позицию! Это очевидно. Алгоритм детерминированный. Для каждого следующего состояния массива существует только одно уникальное предыдущее состояние. Количество всех возможных состояний ограничено длиной массива. Если мы будем перемешивать массив итеративно — рано или поздно мы исчерпаем возможные состояния и пойдем по второму кругу. На самом деле, это случится гораздо раньше. Количество итераций, необходимых для возврата массива в исходное состояние — меньше (или равно) количества элементов в массиве. «Меньше или равно» — все, что можно сказать о количестве итераций.
Для массива из 12-ти элементов хватит 12-ти итераций:
![](https://habrastorage.org/webt/59/f0/ce/59f0ce4d7da57797540724.png)
Для массива из 14-ти элементов хватит всего 4 итерации:
![](https://habrastorage.org/webt/59/f0/cf/59f0cf10e3b2b972779140.png)
На картинке ниже (кликабельно) перемешиваем массивы с длинами от 2-х элементов до 20-ти:
![](https://habrastorage.org/webt/59/f0/cf/59f0cf7b94d08581254571.png)
(unshuffle)
Перечисленные массивы возвращаются в исходное состояние на
2, 4, 3, 6, 10, 12, 4, 8, 18, 6
итерациях. Последовательность A002326
function a002326(n){
var a=1;
var m=0;
do{
a*=2;
a%=2*n+1;
m++;
}while(a>1);
return m;
}
for(var n=1;n<11;n++){
m=a002326(n);
console.log(m);
}
Построим график! На графике по оси X отметим количество элементов в массиве (деленное на 2). По оси Y — количество итераций. Белыми точками обозначим исходные состояния массивов (начало координат — левый верхний угол):
![](https://habrastorage.org/webt/59/f0/d9/59f0d9103a7c0197965270.png)
Согласитесь, точки на графике размещаются хаотично.
Еще одно необычное свойство Perfect Shuffle — после некоторого количества итераций, порядок элементов в массиве может измениться на обратный. Выше на картинке мы перемешивали массив из 12-ти элементов. Порядок элементов меняется на обратный на 6-й итерации. Нарисуем еще один график, на котором отметим массивы с обратным порядком элементов:
![](https://habrastorage.org/webt/59/f0/d9/59f0d91e71a5b042472770.png)
Опять же, размещение точек, не менее хаотично.
Очень интересно понаблюдать за перемещением элементов в массиве! Как элементов из первой половины массива в совокупности, так и конкретного (первого) элемента в частности.
Заполним первую половину массива нулями, вторую — единицами (далее на картинках нули — черные пиксели, единицы — белые). На картинках ниже, каждая строка (X) — состояние массива. По Y — итерации.
Несколько массивов (142-150 элементов):
![](https://habrastorage.org/webt/59/f0/e1/59f0e173e6e1a494534941.png)
![](https://habrastorage.org/webt/59/f0/e1/59f0e173c464f688553413.png)
![](https://habrastorage.org/webt/59/f0/e1/59f0e174184c2603824511.png)
![](https://habrastorage.org/webt/59/f0/e1/59f0e1742b63f526546037.png)
![](https://habrastorage.org/webt/59/f0/e1/59f0e1744be7d263918027.png)
Картинки кликабельны
288 элементов (144*2):
![](https://habrastorage.org/webt/pm/a1/52/pma152yulqsic1o1yh5utxasy1w.png)
610 элементов:
![](https://habrastorage.org/webt/59/f0/e2/59f0e2bc835d5519613640.png)
Массив из 142-х элементов, на 55-й итерации выглядит вот так:
0011001100011001100011001100011001100111001100111001100111001100111001100110001100110001100110001100110001100110011100110011100110011100110011
Эту последовательность можем вбить сюда и посмотреть на этот массив более наглядно:
![](https://habrastorage.org/webt/59/f0/f6/59f0f6880c577205936187.png)
![](https://habrastorage.org/webt/59/f0/f7/59f0f7ccd69fa378697603.gif)
![](https://habrastorage.org/webt/59/f0/f7/59f0f75b3de36134900032.gif)
![](https://habrastorage.org/webt/59/f0/f7/59f0f7dd7375e097917897.gif)
![](https://habrastorage.org/webt/59/f0/f7/59f0f7ea68276921388521.gif)
![](https://habrastorage.org/webt/59/f0/f7/59f0f79c62c54484148352.gif)
Как видим, и здесь у нас сплошной хаос. Понаблюдаем за отдельным элементом и его траекторией в массиве.
Массив 610 элементов. Заполнен только первый элемент:
![](https://habrastorage.org/webt/qv/2-/_o/qv2-_ocjwjhxsd9ycdpdi4px7us.png)
Вообще, для отдельного элемента, не обязательно перемешивать весь массив. Положение конкретного элемента на следующей итерации можно посчитать по формуле:
![](https://habrastorage.org/webt/59/f0/ec/59f0ec4c976a8443465742.png)
(Y — длина массива)
Первые массивы (с длинами от 2-х до 22-х):
![](https://habrastorage.org/webt/59/f0/ec/59f0ecd767eef711696414.png)
На картинке выше: в верхней части картинки массив и положение элемента на каждой итерации, в нижней части линии — все возможные положения элемента. Как видим, траектория элемента внутри массива тоже не очевидна. Чтобы окончательно в этом убедиться — из этих линий сделаем еще один график, сложив их «стопочкой»:
![](https://habrastorage.org/webt/59/f0/ee/59f0eea06b61f948107810.png)
Кликабельно
Черные пиксели — те позиции в массиве, в которые не попадает первый элемент при перемешивании.
На этом можно было бы остановиться, но мы пойдем еще дальше! Понаблюдаем за перемещением всех элементов в массиве. Для этого перейдем к матрицам.
Но прежде, чем переходить к перемешиванию матриц, покажу еще два фокуса с массивами.
Во второй половине массива меняем порядок элементов на обратный (на каждой итерации):
![](https://habrastorage.org/webt/sh/v4/rv/shv4rv9ndqahddzzsfa5nvoilfo.png)
Во второй половине инвертируем элементы:
![](https://habrastorage.org/webt/tt/aq/bp/ttaqbpjhamr8b8hounz8bopsou0.png)
Две эти операции нам еще пригодятся.
Перейдем к матрицам!
Заполним в матрице, в первой строке — первый элемент, во второй — второй и т.д. Другими словами, нарисуем диагональ:
![](https://habrastorage.org/webt/ab/dp/qv/abdpqvrpxkmq2vhznxfxhr4ybbc.png)
Перемешаем с помощью Perfect Shuffle столбики в матрице. Так мы сможем посмотреть, куда попадают все элементы после перемешивания. Матрица 80х80:
![](https://habrastorage.org/webt/jm/xl/_d/jmxl_dhks_bpv9zoe_xqfy8thc4.png)
Тут явно не хватает еще одной диагонали:
![](https://habrastorage.org/webt/0k/2x/vm/0k2xvmwoscfbkydtr6lhbce42j0.png)
Очень любопытный муар получается. Матрица 242х242 с 27 по 35 итерацию:
![](https://habrastorage.org/webt/un/iq/au/uniqauubhq29j5fswfzzaknchr4.png)
Ну и если уже начали перемешивать столбцы в матрице с помощью Perfect Shuffle — почему бы не перемешать и строки?
Немного модифицируем нашу функцию:
function shufflecr(array){
var half=array.length/2;
var temparray=[];
for(var x=0;x<half;x++){
temparray[x*2]=[];
temparray[x*2+1]=[];
for(var y=0;y<half;y++){
temparray[x*2][y*2]=array[x+half][y+half];
temparray[x*2+1][y*2]=array[x][y+half];
temparray[x*2][y*2+1]=array[x+half][y];
temparray[x*2+1][y*2+1]=array[x][y];
}
}
return temparray;
}
Делим матрицу на 4 части. Перемешиваем столбцы. Перемешиваем строки. Получаем новую матрицу. Наглядно:
![](https://habrastorage.org/webt/pp/bh/yx/ppbhyxplwevxxxwt-su0huevam0.png)
Диагонали перемешиваются довольно скучно:
![](https://habrastorage.org/webt/ze/su/jl/zesujlcvnudroby5epr489gvqic.png)
Может даже показаться, что в функции где-то ошибка и матрица не перемешивается. Сдвинем диагонали на один пиксель вправо:
![](https://habrastorage.org/webt/rr/us/oe/rrusoebgkrccvbohxipj93_1oqa.png)
Замечательно. Функция работает, матрица перемешивается. Правда опять же довольно скучно. Попробуем заполнить матрицу каким-то паттерном. В рандомном месте нарисуем квадрат:
![](https://habrastorage.org/webt/ck/m9/nt/ckm9ntdv8rpbcyhsbvry9h2omxs.png)
Размер матрицы 80х80 выбрал не случайно. При перемешивании массива длиной 80 элементов, на 27-й итерации порядок элементов меняется на обратный.
Подвигаем этот квадрат!
![](https://habrastorage.org/webt/2o/m_/et/2om_etw_lvse2qiuonuiq4dsl6o.gif)
Тут можно заметить одно очень интересное свойство, но еще лучше это свойство видно, если нарисовать окружность:
![](https://habrastorage.org/webt/nh/nb/lr/nhnblrexjqxj9xtjbmvbfmzvcfq.png)
Обратите внимание на краевые эффекты. Наша матрица сворачивается в тор! Это хорошо видно на второй итерации.
Подвигаем:
![](https://habrastorage.org/webt/xt/fs/dt/xtfsdtyrmcpmq3tnels51ns6tgs.gif)
Выше мы перемешивали массив и получили несколько замечательных картинок. Одна из них (144*2):
![](https://habrastorage.org/webt/pm/a1/52/pma152yulqsic1o1yh5utxasy1w.png)
Ее тоже запишем в матрицу и перемешаем:
![](https://habrastorage.org/webt/aq/et/vk/aqetvkqhofx_ixqcb5zbpjvldl4.png)
Или даже так. Возьмем исходный паттерн:
![](https://habrastorage.org/webt/pm/a1/52/pma152yulqsic1o1yh5utxasy1w.png)
И оставим на нем пиксели с координатами x*4+i, y*4+j. Для i=2, j=2:
![](https://habrastorage.org/webt/5m/iq/bj/5miqbjm1amxkl3sjfovlms3zvi4.png)
Уберем пустые столбцы и строки:
![](https://habrastorage.org/webt/h_/v3/fg/h_v3fg3ezvdqkydyjb3lb5gpkha.png)
Для других i и j (фактически сделали perfect unshuffle — разделили матрицу на 16 частей):
![](https://habrastorage.org/webt/5l/wz/xh/5lwzxhzjd_1m3b4liemosbpdtpw.png)
Знакомые паттерны! Похожие паттерны можно нарисовать с помощью тригонометрических функций z=sin(n*x/y) и z=sin(n*x*y)
График функции z=sin(3*x*y). Если z>=0 — белый пиксель. Если z<0 — черный:
![](https://habrastorage.org/webt/zw/qm/y0/zwqmy0qfm2pifvyjomy30ui4lnq.png)
z=sin(13*x*y):
![](https://habrastorage.org/webt/nj/9_/da/nj9_dafjz4qyrcgjrdaf_d97rza.png)
Один из интересных паттернов:
![](https://habrastorage.org/webt/sk/id/eg/skidegavrihwhif97yiwujyuwco.png)
Можем сделать заливку, чтобы выделить замкнутые области:
![](https://habrastorage.org/webt/44/qi/aq/44qiaq8ds5ntnd-89b1nohil2sa.png)
На самом деле это довольно круто! Можем взять такой шаблон:
![](https://habrastorage.org/webt/90/c9/ag/90c9agzzn3i8vy3luiirmfxj7o0.png)
И немного сжать его осликом:
![](https://habrastorage.org/webt/77/od/iu/77odiue49osnkynohspek5jmnfe.png)
Получили знакомый паттерн.
Можно поиграться с другими шаблонами:
![](https://habrastorage.org/webt/pb/0x/yc/pb0xycdd9g8om8gxxohcol7ib8a.png)
Сжали осликом:
![](https://habrastorage.org/webt/xp/nk/2r/xpnk2rr3qdxclhlpmk-c4icdyz0.png)
Вспомним о фокусах (изменение порядка элементов на обратный и инвертирование).
Изменение порядка элементов дает очень интересные паттерны! Один из них:
![](https://habrastorage.org/webt/cq/v_/ja/cqv_jab4-xggakyb6lcwqwwuuak.png)
С заливкой:
![](https://habrastorage.org/webt/lf/ur/lk/lfurlk105yxr7zywdajxw54zcaq.png)
Другие паттерны не менее интересны, но на них останавливаться не будем. Гораздо интересней понаблюдать за инвертированием.
Для этого эксперимента нам хватит пустой матрицы. Разделим ее на 4 части. Две из них инвертируем. Перемешаем. На первой итерации ничего необычного:
![](https://habrastorage.org/webt/0q/cp/hv/0qcphvhl8rhamsnc-gzi7pprj1e.png)
А вот дальше появляются любопытные паттерны:
![](https://habrastorage.org/webt/kd/ss/k8/kdssk8zj6atdn2jq04tkwt7yloc.png)
Чтобы разобраться, откуда берутся эти паттерны, вернемся еще раз к массивам. До этого мы использовали матрицы и массивы фиксированной длины. Попробуем немного изменить подход — длину будем увеличивать постепенно:
1. Создадим массив из n элементов.
2. Сделаем его копию.
3. Перемешаем копию с оригиналом с помощью Perfect Shuffle. Получили массив из n*2 элементов.
4. Вернемся к шагу 2.
Копию каждый раз будем инвертировать.
Начнем с массива из двух элементов — 1 и 0
10 — исходный массив
10, 01 — массив и инвертированная копия
0110 — смешали
0110, 1001 — массив и инвертированная копия
10010110
10010110, 01101001
0110100110010110
… и т.д.
Получили последовательность Морса — Туэ (A010060) — простейший фрактал!
И обратно к матрицам. Вот тут начинается чистое искусство. До этого мы делили матрицу на 4 части и перемешивали эти части. Попробуем копировать матрицу, производить над копиями некоторые элементарные действия и перемешивать оригинал с копиями.
С матрицами можем произвести 15 элементарных действий. Действие 0 — матрица без изменений. Действия 1-7 — разные способы вращения матрицы. Действия 8-15 — инвертирование. Наглядно:
![](https://habrastorage.org/webt/rf/gj/q2/rfgjq2sw8ebx_nb0ikvavc1-ip8.png)
В качестве примера, произведем над копиями действия 0, 0, 7, 7. Действие 7 — поворот матрицы на 90°.
![](https://habrastorage.org/webt/yb/3v/th/yb3vthmiu2szo9a2tkxahhlbn7u.png)
Следующая итерация:
![](https://habrastorage.org/webt/dn/wd/9g/dnwd9guwkansr8b0jo6-6mzklg8.png)
… восьмая итерация:
![](https://habrastorage.org/webt/nm/p7/5b/nmp75bmugmw8exgocddxt6o1pd0.png)
Очень необычный фрактал получился.
Действия 0, 0, 7, 7. Первая итерация:
![](https://habrastorage.org/webt/vf/xu/ic/vfxuicqpiye2pc0z3yf6iqnbowm.png)
Вторая итерация:
![](https://habrastorage.org/webt/rk/u6/n3/rku6n3oxtwupj1nyko8zuic6cms.png)
Восьмая:
![](https://habrastorage.org/webt/zq/il/_b/zqil_bvfuphntjojvcz9bpgmz4o.png)
А теперь два фокуса.
Накладываем сверху копию картинки с прозрачными белыми пикселями, копию поворачиваем на 90°:
![](https://habrastorage.org/webt/0h/dy/ad/0hdyadhdvzmyz2dijljaso-5gbm.png)
Копия повернута по вертикали:
![](https://habrastorage.org/webt/zu/ur/f-/zuurf-4wu1jq57yp4pbu1eoejki.png)
Комбинируя перечисленные действия, можно нарисовать 16^4=65536 фракталов. Некоторые из них:
Нарисованы за 6 итераций. Картинки кликабельны (8 итераций).
![](https://habrastorage.org/webt/45/2g/_z/452g_z0phqdequkra4cqzuh3o5c.png)
![](https://habrastorage.org/webt/rs/ls/0i/rsls0ixru2tldujzgwszgc6yy98.png)
![](https://habrastorage.org/webt/wu/kt/fz/wuktfzwq9822m005qlwxe1si2za.png)
![](https://habrastorage.org/webt/uc/uc/cn/ucuccndnvjxua52nbzu9jkgofqm.png)
![](https://habrastorage.org/webt/ro/ta/bx/rotabxrfv8hcsmarbb-eesxjo-s.png)
![](https://habrastorage.org/webt/su/ew/sy/suewsy-h6flnzbs37lixsjzldvc.png)
![](https://habrastorage.org/webt/f0/ed/fq/f0edfqys01iswv2h6ehqtuhzm4s.png)
![](https://habrastorage.org/webt/7j/sd/aw/7jsdawzc-824g-wskief5kt76cw.png)
![](https://habrastorage.org/webt/eo/qy/id/eoqyidd8clkdshf3cbmpunh-xdu.png)
![](https://habrastorage.org/webt/lm/zp/6x/lmzp6xy_rhzah8zzufaokaozexo.png)
![](https://habrastorage.org/webt/f1/w6/7b/f1w67bje8_b0j1gqnxzqhixwesk.png)
![](https://habrastorage.org/webt/f5/oe/ui/f5oeuixf2icezstjb6ultje9ii0.png)
![](https://habrastorage.org/webt/d1/rl/uv/d1rluvog-0a7oglfr3kchvnohm0.png)
![](https://habrastorage.org/webt/jf/_w/gx/jf_wgxjgx2bf270pm_wyw69jfza.png)
![](https://habrastorage.org/webt/e6/pv/pj/e6pvpjrzwrjtkcwiz3m3yqh5ris.png)
![](https://habrastorage.org/webt/yw/gu/br/ywgubre3eeoxl34_o2d4p8_bk1a.png)
![](https://habrastorage.org/webt/ro/os/nu/roosnuu2oowjunsaj81pvj8f2hm.png)
![](https://habrastorage.org/webt/wt/zv/-d/wtzv-deqsexmwuu3_mws_fkizhy.png)
![](https://habrastorage.org/webt/xd/cp/pc/xdcppcwnki4m1dmfmdn-upwr2ae.png)
![](https://habrastorage.org/webt/85/cb/c4/85cbc449h_xdszy7bbahczg22ci.png)
![](https://habrastorage.org/webt/4h/pu/mn/4hpumnz7v7hkyryoq-etxgpl1lk.png)
![](https://habrastorage.org/webt/dg/d8/yv/dgd8yvxfvvty7zvdrp1zr61gwqw.png)
![](https://habrastorage.org/webt/pd/hl/t-/pdhlt-9icdflnwmpxkxz38_1uba.png)
![](https://habrastorage.org/webt/rs/_e/ux/rs_eux9ydpyp8vzcijstl4lei64.png)
![](https://habrastorage.org/webt/4c/p2/qj/4cp2qj8a2mcsejd68zv94wu96oy.png)
![](https://habrastorage.org/webt/s8/ur/ie/s8uriexfllt6b0a5x9o17nqgl7g.png)
![](https://habrastorage.org/webt/g6/w3/ov/g6w3ovaa8g1zudlpn-voaazyeay.png)
![](https://habrastorage.org/webt/ax/k-/9h/axk-9hlvan8yk650eij7q9cpomo.png)
![](https://habrastorage.org/webt/xw/ld/co/xwldcoqo0svunpflwusv-vz-6_8.png)
![](https://habrastorage.org/webt/71/jc/_s/71jc_svyynnjhwc96ha4167rx4g.png)
![](https://habrastorage.org/webt/5q/pk/fj/5qpkfjgnvcwmzx-wlpzzfwvm7w0.png)
![](https://habrastorage.org/webt/ww/5f/f7/ww5ff7haxfuxmmrvytc9ilbbo_m.png)
А вот эти тянут на шедевр:
15, 5, 9, 5:
![](https://habrastorage.org/webt/qf/k9/j1/qfk9j1tiqgyijnktucujk1w7-kg.png)
3, 5, 9, 5:
![](https://habrastorage.org/webt/x7/7y/nk/x77ynkviekxi1ukvp18jtbbj7li.png)
13, 7, 11, 11:
![](https://habrastorage.org/webt/tr/m4/pn/trm4pnv7ibwj9qqsqb1mx9vwt-c.png)
0, 0, 7, 13:
![](https://habrastorage.org/webt/0-/s3/qm/0-s3qm0qbepfgguh7tu5g-spumg.png)
1, 1, 4, 14:
![](https://habrastorage.org/webt/tx/gd/eq/txgdeqkttxbfx0jjdz0xkmaq6ty.png)
Другие фракталы можно нарисовать здесь
Вот такие «карточные фокусы» получились. Думаю, на этом можно временно остановиться (можно перемешивать трехмерные матрицы, но об этом в другой раз).
![](https://habrastorage.org/webt/ne/2l/8b/ne2l8bj3pvdxnnizsknt_y0_0dk.png)
![](https://habrastorage.org/webt/r9/mz/pn/r9mzpnfraq7vcnmqmbmgjeosufu.jpeg)
![](https://habrastorage.org/webt/bz/qo/mw/bzqomwmsaepoix293assixe_4tm.jpeg)
Комментарии (17)
dom1n1k
02.11.2017 12:41+1Прекрасная статья, люблю когда вроде бы несложные вещи, но так подробно разложены по полкам всеми кишками.
zuborg
02.11.2017 14:45+1Надо Стивену Вольфраму это показать, он очень любит такие штуки, даже книгу написал (не про тасование, а про клеточные автоматы и всякое-такое)
LoadRunner
02.11.2017 14:56Мне почему-то некоторые картинки напомнили схемы вязания.
Ну и ещё я тщетно пытался разглядеть в них 3D-картинку. И чуть не уснул в процессе — почему-то от них сонливость нагоняется.
nought
02.11.2017 15:06Очень круто, что некоторые картинки буквально повторяют паттерны из эксперимента с сыпучими веществами и чистыми нотами, как на видео:
www.youtube.com/watch?v=wvJAgrUBF4w
OlegZH
02.11.2017 20:05Хотелось бы всё это самому проверить в деле и почувствовать. Как это всё рисуется? Где именно происходит «отрисовка»?
А ещё хотелось бы знать, кто-нибудь питался приспособить эти фракталы к распознаванию образов? Я имею в виду хитрое (существенно нелинейное) разбиение признакового пространства, которое позволяет обойти гипотезу компактности. Ведь, реально объекты различных классов существенно «зацеплены» друг за друга, и любые классификаторы будут, очевидно, существенно «ошибаться».
dcc0
02.11.2017 22:52+1Отличный материал. Спасибо.
Есть в таких алгоритмах что-то фундаментальное
Да. Веет стариной глубокой.
Про картинки с фракталами: тот момент, когда немного начинаешь понимать людей, которые любят вышивать крестиком.
Milfgard
03.11.2017 03:42+1Спасибо за гикпорн.
Вот эта штука:
в физическом исполнении выглядит так:
«Достаточно хорошим» в большинстве игр считается два-три таких rifle и несколько случайных сдвигов.
Jarro
03.11.2017 16:47На самом деле, никакой Perfect Shuffle для построения большинства этих изображений не понадобится — интереснейшие муаровые узоры будут образовываться даже тогда, когда мы просто будем хитро прописывать зависимость цвета пикселя от его координат. :)
Подробнее о моем маленьком исследовании данного типа фракталов можно прочитать например здесь: www.gamedev.ru/code/forum/?id=177887
Мое видео на данную тему (осторожно, плохое качество, записывал давно)
DrZlodberg
Чертовски любопытно!
А ещё интересно, нельзя ли использовать последнюю картинку для сжатия изображений видео-кодеком с бОльшей пользой?
ЗЫ: За генератор отдельное спасибо. Попадается куча интересных, типа 8,12, 7,8. А если использовать не ч/б а градиент на входе не будет ли интереснее?
RomanArzumanyan
Подобный алгоритм как раз используется в декомпозиции матриц дискретного преобразования в видео кодеках.
DrZlodberg
Хмм… Разве такой? Вроде там используется что-то типа сортировки, чтобы вч гармоники оказались в одном углу, а нч в другом (если не путаю). А тут идея использовать разницу (довольно небольшую для полутоновых изображений) между отдельными микрокадрами единственного изображения, которые получаются в некоторых случаях (т.е. превратить одно изображение в видео меньшего разрешения). Сам сабжевый алгоритм ту не особо важен, кадры можно получить и проще. А вот будет ли профит?
RomanArzumanyan
Да, такой. Матрицу преобразования рекурсивно делят на чётные и нечётные строки, а потом компенсируют престановку входов. Получается тот же perfect shuffle. Цель у него, конечно другая (переход к быстрому алгоритму за счёт свойств матрицы), но получается что perfect shuffle всё-таки присутствует. Вот статья с примером, если интересно: halicery.com/Image/idct.html
То, о чём говорите вы — это порядок обхода коэффициентов преобразования (Z-order scan), когда в начале идут низкочастотные компоненты, а за ними — высокочастотные (большую часть которых обрезают, за счёт чего достигается сжатие).
DrZlodberg
Спасибо, интересно. В математике не разобрался, но основную идею понял.
Однако идея была использовать преобразование совсем в другом месте и с другими целями, так что вопрос открыт.
labone
удалено