Поиск групп элементов в массиве, которые укладываются в границы - PullRequest
Новая
       66

Поиск групп элементов в массиве, которые укладываются в границы

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

Учитывая входной массив, я пытаюсь сгенерировать массив возможных способов их размещения, если их длина меньше требуемой длины, например, 1800.

Пример ввода: 

[{length: 500}, {length: 800}, {length: 450}, {length: 650}, {length: 550}, {length: 500}, {length: 600}]

У меня есть следующий рабочий код, но он недостаточно эффективен для работы с большими массивами. Я получаю результат по 4 или 5 элементам, но поражаю лимиты памяти с помощью 7. В идеале я пытаюсь оптимизировать это так, чтобы он возвращал массивы до 15 элементов. У меня такое ощущение, что мой подход с использованием powerset просто слишком обременителен, когда есть какой-то другой способ получить результат с помощью гораздо более простого алгоритма. 

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, maxLength) {
    const subsets = getPowerset(arr).filter((subset) => subset.reduce((sum, part) => sum += part.length, 0) <= maxLength);
    const subsetsOfSubsets = getPowerset(subsets);
    return subsetsOfSubsets.filter((subset) => {
        const flattened = subset.flat();
        if (flattened.length !== arr.length) {
            return false;
        }
        const 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('4 length');
console.log(getCombinationsOfSet([{length: 500}, {length: 800}, {length: 450}, {length: 650}], 1800));
console.timeEnd('4 length');
console.time('5 length');
console.log(getCombinationsOfSet([{length: 500}, {length: 800}, {length: 450}, {length: 650}, {length: 550}], 1800)); // Slower
console.timeEnd('5 length');
console.time('7 length');
console.log(getCombinationsOfSet([{length: 500}, {length: 800}, {length: 450}, {length: 650}, {length: 550}, {length: 500}, {length: 600}], 1800)); // Too slow
console.timeEnd('7 length');

Результат для ввода 4: 

[
  [
    [{"length": 650}],
    [{"length": 450}],
    [{"length": 800}],
    [{"length": 500}]
  ],
  [
    [{"length": 650}],
    [{"length": 450}],
    [{"length": 800},{"length": 500}]
  ],
  [
    [{"length": 650}],
    [{"length": 450},{"length": 500}],
    [{"length": 800}]
  ],
  [
    [{"length": 650}],
    [{"length": 450},{"length": 800}],
    [{"length": 500}]
  ],
  [
    [{"length": 650}],
    [{"length": 450},{"length": 800},{"length": 500}]
  ],
  [
    [{"length": 650},{"length": 500}],
    [{"length": 450}],
    [{"length": 800}]
  ],
  [
    [{"length": 650},{"length": 500}],
    [{"length": 450},{"length": 800}]
  ],
  [
    [{"length": 650},{"length": 800}],
    [{"length": 450}],
    [{"length": 500}]
  ],
  [
    [{"length": 650},{"length": 800}],
    [{"length": 450},{"length": 500}]
  ],
  [
    [{"length": 650},{"length": 450}],
    [{"length": 800}],
    [{"length": 500}]
  ],
  [
    [{"length": 650},{"length": 450}],
    [{"length": 800},{"length": 500}]
  ],
  [
    [{"length": 650},{"length": 450},{"length": 500}],
    [{"length": 800}]
  ]
]

В худшем случае наибольшее количество групп будет иметь один элемент. Но, как вы можете видеть, есть ситуации, когда мы можем сгруппировать 2 или 3 элемента в группу и иметь длину менее 1800. Если это поможет, я могу добавить искусственный предел не более 4 элементов в группе, так как есть мало шансов с моими текущими входами, что это было бы возможно. Хотя в идеале это ограничение не должно играть роль.

...