如何创建包含数组 1-n 数组项的所有组合的数组？

Question

我们有以下任务，将下面称为 passengerFlights 的数组（带有 passenger-id-keys 和航班数组的对象）转换为：

(1) 包含所有可能的乘客航班组合的数组：

预期输出：

[
    ["aaa", "ddd", "eee"],
    ["aaa", "ddd", "fff"],
    ["bbb", "ddd", "eee"],
    ["bbb", "ddd", "fff"],
    ["ccc", "ddd", "eee"],
    ["ccc", "ddd", "fff"]
]

和 (2) 规定可以有 任意数量的乘客。

以下是尝试首先解决此问题的三个航班的静态示例，尽管尚不清楚 (1) 创建包含所有可能组合的数组，以及 (2) 如何解决 2-n 要求，我们假设某种递归。

const passengerFlights = {
    777: [
        {
            _id: "aaa"
        },
        {
            _id: "bbb"
        },
        {
            _id: "ccc"
        }
    ],
    888: [
        {
            _id: "ddd"
        }
    ],
    999: [
        {
            _id: "eee"
        },
        {
            _id: "fff"
        }
    ],
};

const getGroupedFlights = (passengerFlights) => {

    let indexPointer = 0;
    const indexCounters = [0, 0, 0];
    const arr = [];
    while (indexCounters[0] <= passengerFlights['777'].length - 1 || indexCounters[1] <= passengerFlights['888'].length - 1 || indexCounters[2] <= passengerFlights['999'].length - 1) {
        arr.push([passengerFlights['777'][0]._id, passengerFlights['888'][0]._id, passengerFlights['999'][0]._id]);

        if (indexCounters[2] < passengerFlights['999'].length) indexCounters[2]++;
        if (indexCounters[2] >= passengerFlights['999'].length - 1 && indexCounters[1] < passengerFlights['888'].length) indexCounters[1]++;
        if (indexCounters[1] >= passengerFlights['888'].length - 1 && indexCounters[0] < passengerFlights['777'].length) indexCounters[0]++;

        console.log(indexCounters, passengerFlights['888'].length - 1);
    }
    return arr;
}

const groupedFlights = getGroupedFlights(passengerFlights);
console.log(groupedFlights);

Answer 1

这只是一个简单的递归问题....

const
  passengerFlights = 
    { 777: [ { _id: 'aaa' }, { _id: 'bbb' }, { _id: 'ccc' } ] 
    , 888: [ { _id: 'ddd' }                                 ] 
    , 999: [ { _id: 'eee' }, { _id: 'fff' }                 ] 
    } 
, result = combinations( passengerFlights, '_id' )
    ;

console.log( showArr(result) )

function combinations( obj, KeyName )
  {
  let 
    result = []
  , keys   = Object.keys(obj)  // [ "777", "888", "999" ]
  , max    = keys.length -1  
    ;
  f_recursif_combi(0)
  return result

  function f_recursif_combi( level, arr = [] )
    {
    obj[ keys[level] ]    // like :passengerFlights['777']
    .forEach( elm =>      
      {
      let arr2 = [...arr, elm[KeyName] ]; // arr + elm['_id']
      (level < max)
        ? f_recursif_combi(level +1, arr2 )
        : result.push( arr2 )
      })
    }
  }
  
// ************************************ just to present result...
function showArr(Arr)
  {
  const r = { '[["': `[ [ '`, '","': `', '`, '"],["': `' ]\n, [ '`, '"]]': `' ]\n]` }
  return JSON
      .stringify(result)
      .replace(/\[\[\"|\"\,\"|\"\]\,\[\"|\"\]\]/g,(x)=>r[x])
  }

.as-console-wrapper {max-height: 100%!important;top:0 }

Answer 2

我认为这是航班集的笛卡尔积。所以这应该有帮助： Cartesian product of multiple arrays in JavaScript

Answer 3

正如另一个答案所建议的那样，您可以使用基本的 笛卡尔积 函数。使用Object.values(passengerFlights)传入数组的数组。

function *product(arrs, p = []) {
  if (arrs.length == 0)
    yield p
  else
    for (const value of arrs[0])
      yield *product(arrs.slice(1), [...p, value])
}

const passengerFlights =
  {777: [{_id: "aaa"},{_id: "bbb"},{_id: "ccc"}],888: [{_id: "ddd"}],999: [{_id: "eee"},{_id: "fff"}]}

for (const p of product(Object.values(passengerFlights)))
  console.log(JSON.stringify(p.map(obj => obj._id)))

我在演示中使用了 JSON.stringify 以便于可视化

["aaa","ddd","eee"]
["aaa","ddd","fff"]
["bbb","ddd","eee"]
["bbb","ddd","fff"]
["ccc","ddd","eee"]
["ccc","ddd","fff"]

但对于您的程序，您可能更喜欢 Array.from

console.log(
  Array.from(
    product(Object.values(passengerFlights)),
    p => p.map(obj => obj._id)
  )
)

[
  ["aaa","ddd","eee"],
  ["aaa","ddd","fff"],
  ["bbb","ddd","eee"],
  ["bbb","ddd","fff"],
  ["ccc","ddd","eee"],
  ["ccc","ddd","fff"]
]

由于预期结果的顺序并不重要，我们可以使程序更高效。

function *product(arrs) {
  if (arrs.length == 0)
    yield []
  else
    for (const p of product(arrs.slice(1)))
      for (const value of arrs[0])
        yield [value, ...p]
}

const passengerFlights =
  {777: [{_id: "aaa"},{_id: "bbb"},{_id: "ccc"}],888: [{_id: "ddd"}],999: [{_id: "eee"},{_id: "fff"}]}

for (const p of product(Object.values(passengerFlights)))
  console.log(JSON.stringify(p.map(obj => obj._id)))

["aaa","ddd","eee"]
["bbb","ddd","eee"]
["ccc","ddd","eee"]
["aaa","ddd","fff"]
["bbb","ddd","fff"]
["ccc","ddd","fff"]

如何创建包含数组 1-n 数组项的所有组合的数组？

How create array containing all combinations of array 1-n array items?

javascript

algorithm

recursion