- PVSM.RU - https://www.pvsm.ru -
Меня всегда привлекали элементарные алгоритмы, с помощью которых можно создавать сложные паттерны. Есть в таких алгоритмах что-то фундаментальное. Один из таких алгоритмов — Perfect Shuffle. Посмотрим на его необычные свойства, а также попробуем нарисовать несколько впечатляющих фракталов с помощью этого алгоритма.
Дальше много картинок, gif-анимации и немного музыки.
Perfect Shuffle известен в среде фокусников-картежников. Называют они его Faro Shuffle. Недавно тоже захотел научиться показывать карточные фокусы. С чего начинаются фокусы? С развития ловкости рук. Повертев неделю колоду карт, освоил основные способы тасовки — «Riffle Shuffle», «Faro Shuffle», «Charlier Pass». Тренируясь делать Faro Shuffle, однажды упорядочил колоду так, чтобы все черные масти находились в начале колоды, а красные — в конце. Сделав несколько раз Faro Shuffle, обратил внимание на необычный порядок карт в колоде. Карты отложил и сел программировать.
Данный алгоритм меняет порядок элементов в массиве (перемешивает массив). Сей алгоритм элементарен:
1. Делим массив на две равные части.
2. Элементы из первой половины массива размещаем на четных позициях. Из второй — на нечетных.
Наглядно:
Еще наглядней:
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]
Как видим, крайние элементы остаются на своих позициях, а середина массива перемешивается тем же in-shuffle. Вариант out-shuffle далее не рассматриваем.
Кроме того, не рассматриваем вариант, когда количество элементов в массиве нечетное — последний элемент в массиве остается на своей позиции.
У алгоритма есть несколько примечательных свойств. Если перемешать массив несколько раз — через n итераций все элементы вернутся в исходную позицию! Это очевидно. Алгоритм детерминированный. Для каждого следующего состояния массива существует только одно уникальное предыдущее состояние. Количество всех возможных состояний ограничено длиной массива. Если мы будем перемешивать массив итеративно — рано или поздно мы исчерпаем возможные состояния и пойдем по второму кругу. На самом деле, это случится гораздо раньше. Количество итераций, необходимых для возврата массива в исходное состояние — меньше (или равно) количества элементов в массиве. «Меньше или равно» — все, что можно сказать о количестве итераций.
Для массива из 12-ти элементов хватит 12-ти итераций:
Для массива из 14-ти элементов хватит всего 4 итерации:
На картинке ниже (кликабельно) перемешиваем массивы с длинами от 2-х элементов до 20-ти:
Перечисленные массивы возвращаются в исходное состояние на
2, 4, 3, 6, 10, 12, 4, 8, 18, 6
итерациях. Последовательность A002326 [2]
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 — количество итераций. Белыми точками обозначим исходные состояния массивов (начало координат — левый верхний угол):
Согласитесь, точки на графике размещаются хаотично.
Еще одно необычное свойство Perfect Shuffle — после некоторого количества итераций, порядок элементов в массиве может измениться на обратный. Выше на картинке мы перемешивали массив из 12-ти элементов. Порядок элементов меняется на обратный на 6-й итерации. Нарисуем еще один график, на котором отметим массивы с обратным порядком элементов:
Опять же, размещение точек, не менее хаотично.
Очень интересно понаблюдать за перемещением элементов в массиве! Как элементов из первой половины массива в совокупности, так и конкретного (первого) элемента в частности.
Заполним первую половину массива нулями, вторую — единицами (далее на картинках нули — черные пиксели, единицы — белые). На картинках ниже, каждая строка (X) — состояние массива. По Y — итерации.
Несколько массивов (142-150 элементов):
[3] [4] [5] [6] [7]
Картинки кликабельны
288 элементов (144*2):
610 элементов:
Как видим, и здесь у нас сплошной хаос. Понаблюдаем за отдельным элементом и его траекторией в массиве.
Массив 610 элементов. Заполнен только первый элемент:
Вообще, для отдельного элемента, не обязательно перемешивать весь массив. Положение конкретного элемента на следующей итерации можно посчитать по формуле:
(Y — длина массива)
Первые массивы (с длинами от 2-х до 22-х):
На картинке выше: в верхней части картинки массив и положение элемента на каждой итерации, в нижней части линии — все возможные положения элемента. Как видим, траектория элемента внутри массива тоже не очевидна. Чтобы окончательно в этом убедиться — из этих линий сделаем еще один график, сложив их «стопочкой»:
Черные пиксели — те позиции в массиве, в которые не попадает первый элемент при перемешивании.
На этом можно было бы остановиться, но мы пойдем еще дальше! Понаблюдаем за перемещением всех элементов в массиве. Для этого перейдем к матрицам.
Но прежде, чем переходить к перемешиванию матриц, покажу еще два фокуса с массивами.
Во второй половине массива меняем порядок элементов на обратный (на каждой итерации):
Во второй половине инвертируем элементы:
Две эти операции нам еще пригодятся.
Перейдем к матрицам!
Заполним в матрице, в первой строке — первый элемент, во второй — второй и т.д. Другими словами, нарисуем диагональ:
Перемешаем с помощью Perfect Shuffle столбики в матрице. Так мы сможем посмотреть, куда попадают все элементы после перемешивания. Матрица 80х80:
Тут явно не хватает еще одной диагонали:
Очень любопытный муар получается. Матрица 242х242 с 27 по 35 итерацию:
Ну и если уже начали перемешивать столбцы в матрице с помощью 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 части. Перемешиваем столбцы. Перемешиваем строки. Получаем новую матрицу. Наглядно:
Диагонали перемешиваются довольно скучно:
Может даже показаться, что в функции где-то ошибка и матрица не перемешивается. Сдвинем диагонали на один пиксель вправо:
Замечательно. Функция работает, матрица перемешивается. Правда опять же довольно скучно. Попробуем заполнить матрицу каким-то паттерном. В рандомном месте нарисуем квадрат:
Размер матрицы 80х80 выбрал не случайно. При перемешивании массива длиной 80 элементов, на 27-й итерации порядок элементов меняется на обратный.
Подвигаем этот квадрат!
Тут можно заметить одно очень интересное свойство, но еще лучше это свойство видно, если нарисовать окружность:
Обратите внимание на краевые эффекты. Наша матрица сворачивается в тор! Это хорошо видно на второй итерации.
Подвигаем:
Выше мы перемешивали массив и получили несколько замечательных картинок. Одна из них (144*2):
Ее тоже запишем в матрицу и перемешаем:
Или даже так. Возьмем исходный паттерн:
И оставим на нем пиксели с координатами x*4+i, y*4+j. Для i=2, j=2:
Уберем пустые столбцы и строки:
Для других i и j (фактически сделали perfect unshuffle — разделили матрицу на 16 частей):
Знакомые паттерны! Похожие паттерны можно нарисовать с помощью тригонометрических функций z=sin(n*x/y) [12] и z=sin(n*x*y) [13]
График функции z=sin(3*x*y). Если z>=0 — белый пиксель. Если z<0 — черный:
z=sin(13*x*y):
Один из интересных паттернов:
Можем сделать заливку, чтобы выделить замкнутые области:
И немного сжать его осликом:
Получили знакомый паттерн.
Можно поиграться с другими шаблонами:
Сжали осликом:
Вспомним о фокусах (изменение порядка элементов на обратный и инвертирование).
Изменение порядка элементов дает очень интересные паттерны! Один из них:
С заливкой:
Другие паттерны не менее интересны, но на них останавливаться не будем. Гораздо интересней понаблюдать за инвертированием.
Для этого эксперимента нам хватит пустой матрицы. Разделим ее на 4 части. Две из них инвертируем. Перемешаем. На первой итерации ничего необычного:
А вот дальше появляются любопытные паттерны:
Чтобы разобраться, откуда берутся эти паттерны, вернемся еще раз к массивам. До этого мы использовали матрицы и массивы фиксированной длины. Попробуем немного изменить подход — длину будем увеличивать постепенно:
1. Создадим массив из n элементов.
2. Сделаем его копию.
3. Перемешаем копию с оригиналом с помощью Perfect Shuffle. Получили массив из n*2 элементов.
4. Вернемся к шагу 2.
Копию каждый раз будем инвертировать.
Начнем с массива из двух элементов — 1 и 0
10 — исходный массив
10, 01 — массив и инвертированная копия
0110 — смешали
0110, 1001 — массив и инвертированная копия
10010110
10010110, 01101001
0110100110010110
… и т.д.
Получили последовательность Морса — Туэ (A010060 [14]) — простейший фрактал!
И обратно к матрицам. Вот тут начинается чистое искусство. До этого мы делили матрицу на 4 части и перемешивали эти части. Попробуем копировать матрицу, производить над копиями некоторые элементарные действия и перемешивать оригинал с копиями.
С матрицами можем произвести 15 элементарных действий. Действие 0 — матрица без изменений. Действия 1-7 — разные способы вращения матрицы. Действия 8-15 — инвертирование. Наглядно:
В качестве примера, произведем над копиями действия 0, 0, 7, 7. Действие 7 — поворот матрицы на 90°.
Следующая итерация:
… восьмая итерация:
Очень необычный фрактал получился.
Действия 0, 0, 7, 7. Первая итерация:
Вторая итерация:
Восьмая:
А теперь два фокуса.
Накладываем сверху копию картинки с прозрачными белыми пикселями, копию поворачиваем на 90°:
Копия повернута по вертикали:
Комбинируя перечисленные действия, можно нарисовать 16^4=65536 фракталов. Некоторые из них:
Нарисованы за 6 итераций. Картинки кликабельны (8 итераций).
[15] [16] [17] [18] [19]
[20] [21] [22] [23] [24]
[25] [26] [27] [28] [29]
[30] [31] [32] [33] [34]
[35] [36] [37] [38] [39]
[40] [41] [42] [43] [44]
[45] [46]
А вот эти тянут на шедевр:
15, 5, 9, 5:
3, 5, 9, 5:
13, 7, 11, 11:
0, 0, 7, 13:
1, 1, 4, 14:
Другие фракталы можно нарисовать здесь [47]
Вот такие «карточные фокусы» получились. Думаю, на этом можно временно остановиться (можно перемешивать трехмерные матрицы, но об этом в другой раз).
Автор: xcont
Источник [48]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/267259
Ссылки в тексте:
[1] Image: https://habrastorage.org/webt/59/f0/cf/59f0cf89f1b4e665306730.png
[2] A002326: https://oeis.org/A002326
[3] Image: https://habrastorage.org/webt/59/f0/e1/59f0e1c990fb3737374018.png
[4] Image: https://habrastorage.org/webt/59/f0/e1/59f0e1c990f97715873297.png
[5] Image: https://habrastorage.org/webt/59/f0/e1/59f0e1c9bde68232362675.png
[6] Image: https://habrastorage.org/webt/59/f0/e1/59f0e1c9c71e3509409015.png
[7] Image: https://habrastorage.org/webt/59/f0/e1/59f0e1c9e7aa2672624583.png
[8] скрипт: http://xcont.com/perfectshuffle/
[9] первой своей статье: https://habrahabr.ru/post/194406/
[10] сюда: http://xcont.com/prch/1102.php
[11] Image: https://habrastorage.org/webt/59/f0/ed/59f0edf290363632758670.png
[12] z=sin(n*x/y): http://xcont.com/trigonometry/sin0.html
[13] z=sin(n*x*y): http://xcont.com/trigonometry/sin1.html
[14] A010060: https://oeis.org/A010060
[15] Image: https://habrastorage.org/webt/yj/uo/sc/yjuosc-1xbofan7ljbsmdn_r6bk.png
[16] Image: https://habrastorage.org/webt/q8/hk/ch/q8hkch58yggyoslmumvgmsap-fu.png
[17] Image: https://habrastorage.org/webt/sb/tr/3l/sbtr3lovc_oyjlau-unlnxcot8w.png
[18] Image: https://habrastorage.org/webt/qe/kn/h7/qeknh7wrs74pwkfnswnfavpswgu.png
[19] Image: https://habrastorage.org/webt/w7/35/ot/w735ot-afgjasrq415knube001a.png
[20] Image: https://habrastorage.org/webt/cb/hp/px/cbhppxwpf_3tbejn9vapaddr4ea.png
[21] Image: https://habrastorage.org/webt/sd/38/7c/sd387cfbbnqxjciwt3zgius4q7w.png
[22] Image: https://habrastorage.org/webt/yd/ih/xu/ydihxufowyeqmzqibd-1x_liwx4.png
[23] Image: https://habrastorage.org/webt/4w/jv/zp/4wjvzpl7yaomfdjn1tu44ly7my4.png
[24] Image: https://habrastorage.org/webt/fi/ho/se/fihosexcjqklk7n4_buqgxj4inm.png
[25] Image: https://habrastorage.org/webt/5y/-l/_u/5y-l_uhvtn_yupgnswbsdr_mrcm.png
[26] Image: https://habrastorage.org/webt/vg/9e/p3/vg9ep37a1tziz-oky_tkjosom4i.png
[27] Image: https://habrastorage.org/webt/8z/sn/ql/8zsnqli2rw-fhyp1ozaawgozx7a.png
[28] Image: https://habrastorage.org/webt/pv/r1/29/pvr129yfibfr2kuf942s3mdhing.png
[29] Image: https://habrastorage.org/webt/gj/tt/ev/gjttevk6w8nhzgsjynsj4ghx0u8.png
[30] Image: https://habrastorage.org/webt/uo/wt/d4/uowtd4nmem97qz0uwol9mp8msfk.png
[31] Image: https://habrastorage.org/webt/6k/fo/dr/6kfodroykxkxkm5d-j1kvwemoow.png
[32] Image: https://habrastorage.org/webt/qm/3i/zf/qm3izf_qjlk6hhz4tjeik03xku4.png
[33] Image: https://habrastorage.org/webt/zf/ef/9u/zfef9uf8kln0trlt7utu4shlc58.png
[34] Image: https://habrastorage.org/webt/js/k5/ft/jsk5ftpfllmgkiuyr6f-lqspzac.png
[35] Image: https://habrastorage.org/webt/4e/9d/eh/4e9dehxvyanraoej6muu6bkvhbc.png
[36] Image: https://habrastorage.org/webt/qd/ur/ne/qdurneay-fzlsts0d82oroasf4e.png
[37] Image: https://habrastorage.org/webt/rb/0u/k5/rb0uk5j-w3wj_v8vuh9wcqar2i8.png
[38] Image: https://habrastorage.org/webt/iw/cb/r8/iwcbr8lvesrz9d033cqqrl0fzq8.png
[39] Image: https://habrastorage.org/webt/gp/fr/ws/gpfrwsplmvauyr_5gq0vt5co7uw.png
[40] Image: https://habrastorage.org/webt/px/dj/q6/pxdjq6eh08ouykis08rffsyzweu.png
[41] Image: https://habrastorage.org/webt/rv/ly/hc/rvlyhcyxksevw3ocbgo6oj-ge9a.png
[42] Image: https://habrastorage.org/webt/5q/wv/y-/5qwvy-y-5aoez9lflla-b0ho36s.png
[43] Image: https://habrastorage.org/webt/lg/rn/oj/lgrnojyp4z9fmcxyuuwe2lefe4y.png
[44] Image: https://habrastorage.org/webt/qf/v7/bx/qfv7bxtbyhjbdj0ontou95n8a1y.png
[45] Image: https://habrastorage.org/webt/il/tu/uc/iltuuclhcbyos5zo99txnfizoy8.png
[46] Image: https://habrastorage.org/webt/oj/u3/wm/oju3wmfwvwxwcbcpsn1rqfxs2nu.png
[47] здесь: http://fractal.xcont.com/permutations.html
[48] Источник: https://habrahabr.ru/post/340964/
Нажмите здесь для печати.