Когда длина набора кратна степеням двойки можно перемешивать биты, адресующие элемент.
В рамках одного порядка перемешивания битов адреса, все множество элементов однозначно («
биективно») отображается в такое же по длине «перемешанное» множество.
Вот пример кода:
const src = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; // массив элементов
const key = [2, 1, 0]; // номера битов для перемешивания адреса
const mapIndex = (n, key) => key.reduce((p,c,i) => p | ((1 << c & n) >> c) << i, 0);
const biject = (arr, key) => arr.map((e,i) => arr[mapIndex(i, key)]);
console.log( JSON.stringify(biject(src, key)));
// ["a","e","c","g","b","f","d","h"]
console.log( JSON.stringify(biject(src, [1,2,0])));
// ["a","e","b","f","c","g","d","h"]
Disclaimer. Этот способ не исчерпывает все возможные перестановки, ограничиваясь их небольшой частью. Первый и последний всегда остаются на своих местах (все "0" как ни перемешивай..)
Upd. отличный способ
подсказали на SO. Когда длина массива N, нужно взять любое простое число больше N. Оно гарантированно будет взаимнопростым с любым из чисел меньше.
Новый адрес элемента получается из старого: адрес умножить на простое и взять остаток от деления на длину.
{
const src = 'abcdefgh'.split('');
const N = src.length; // 8
const Prime = 37; // Prime > N
const mapIndex = (i, N, Prime) => (i * Prime) % N;
//for(let i = 0; i< 8; i++) console.log(i, mapIndex(i, N, Prime))
const shuffle = (str, Prime) => str.split('').map((e,i,a) => a[mapIndex(i, a.length, Prime)]).join('');
console.log( shuffle('abcdefgh', 17));
console.log( shuffle('abcdefgh', 19));
console.log( shuffle('abcdefgh', 23));
console.log( shuffle('abcdefgh', 29));
abcdefgh // не перемешалось
adgbehcf
ahgfedcb
afchebgd
Для некоторых простых чисел почему-то не происходит перемешивания: для 17, 37 при длине массива 8.
