生成置换和原地求逆置换

perm.js

 const generatePerm = (len, rng) => {
    const result = new Array(len);
    for (let i = 0; i < len; i++) {
        result[i] = i;
    }
    for (let i = len - 1; i >= 0; i--) {
        const j = rng() % (i + 1);
        [result[i], result[j]] = [result[j], result[i]];
    }
    return result;
}

// https://stackoverflow.com/questions/31773203/#answer-37645001
const invertInplace = array => {
    const len = array.length;
    for (let i = 0; i < len; i++) {
        // 一个置换可以分成几个独立的小置换
        // 例如 [2, 0, 1, 4, 3, 5] 可以分成 0 -> 2 -> 1 -> 0 和 3 -> 4 -> 3 和 5 -> 5
        // 依次检查 0、1、2……所在的置换
        // 已经变成了逆置换，或是后面两种逆置换和置换完全相同的情况，则跳过
        let skip = false;
        for (let c = array[i]; c !== i; c = array[c]) {
            if (c <= i) {
                skip = true;
                break;
            }
        }
        if (skip) {
            continue;
        }

        // 对于以下置换
        // 0 -> 1 -> 2 -> 3 -> 0
        // 从 0 开始，注意 0 -> 1 -> 2 也就是 from -> to -> toNext
        // 先修改 1 -> ?  使置换变成 0 <-> 1    2
        // 然后将 1    2 --> 3 变成 1 <-- 2    3
        //       2    3 --> 0 变成 2 <-- 3    0
        //       3    0 <-> 1 变成 3 <-- 0 <- 1
        //       0 <- 1 <-- 3 变成……但是from回到置换的开始位置了，结束
        // 于是就得到了
        // 0 <- 1 <- 2 <- 3 <- 0
        let from = i;
        let to = array[i];
        do {
            // let toNext = array[to];
            // array[to] = from;
            // from = to;
            // to = toNext;
            // 实际上就是下面的解包赋值了
            [array[to], from, to] = [from, to, array[to]];
        } while (from !== i);
    }
};

const permLength = 128;
const perm = generatePerm(permLength, () => Math.random() * 0x7FFFFFFF | 0);

const permOriginal = perm.slice();
console.log(permOriginal);

console.time('invert');
invertInplace(perm);
console.timeEnd('invert');

const permInverted = perm.slice();
console.log(permInverted);

for (let i = 0; i < permLength; i++) {
    if (permInverted[permOriginal[i]] !== i) {
        throw new Error('Test failed');
    }
}