Skip to content

Instantly share code, notes, and snippets.

@torjusti
Created May 23, 2017 22:23
Show Gist options
  • Save torjusti/c26449f802b141a66f736f8947173139 to your computer and use it in GitHub Desktop.
Save torjusti/c26449f802b141a66f736f8947173139 to your computer and use it in GitHub Desktop.
Bijection which maps repetition-less permutations to a single integer in a minimal range, given the number of affected pieces.
const getIndex = (permutation, affected) => {
const indexes = affected.map(i => permutation.indexOf(i));
if (affected.length === 1) {
return permutation.indexOf(affected[0]);
}
let base = permutation.length;
let index = indexes[indexes.length - 1];
for (let i = indexes.length - 2; i >= 0; i -= 1) {
for (let j = indexes.length - 1; j > i; j -= 1) {
if (indexes[i] > indexes[j]) {
indexes[i] -= 1;
}
}
index += base * indexes[i];
base *= 1 + permutation.length - indexes.length + i;
}
return index;
};
const getPermutation = (index, affected, size) => {
const permutation = [], indexes = [];
if (affected.length === 1) {
permutation[index] = affected[0];
return permutation;
}
const factor = 1 + size - affected.length;
let base = size;
for (let i = affected.length - 2; i >= 0; i -= 1) {
base *= factor + i;
}
for (let i = 0; i < affected.length - 1; i += 1) {
base /= factor + i;
let value = Math.floor(index / base);
let rest = index % base;
indexes.push(value);
if (i === affected.length - 2) {
indexes.push(rest);
}
index -= base * value;
}
for (let i = 0; i < indexes.length - 1; i += 1) {
for (let j = i + 1; j < indexes.length; j += 1) {
if (indexes[i] >= indexes[j]) {
indexes[i] += 1;
}
}
}
for (let i = 0; i < affected.length; i += 1) {
permutation[indexes[i]] = affected[i];
}
return permutation;
};
@torjusti
Copy link
Author

torjusti commented May 23, 2017

getIndex([2, 1, 3, 0, 4], [0, 1, 2, 3, 4]); // => 119 (guaranteed to be in the range [0, 5!>)
getPermutation(119, [0, 1, 2, 3, 4], 5); // [2, 1, 3, 0, 4]

Generally, the number of permutations is given by (number of pieces)!/(number of pieces - number of affected pieces)!.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment