permutations_heap.js

/**
 * [Heap算法](https://en.wikipedia.org/wiki/Heap%27s_algorithm)的实现，
 * 用于生成排列。
 *
 * @param {Array} elements 任意类型的数据
 * @returns {Array<Array>} 排列的数组
 */
function permutationsHeap(elements) {
    const indexes = new Array(elements.length);
    const permutations = [elements.slice()];

    for (let i = 0; i < elements.length; i++) {
        indexes[i] = 0;
    }

    for (let i = 0; i < elements.length; ) {
        if (indexes[i] < i) {
            // 在奇数索引处，从indexes[i]开始交换，
            // 而不是从数组的开头交换
            let swapFrom = 0;
            if (i % 2 !== 0) {
                swapFrom = indexes[i];
            }

            // 在swapFrom和i之间交换，使用
            // 一个临时变量作为存储
            const temp = elements[swapFrom];
            elements[swapFrom] = elements[i];
            elements[i] = temp;

            permutations.push(elements.slice());
            indexes[i]++;
            i = 0;
        } else {
            indexes[i] = 0;
            i++;
        }
    }

    return permutations;
}

export default permutationsHeap;