Как перебрать все элементы множества в псевдо-произвольном порядке?

Question

[xmoonlight]

Есть произвольный пронумерованный набор элементов.
Например: 1,2,3,4,5
Как получить формулу для перебора всех элементов строго по одному разу (как-бы рандомно) и (по-возможности) с разными последовательностями с помощью управляющего коэффициента.

Например:
f(1) = {3,5,2,1,4}
f(2) = {5,3,1,4,2}
и т.д.

UPD: брут или стэк (достаём до опустошения) - не нужны!
Нужна именно формула (или где почитать), меняющая позиции элементов в зависимости от поданного на вход коэффициента.

UPD2: нашёл только лекцию по лексографическим перестановкам, но это совсем не то, что мне требуется.

PS: подобный вопрос - здесь.

Comments

[Сергей Соколов]

лексикографические перестановки - это алгоритм Нарайаны? Красивый.

[xmoonlight]

Сергей Соколов, ага, он самый.

[Сергей Соколов]

Похожий вопрос задавал сто лет назад: Как задать перемешивание массива относительно коротким числом параметров?

[Сергей Соколов]

Тогда же задавал его на SO, там хорошие советы.

[xmoonlight]

Сергей Соколов, Не хило... Надо потестить решение с взаимно-простым.

[Сергей Соколов]

xmoonlight, дополнил ответ тут. Из нескольких вариантов простого, у двух не проиходило перемешивания. Надо как-то проверять такие случаи.

Answer 1

[Сергей Соколов]

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

Вот пример кода:

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.

Comments

[xmoonlight]

Спасибо большое!
Я на основе этого - попробую реализовать до конца то, что мне нужно.
Если интересно - могу потом поделиться.

[Sumor]

17 это 1 по модулю 8, то есть умножение на 17 равно умножению на 1 и поэтому перемешивания не происходит.
Перемешивание с помощью одного умножения по модулю даёт линейное перемешивание, то есть элементы идут подряд или через равные промежутки.

Для полного понимания того, что происходит нужны небольшие знания из теории групп, а именно: понятие циклическая группа, порождающий элемент.

[longclaps]

Плохой рецепт.
Ты заметил, что все перестановки начинаются с 'a'? А еще их всего 8 - по числу остатков от деления на 8.
В таком виде это не лечится,

function shuffle(str, seed) {
    let src = str.split(''), res = [];
    for (let i = src.length; i > 0; i--) {
        res.push(src.splice(seed % i, 1));
        // так называемый минимальный стандартный генератор случайных чисел
        seed = seed * 16807 % 2147483647; // аккуратно, с нуля он не стартует )
    }
    return res.join('')
}

console.log(shuffle('abcdefgh', 42));

[xmoonlight]

longclaps, циклы - не айс...
я вот что подумал... может использовать просто смену разводки и Нарайану?

[longclaps]

xmoonlight, циклы норм. Вот код чуть поаккуратнее:

function shuffle(str, seed) {
    let arr = str.split(''), j;
    for (let i = 0; i < arr.length; i++) {
        j = (seed = seed * 16807 % 2147483647) % arr.length;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr.join('')
}

может использовать просто смену разводки и Нарайану

А что это?

[xmoonlight]

longclaps, UPD2 в тексте вопроса - линк там.
И, дополнительно, на выходе, перегрупироввывать (скоммутировать) элементы разными фиксированными способами через остаток от деления в зависимости от входного параметра.

[Sumor]

В продолжение темы небольшой код для перемешивания с помощью порождающего элемента.
Взято простое число 19. Для группы размером 19 порождающими являются числа 2, 3, 10, 13, 14, 15.
Например 2^1, 2^2, ... 2^19 даст все числа по одному разу.
0 в результате умножения не получается. 1 получается при возведении любого из этих чисел в 19 степень.

public static void Main()
	{
		var str = "abcdefghijklmnop";
		Console.WriteLine(str);
		Console.WriteLine(string.Concat(Shuffle(str)));
	}
	private static Random Rnd = new Random((int)DateTime.Now.Ticks);
	public static IEnumerable<char> Shuffle(string str)
	{
		var prime = 19;	
		var makers = new [] {2, 3, 10, 13, 14, 15};
		var maker = makers[Rnd.Next(makers.Length)];
		if(prime < str.Length + 2) throw new Exception("Слишком длинная строка");
		var current = maker;
		while(current != 1)
		{		
			if(current < str.Length + 2)
				yield return str[current - 2];
			current *= maker;
			current %= prime;			
		}
	}

[xmoonlight]

Sumor, мне нужно не перемешать и забыть, а нужно обратимое соответствие через формулу: 1 <=> перемешано так, 2 <=> перемешано сяк, и т.д.

[Sumor]

В данном случае для 19 есть 6 способов, по выбору порождающего элемента.

[xmoonlight]

Sumor, Спасибо, да. Разобрался. Отличный вариант!
А как находить порождающие числа?

[xmoonlight]

longclaps, Спасибо!
Оформи код в ответ - отмечу ответом. (про циклы - это по буквам, я не посмотрел!)

Answer 2

[longclaps]

function shuffle(str, seed) {
    let arr = str.split(''), j;
    for (let i = 0; i < arr.length; i++) {
        // так называемый минимальный стандартный генератор случайных чисел
        // https://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод
        // аккуратно, с нуля он не стартует )
        j = (seed = seed * 16807 % 2147483647) % arr.length;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr.join('');
}

console.log(shuffle('abcdefgh', 42));

Comments

[xmoonlight]

Спасибо!

[longclaps]

xmoonlight, да, про обратимость:

function mutators(size, seed) {
    let fw = Array(size);
    let bw = Array.from(fw.keys());
    for (let i = 0, j; i < size; i++) {
        j = (seed = seed * 16807 % 2147483647) % bw.length;
        [bw[i], bw[j]] = [bw[j], bw[i]];
    }
    bw.forEach((i, j) => fw[i] = j);
    return [fw, bw];
}

function shuffle(str, key) {
    key.forEach((i, j) => key[j] = str[i]);
    return key.join('');
}

let [enc, dec] = mutators(8, 42);
let s = shuffle('abcdefgh', enc);
let t = shuffle(s, dec);
console.log(s, t);

[xmoonlight]

longclaps, Супер!

PS: а смысл какой размер строки передавать в mutators(), а не саму строку, чтобы там же посчитать её длину и "прозрачно" вернуть в массив вместе с return [fw, bw, s];?
Ну или как-то, чтобы не путанно было...

[longclaps]

xmoonlight, ну да, лучше всё собрать в объект с двумя методами.

Answer 3

[Sumor]

Небольшой код для перемешивания с помощью порождающего элемента.
Математическое обоснование основано на теории групп.
Кратко:
В конечном поле, мощностью равному простому числу p есть мультипликативная группа, которая включает в себя все элементы кроме нуля.
В этой мультипликативной группе обязательно есть порождающий элемент.
Что такое порождающий элемент? Это элемент (a), который можно последовательно возводить в степень и получить все элементы мультипликативной группы, то есть все элементы нашего поля, кроме нуля. Причём единица получится всегда последней. a^(p-1) = 1 (mod p)
На том, что степени порождающего элемента проходят все элементы ровно по одному разу и построен предложенный алгоритм генерации перестановок. Он не годится для реальных дел, но в некоторых научных или ненаучных целях его можно использовать.
Нужно взять простое число большее как минимум на 2 максимальной длины строки.
0 в результате умножения не получается, а 1 будем считать признаком завершения подсчётов, элементы больше длины строки + 2 будем пропускать.
Для поиска порождающих элементов нужно разложить число (p-1) на множители. Если элемент a является порождающим, то возведение его в степени полученных множителей не должно равняться 1 по модулю p.
Как только один порождающий элемент найден, то порождающими будут его степени, взаимно простые с (p-1).

Для примера взял число 19. (19-1)=18=2*3*3
Проверяем число 2: 2^2 = 4≢1(mod p) 2^3 = 8≢1(mod p) - значит 2 - порождающий элемент.
Числа 1, 5, 7, 11, 13, 17 - взаимно простые с 18, поэтому 2^1, 2^5, 2^7, 2^11, 2^13, 2^17 - порождающие элементы
Это числа 2, 3, 10, 13, 14, 15. В данном случае у нас получится 6 вариантов перемешивания.
И теперь код:

public static void Main()
  {
    var str = "abcdefghijklmnop";
    Console.WriteLine(str);
    Console.WriteLine(string.Concat(Shuffle(str)));
  }
  private static Random Rnd = new Random((int)DateTime.Now.Ticks);
  public static IEnumerable<char> Shuffle(string str)
  {
    var prime = 19;	
    var makers = new [] {2, 3, 10, 13, 14, 15};
    var maker = makers[Rnd.Next(makers.Length)];
    if(prime < str.Length + 2) throw new Exception("Слишком длинная строка");
    var current = maker;
    while(current != 1)
    {		
      if(current < str.Length + 2)
        yield return str[current - 2];
      current *= maker;
      current %= prime;			
    }
  }

Comments

[xmoonlight]

Sumor, Спасибо Большое!
А в обратную сторону как это использовать?

Answer 4

[mayton2019]

Это называется генерация перестановок.

Comments

[xmoonlight]

Спасибо.
А не подскажете как получить общий вид формулы с одним типом перестановки для n-элементов?

[mayton2019]

Формулы скорее всего нет. Есть итеративный алгоритм. Все символы вращаются по кругу.
На 1 шаг. Потом из хоровода исключается 1-й символ. Вращаются все остальные. И так далее
пока хоровод не станет пустой.

Есть готовые имплементации этого алгортима на C++ STD. И на других языках разработки
в библиотеках коллекций.

[xmoonlight]

mayton2019, итеративно (это брут) - не интересует...

[mayton2019]

Я хочу вам сказать что существуют предметные области (шахматы) где не существуют прямой формулы расчета решения. Есть просто некая итеративность которую нужно последовательно исполнять до достижения цели. Например задачу 8 ферзей решал математик Гаусс. Он искал формульное решение но не нашел. Его просто не существует.

Поэтому я вас прошу - будьте более грамотны в формировании ваших желаний. И воздержитесь от радикальных заявлений что это брут или не брут. Может так оказаться что вращательный алгоритм будет единственным и примлемым для вашей задачи.

[xmoonlight]

mayton2019, он не мог построить модель и попытаться найти зависимости, т.к. у него не было выч. мощности. Есть или нет формульное решение у 8-ми ферзей - я точно не знаю.
Но эту задачку с циклами - я кодил лично очень давно и не задавался тогда этим вопросом.

То, что не существует возможности получения формулы при присутствии итеративной 100% логики - я, лично, сильно сомневаюсь.