时间戳

首页 > 解决方案 > 生成完全包含原始集合中元素的所有子集组合

javascript - 生成完全包含原始集合中元素的所有子集组合

问题描述

给定1, 2, 3我得到 8 个子集的幂集：[], [1], [2], [2,1], [3], [3,1], [3,2], [3,2,1]. 然后我想生成这个新集合的子集，它们正好是原始集合的 1 个。

我的 powerset 的 powerset 中的子集数量为 256，但只有 8 个，其中“1”、“2”和“3”中的每个仅包含 1 个，它们是：

[
  [
    [1,2,3]
  ],
  [
    [2,3],[1]
  ],
  [
    [2],[1,3]
  ],
  [
    [3],[1,2]
  ],
  [
    [3],[2],[1]
  ],
  [
    [],[2],[1,3]
  ],
  [
    [],[3],[1,2]
  ],
  [
    [],[3],[2],[1]
  ]
]

有没有一种方法可以在不生成具有 256 个子集的第二个 powerset 的情况下获得最终集？我正在寻找一种可以扩展到第一组 3 个可以有 10+ 个元素的方法，因此计算第二个 powerset 效率不高。请注意，我实际上并不需要有空数组的情况。我的理想答案只包括前 5 个元素。通过专注于 powerset，我可能把自己推到了错误的兔子洞里。它解决了我的 n=7 问题，但没有扩展到 n=14。

这是我目前拥有的功能，但是当数组中有 5 个项目时它会失败。我很可能完全从错误的方向来解决这个问题。

function getPowerset(arr) {
    return (function ps(list) {
        if (list.length === 0) {
            return [
                []
            ];
        }
        const head = list.pop();
        const tail = ps(list);
        return [...tail, ...tail.map((e) => [head, ...e])];
    })([...arr]).filter(x => x.length);
}

function getCombinationsOfSet(arr) {
    const subsets = getPowerset(arr);
    const subsetsOfSubsets = getPowerset(subsets);
    return subsetsOfSubsets.filter((subset) => {
        const flattened = subset.flat();
        if (flattened.length !== arr.length) {
            return false;
        }
        let tempArr = [...arr];
        for (let part of flattened) {
            const index = tempArr.indexOf(part);
            if (index === -1) {
                return false;
            }
            tempArr.splice(index, 1);
        }
        return true;
    })
}

console.time('time-taken');
console.log(getCombinationsOfSet([1, 2, 3]));
console.timeEnd('time-taken');

标签： javascriptcombinationspermutationpowerset

解决方案

感谢@SirRaffleBuffle 提供答案的方向。stackoverflow 问题How to find all partitions of a set正是我所追求的。

我将该问题https://stackoverflow.com/a/30903689/3972094中已接受的答案移植到了 Javascript，这让我大部分时间都得到了帮助，我添加了一个过滤器来让我限制分区，让它在数组大小 > 11 上运行在合理的时间内：

function getAllPartitions(fixedParts, suffixElements, filter) {
    let partitions = [];
    if (filter(suffixElements)) {
        partitions.push(fixedParts.concat([suffixElements]));
    }

    const suffixPartitions = getTuplePartitions(suffixElements).filter(x => filter(x.fixedPart));
    for (const suffixPartition of suffixPartitions) {
        const subPartitions = getAllPartitions(fixedParts.concat([suffixPartition.fixedPart]), suffixPartition.suffixPart, filter);
        partitions = partitions.concat(subPartitions);
    }
    return partitions;
}

function getTuplePartitions(elements) {
    if (elements.length < 2) {
        return [];
    }

    const partitions = [];
    for (let pattern = 1; pattern < 1 << (elements.length - 1); pattern++) {
        const resultSets = [[elements[0]], []];

        for (let index = 1; index < elements.length; index++) {
            resultSets[( pattern >> (index - 1)) & 1].push(elements[index]);
        }

        partitions.push({fixedPart: resultSets[0], suffixPart: resultSets[1]});
    }

    return partitions;
}

function sumPart(part) {
    return part.reduce((sum, n) => sum += n, 0)
}

getAllPartitions([], [1, 2, 3, 4, 5], (part) => sumPart(part) <= 7).map(x => JSON.stringify(x));

推荐阅读