combinations_replacement.js

/**
 * 实现[组合](https://en.wikipedia.org/wiki/Combination)的替换版本
 * 组合是集合的唯一子集 - 在此情况下，每次从集合中选取 k 个元素。
 * '替换'意味着一个给定的元素可以被多次选择。
 * 与排列不同，组合不关心顺序。
 *
 * @param {Array} x 任意类型的数据
 * @param {int} k 每组对象的数量（允许重复）
 * @returns {Array<Array>} 组合的数组
 * @example
 * combinationsReplacement([1, 2], 2); // => [[1, 1], [1, 2], [2, 2]]
 */
function combinationsReplacement(x, k) {
    const combinationList = [];

    for (let i = 0; i < x.length; i++) {
        if (k === 1) {
            // 如果仅需选择一个元素，则无需递归：
            // 直接将 `x[i]` 推入组合列表。
            combinationList.push([x[i]]);
        } else {
            // 否则，递归地寻找组合，指定 `k - 1`。注意，
            // 我们请求的是 `k - 1`，因此如果需要 k=3 的组合，
            // 则请求 k=2。在后续的循环中，这一减一操作会被逆转，
            // 因为我们会将 `x[i]` 连接到选定的组合上，使 k 恢复到请求的值。
            // 此递归可能会深入多层，因为它仅在 k=1 时停止。
            const subsetCombinations = combinationsReplacement(
                x.slice(i, x.length),
                k - 1
            );

            for (let j = 0; j < subsetCombinations.length; j++) {
                combinationList.push([x[i]].concat(subsetCombinations[j]));
            }
        }
    }

    return combinationList;
}

export default combinationsReplacement;