如何創建包含陣列1-n陣列項的所有組合的陣列？

我們有以下任務，將下面呼叫的陣列passengerFlights（帶有乘客 ID 鍵和航班陣列的物件）轉換為：

(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);

uj5u.com熱心網友回復：

這只是一個簡單的遞回問題......

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 }

uj5u.com熱心網友回復：

我認為這是航班集的笛卡爾積。所以這應該會有所幫助： JavaScript 中多個陣列的笛卡爾積

uj5u.com熱心網友回復：

正如另一個答案所暗示的，您可以使用基本的笛卡爾積函式。用于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"]
]

Since the order of the expected result is not important, we can make the program more efficient.

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"]

標籤：javascript 算法 递归

上一篇：如果只能洗掉葉子，則洗掉二叉樹的方法數

下一篇：將元素添加到不可變矢量rust