Как перемешать массив одинаково для всех?

Question

[Extramezz]

У нас есть массив (к примеру) [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]. И есть число, к примеру 12837823632, оно периодически меняется (я получаю его с сервера).

Мне нужно на клиенте перемешивать этот массив, опираясь на данное число. Так, чтобы если сайт открыт на 10 устройствах - результат перемешивания отобразился одинаковый. К примеру, [1, 2, 1, 3, 3, 2, 1, 1, 2, 3, 3, 2, 2, 1, 3]. Но при этом результат должен быть уникальным, не таким каким был с предыдущим числом.

Если использовать Math.random(), то, разумеется, результат будет на всех устройствах разный.

В какую сторону копать?

Answer 1

[Vitaliy]

https://github.com/skratchdot/random-seed

Comments

[Extramezz]

На nodejs все четко, а если в браузере запускать, то результат всегда примерно [1,1,1,,1,1,1,2,1,1,2,2,2,2,2,2,3,2,2,2,2,2,3,3,3,3,3,3,1]

Answer 2

[twobomb]

Псевдорандом

let arr = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3];
var seed = 12837823631;
arr = arr.sort((a,b)=>rand() - rand());

function rand(){
 	seed = (45 * seed + 21) % 67;
 	return seed/67;
}

Comments

[Wataru]

Во-первых, не надо сортировке выдавать самопротиворечивую функцию сравнения.
Она и в O(N^2) может запросто скатиться, а то и повиснуть. И может выдавать разные результаты при одинаковых входных данных:

compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined.

Во-вторых, раз уж у вас есть rand() с seed, то можно перемешать массив вот этим стандартным методом, что 100% быстрее и без возможных спец-эффектов:

for (i = 1; i<arr.length; ++i) {
 let j = floor(rand()*(i+1));
 let tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}

[Aetae]

Более того: в разных браузерах - алгоритмы сортировки могут быть вообще разные. Второй раз за сегодня натыкаюсь на вредные советы от twobomb. Диверсант какой-то.)

[twobomb]

Aetae, сортировку я так прикрутил первое что пришло в голову, лень код писать. Тут основное функция rand, которую я тоже вытащил из какого-то своего скрипта на Jsfiddle даже значения впадлу менять было.

Answer 3

[Wataru]

Вот алгоритм для перемешивания массива, если у вас есть детерминированная функция rand(), которую вы каким-то seed проинициализровали.

for (i = 1; i<arr.length; ++i) {
 let j = floor(rand()*(i+1));
 let tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}

Можно использовать что-то вроде функции, предложенной twobomb, но именно той функцией пользоваться не советую - она выдаст максимум 67 различных вариантов, а на самом деле сильно меньше. Используйте, например, параметры отсюда:

function rand(){
 	seed = (16,807*seed) % 2,147,483,647;
 	return seed/2,147,483,647;
}

Comments

[twobomb]

Да хоть 10 вариантов, этого достаточно чтобы перемешать массив

[Wataru]

twobomb, Что уж там, тогда делайте просто function rand() {return 0;} Тоже в некотором смысле перемешано будет. Хоть вариант и всего один будет.

Но в вопросе указано:

Но при этом результат должен быть уникальным, не таким каким был с предыдущим числом.

Это вообще сложно гарантировать с использованием псевдослучайного генератора. Но в вашем примере будет всего 67 перестановок (может и меньше), несмотря на то, что seed может принимать очень много значений и перестановок возможных очень много. Вряд ли это удовлетворительное решение.

Answer 4

[xmoonlight]

Я задавал похожий вопрос.
Посмотрите.