0

Given the powerset of 1, 2, 3 I get 8 subsets: [], [1], [2], [2,1], [3], [3,1], [3,2], [3,2,1]. I would like to then generate the subsets of this new set which have exactly 1 of the original set.

The number of subsets in the powerset of my powerset is 256, but there are only 8 which only contain 1 each of "1", "2" and "3", these are:

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

Is there a way that I can get that final set without generating the second powerset with 256 subsets? I am looking for a way which can scale up to where the first set of 3 can have 10+ elements, so it isn't efficient to calculate the second powerset. Note that I don't actually require the cases where there is an empty array. My ideal answer would include only the first 5 elements. I may have pushed myself down the wrong rabbit hole by focusing on powersets. It solved my problems for n=7 but doesn't scale up to n=14.

This is the function that I currently have, but it falls over when there are 5 items in the array. I am likely approaching this from the wrong direction entirely.

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');
Toeler
  • 11
  • 2
  • You are looking for all ways to divide up the original set into subsets (where the empty subset is sometimes included), correct? – Scott Hunter Mar 29 '20 at 02:26
  • @ScottHunter Yes. Ideally I could get all possible ways to divide up the original set so that I can run each possibility through a scoring function to select the best one. For my concrete use case it would be that I wouldn't want any subset to have a sum greater than X and from those then I would pick the one that had the least difference between the sum and X. – Toeler Mar 29 '20 at 04:47
  • I believe you're looking for the partitions of the original set (https://stackoverflow.com/questions/20530128/how-to-find-all-partitions-of-a-set) – RaffleBuffle Mar 29 '20 at 14:34

1 Answers1

1

Thanks to @SirRaffleBuffle for the direction for the answer. The stackoverflow question How to find all partitions of a set was exactly what I was after.

I ported the accepted answer from that question https://stackoverflow.com/a/30903689/3972094 to Javascript which got me most of the way, I added a filter to let me constrain the partitions which lets it run on array sizes > 11 in reasonable time:

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));
Toeler
  • 11
  • 2