How to iterate over all elements of a set in a pseudo-arbitrary order?

Question

Mathematics

There is an arbitrary numbered set of elements.
For example: 1,2,3,4,5
How to get a formula for iterating over all elements exactly once (as if randomly) and (if possible) with different sequences using a control coefficient.

For example:
f(1) = {3,5,2,1,4}
f(2) = {5,3,1,4,2}
etc.

UPD: brute or stack (reach until empty) - not needed!
What is needed is a formula (or where to read), which changes the positions of the elements depending on the input coefficient.

UPD2: I found only a lecture on lexographic permutations, but this is not at all what I need.

PS: a similar question is here .

Answer 1

When the length of the set is a multiple of powers of two, you can shuffle the bits addressing the element.
Within the framework of one order of mixing address bits, the entire set of elements is uniquely (“ bijectively ”) mapped to the same “mixed” set in length.
Here is an example code:

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. This method does not exhaust all possible permutations, limiting itself to a small part of them. The first and last always remain in their places (all "0" no matter how you mix it ..)
Upd. a great way suggested on SO. When the length of the array is N, one should take any prime number greater than N. It is guaranteed to be coprime with any of the numbers less than.
The new address of the element is obtained from the old one: multiply the address by a prime and take the remainder of the division by the length.

{
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

For some prime numbers, for some reason, there is no mixing: for 17, 37 with an array length of 8.

Answer 2

This is called permutation generation.