Javascript алгоритм для генерации всех возможных уникальных комбинаций любой длины под-массивов в массиве - PullRequest
Новая
       12

Javascript алгоритм для генерации всех возможных уникальных комбинаций любой длины под-массивов в массиве

3 голосов
/ 19 февраля 2020

У меня есть массив с вложенными массивами, и мне нужен алгоритм, который генерирует все возможные уникальные комбинации вложенных массивов. Результирующие комбинации могут быть любой длины. Например, если у массива есть 4 подмассива, первый подмассив сам по себе будет уникальной и действительной результирующей комбинацией, как и любая другая уникальная комбинация любой длины.

Комбинация с субэлементом Массив одинаковых предметов в другом порядке не будет считаться уникальным. 

let mainArray = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]]

//Valid Resultant Combinations
[[0.3, 1]]
[[0.3, 1], [0.5, 2]]
[[0.3, 1], [0.5, 2], [0.6, 3]]
[[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]]
[[0.5, 2]]
[[0.5, 2], [0.6, 3]]
[[0.5, 2], [0.6, 3], [0.3, 4]]
[[0.6, 3]]
[[0.6, 3], [0.3, 4]]
[[0.3, 4]]
[[0.3, 1], [0.6, 3], [0.3, 4]]
[[0.3, 1], [0.5, 2], [0.3, 4]]
[[0.3, 1], [0.3, 4]]
[[0.3, 1], [0.6, 3]]
[[0.5, 2], [0.3, 4]]

//Don't think i missed any..

Ответы [ 3 ]

3 голосов
/ 19 февраля 2020

Для более удобной обработки вы можете взять массив индексов и написать код для получения всех комбинаций.

Позже вы можете заменить массив индексами на реальные значения.

Этот подход работает с отказом, который хранит массив собранных предметов и индекс, который указывает на переданный массив.

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

Следующая часть снова вызывает функцию с явно собранным значением и новым значением из массива и увеличенным индексом и с другой вызов только с измененным индексом (здесь фактический элемент не используется). 

function getCombinations(array) {
    function iter(temp, index) {
        if (index >= array.length) {
            result.push(temp);
            return;
        }

        iter([...temp, array[index]], index + 1);
        iter(temp, index + 1);
    }
    
    var result = [];
    iter([], 0);
    return result;
}

let array = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]];

console.log('indices')
getCombinations([...array.keys()]).forEach(a => console.log(...a));
console.log('arrays')
getCombinations(array).forEach(a => console.log(...a.map(b => JSON.stringify(b))));
.as-console-wrapper { max-height: 100% !important; top: 0; }
0 голосов
/ 20 февраля 2020

Вот еще один подход: 

function combinations(array) {
  const results = [];
  for (let item of array) {
    // take every result that is in the results yet, 
    const withItem = results.map(row => [...row, item]);
    // add that result + the current item
    results.push(...withItem);
    // also add just the current item
    results.push([item]);
  }
  return results;
}

или вот так: 

const values = [1,2,3,4];

function combinations(array) {
  return array.reduce((results, item) => [...results, ...results.map(row => [...row, item]), [item]], []);
}

console.log(combinations(values).join("\n"));
.as-console-wrapper{top:0;max-height:100%!important}
0 голосов
/ 19 февраля 2020

Алгоритм будет основан на следующих логиках c. Сколько всего возможных под-массивов существует? I. Давайте рассмотрим, что есть только один элемент: (_) Итак, первый подмассив -> Я не выбираю элемент. Второй массив -> Я выбираю предмет. Что означает два подмассива. II. Давайте рассмотрим, что есть два элемента: (_) (_) Итак, первый суб-массив -> Я не выбираю 1-й элемент. Я выбираю 2-й элемент. Второй массив -> Я выбираю 1-й предмет. Я выбираю 2-й предмет. Итак, первый суб-массив -> я не выбираю второй элемент. Я не выбираю первый элемент. Второй массив -> Я выбираю 2-й предмет. Я выбираю 1-й предмет. Что означает 4 суб-массива.

Таким образом, я могу обобщить это, в каждой позиции, я могу выбрать это или нет. Что означает два значения на позицию. Таким образом, для n элементов -> 2x2x ..... 2 (n раз) или 2 n

Итак, для трех элементов мы можем найти решение для трех элементов: 

    |Item1|Item2|Item3|     |Item1|Item2|Item3|
    ___________________     ___________________
    |  ✘  |  ✘  |  ✘  |  or |  0  |  0  |  0  |
    |  ✘  |  ✘  |  ✔  |  or |  0  |  0  |  1  |
    |  ✘  |  ✔  |  ✘  |  or |  0  |  1  |  0  |
    |  ✘  |  ✔  |  ✔  |  or |  0  |  1  |  1  |
    |  ✔  |  ✘  |  ✘  |  or |  1  |  0  |  0  |
    |  ✔  |  ✘  |  ✔  |  or |  1  |  0  |  1  |
    |  ✔  |  ✔  |  ✘  |  or |  1  |  1  |  0  |
    |  ✔  |  ✔  |  ✔  |  or |  1  |  1  |  1  |
Так что, если мы выполним от 0 до (2
n - 1), преобразуем в двоичный файл и видим показ единственного элемента, который соответствует единицам, а не нулям.

Псевдокод будет быть примерно таким: 

n -> list.length dummyList -> [] for i:0 to 2^n-1
    dummy2 -> []
    toBinary -> binary(i)
    for j: 0 to n-1
        if toBinary[j] equals 1
           insert list[j] to dummy2
    insert dummy2 to dummyList

Сложность времени = nx 2 n 

function allSubs(list){
    let len = list.length;
    let lenraisedtoTwo = 1<<len;
    let nwArr = Array(lenraisedtoTwo).fill().map((_,idx)=>list.filter(($,ind)=>idx.toString(2).padStart(len)[ind]==="1"))
    return nwArr
}
abc.innerText = JSON.stringify(allSubs([1,2,3]))
<div id="abc">This div contains the result for all possible combinations</div>
...