从数组中生成所有不同的、非空的子数组，并保留顺序

Question

我有一个数组和子数组，需要一种算法来生成子数组的所有可能的不同组合。生成的组合可以是任意长度。例如，如果数组有 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.

Answer 1

为了更方便的处理，您可以采用索引数组并编写获取所有组合的代码。

稍后，您可以用实际值替换索引数组。

此方法与 recusion 一起使用，recusion 保留收集的项目数组和指向移交数组的索引。

开始时，您有一个标准的退出条件，它会检查索引是否大于可能的值并将收集的值添加到结果集中。

以下部分使用先前收集的值和数组中的新值以及递增的索引再次调用该函数，并使用另一个仅更改索引的调用（此处未使用实际项目）。

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; }

Answer 2

The algorithm would be based on the following logic. How many total possible sub-arrays exist? I. Let us consider there is only one item: ( _ ) So first sub array -> I don't pick the item. Second array -> I pick the item. Which means two sub arrays. II. Let us consider there are two items: ( _ ) ( _ ) So first sub array -> I don't pick the 1st item.I pick the 2nd item. Second array -> I pick the 1st item.I pick the 2nd item. So first sub array -> I don't pick the 2nd item.I don't pick the 1st item. Second array -> I pick the 2nd item.I pick the 1st item. Which means 4 sub arrays.

So I can generalise this, at each position, I can either pick it or not. Which means two values per position. So for n items -> 2x2x.....2 (n times) or 2ⁿ

So for three items, here's how we can work out a solution for three items :
    |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  | 
So if we run from 0 to (2ⁿ - 1), convert to binary and see show the only item which matches the ones, and not the zeros.

The pseudocode would be something like this:
 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 
Time complexity = n x 2ⁿ

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>

Answer 3

这是另一种方法：

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}

从数组中生成所有不同的、非空的子数组，并保留顺序

From array, generate all distinct, non-empty subarrays, with preserved order

javascript

arrays

multidimensional-array

set

combinatorics