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

Question

We have the following task, to convert the array below called passengerFlights (object with passenger-id-keys and array of flights) to:

(1) an array with all possible combination of passenger-flights:

EXPECTED OUTPUT:

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

and (2) with the stipulation that there can be any number of passengers.

The following is an attempt to solve this first as a static example of three flights, although it's not clear the best way to (1) create the array with all possible combinations, and (2) how to solve the 2-n requirement, we assume recursion of some kind.

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

What is your expected output meant to look like? Where do `777` and `888` come into the equation? — Andy, Feb 17 '22 at 22:53
Expected output is shown in first code block: `[["aaa", "ddd", "eee"],["aaa", "ddd", "fff"],...`. Yeah, the 777, 888 are the hard-coded passenger ids (our attempted solution is admittedly primitive), ultimately these ids would have to be dynamic, e.g. gotten from iteration. — Edward Tanguay, Feb 17 '22 at 23:02
We (simply) want an array containing all possible combinations of these flights. Each flight is identified with an `_id`. — Edward Tanguay, Feb 17 '22 at 23:05
No, order of expected result is not important. We just need the array of passenger-flight combinations, which we can reorder later before we send it to the front end. — Edward Tanguay, Feb 18 '22 at 00:04
No, passengerFlights can have any number of objects, i.e. passengers with arrays of possible flights. — Edward Tanguay, Feb 18 '22 at 00:05
Does this answer your question? [Cartesian product of multiple arrays in JavaScript](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) — yjay, Feb 18 '22 at 02:19

Mister Jojo · Accepted Answer · 2022-02-18T05:22:42.990

It's just a simple recursive problem....

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 }

score 0 · Answer 2 · answered Feb 18 '22 at 02:15

0

I think it's the Cartesian product of flights sets. So this should help: Cartesian product of multiple arrays in JavaScript

answered Feb 18 '22 at 02:15

yjay

942
4
11

よつば · Answer 3 · 2022-02-18T03:53:07.890

As another answer suggests, you can use a basic cartesian product function. Use Object.values(passengerFlights) to pass in the array of arrays.

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

I used JSON.stringify for easy visualization in the demo

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

But for your program you will probably prefer 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"]

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

3 Answers3