Генерация всех комбинаций подмножеств, которые содержат точно элементы в исходном наборе - PullRequest
Новая
       95

Генерация всех комбинаций подмножеств, которые содержат точно элементы в исходном наборе

0 голосов
/ 29 марта 2020

Учитывая мощность набора 1, 2, 3, я получаю 8 подмножеств: [], [1], [2], [2,1], [3], [3,1], [3,2], [3,2,1]. Затем я хотел бы сгенерировать подмножества этого нового набора, которые имеют ровно 1 исходного набора.

Количество подмножеств в powerset моего powerset равно 256, но есть только 8, которые содержат только 1 каждый из "1", "2" и "3", это: 

[
  [
    [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 подмножествами? Я ищу способ, который можно масштабировать до уровня, где первый набор из 3 может иметь более 10 элементов, поэтому неэффективно рассчитывать второй набор мощности. Обратите внимание, что я на самом деле не требую случаев, когда есть пустой массив. Мой идеальный ответ будет включать только первые 5 элементов. Возможно, я толкнул себя не в ту кроличью нору, сосредоточившись на powersets. Он решил мои проблемы для 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');

1 Ответ

1 голос
/ 30 марта 2020

Спасибо @SirRaffleBuffle за направление для ответа. Вопрос stackoverflow Как найти все разделы набора был именно таким, каким я был.

Я перенес принятый ответ на этот вопрос { ссылка } на 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));
...