How to get all possible combinations of multiple lists with different indexes only in javascript?

Frinch87
February 16, 2024
146 views
0 votes
2 Answers

Let’s pretend I have the following lists:

const list1 = [1,2,3,4,5]
const list2 = [6,7,8,9,10]
const list3 = [11,12,13,14,15]
const list4 = [16,17,18,19,20]

How do I get all possible combinations but only with different indexes?

So for example the result [1,6,11,16] wouldn’t work.

I would need all combinations like:

[1, 2, 3, 4, 5],
[1, 2, 3, 4, 10],
[1, 2, 3, 9, 5].
[1, 2, 3, 9, 10],
[1, 2, 8, 4, 5],
[1, 2, 8, 9, 5],
[1, 2, 8, 4, 10],
[1, 2, 8, 9, 10],
...
[6, 2, 3, 4, 5], 
[6, 2, 13, 14, 20]

and so on…

So index of each list, must only be used once.
You can’t use value of list1[0] and of another list index[0].

Answers

one way I can think of is like this to generate possible combination

function getUniqueIndexCombinations(...lists) {
  const results = [];

  function generateCombinations(currentIndex, combination) {
    if (currentIndex === lists.length) {
      results.push(combination);
      return;
    }

    for (let i = 0; i < lists[currentIndex].length; i++) {
      const newItem = lists[currentIndex][i];
      const newCombination = [...combination, newItem];
      generateCombinations(currentIndex + 1, newCombination);
    }
  }

  generateCombinations(0, []);
  return results;
}

const list1 = [1, 2, 3, 4, 5];
const list2 = [6, 7, 8, 9, 10];
const list3 = [11, 12, 13, 14, 15];
const list4 = [16, 17, 18, 19, 20];

const combinations = getUniqueIndexCombinations(list1, list2, list3, list4);
console.log(combinations);

This appears to solve what you want.

// Using a generator because this can yield a lot of values. Making an array
// from a generator is easy, and generator results can be fetched one after the other,
// reducing memory load.
function* generateIndexCombinations(...lists) {
  // Fetch how many cell we needs in our results.
  const size = Math.max(...lists.map(l => l.length));

  // Using a helper so we can add the index parameter. We could also do by
  // slicing the lists, but this would have much larger memory footprint.
  function* doGenerate(lists, index, acc) {
    // Recursion end case.
    if (index >= size) {
      yield acc;
      return;
    }

    for (const list of lists) {
      if (list.length > index) {
        // For each remaining list, create a copy of acc including the index value.
        const newAcc = [...acc, list[index]];
        // Generate the combinations of the tail to be added in acc and re-yield them.
        yield* doGenerate(lists, index + 1, newAcc)
      }
    }
  }
  yield* doGenerate(lists, 0, []);
}



const list1 = [1, 2, 3, 4, 5];
const list2 = [6, 7, 8, 9, 10];
const list3 = [11, 12, 13, 14, 15];
const list4 = [16, 17, 18, 19, 20];

const table = document.querySelector('table');

// Option 1: get each combination one after the other.
for(let c of generateIndexCombinations(list1, list2, list3, list4)) {
  const tr = document.createElement('tr');
  for (let v of c) {
    const td = document.createElement('td');
    td.textContent = v;
    tr.appendChild(td);
  }
  table.appendChild(tr);
}

// Option 2: Store all combinations in an array.
console.log([...generateIndexCombinations(list1, list2, list3, list4)]);

table td {
  padding: 0 0.25em;
}

<table>
</table>

Edit: if you also need to associate each value with the list it comes from, I would use a mapper function as follow:

// Using a generator because this can yield a lot of values. Making an array
// from a generator is easy, and generator results can be fetched one after the other,
// reducing memory load.
function* generateIndexCombinations(lists, mapper = x => x) {
  // Fetch how many cell we needs in our results.
  const size = Math.max(...lists.map(l => l.length));

  // Using a helper so we can add the index parameter. We could also do by
  // slicing the lists, but this would have much larger memory footprint.
  function* doGenerate(lists, valueIndex, acc) {
    // Recursion end case.
    if (valueIndex >= size) {
      yield acc;
      return;
    }

    for (let listIndex = 0; listIndex < lists.length; listIndex++) {
      const list = lists[listIndex];
      if (list.length > valueIndex) {
        const val = mapper(list[valueIndex], listIndex, valueIndex, lists);
        // For each remaining list, create a copy of acc including the index value.
        const newAcc = [...acc, val];
        // Generate the combinations of the tail to be added in acc and re-yield them.
        yield* doGenerate(lists, valueIndex + 1, newAcc)
      }
    }
  }
  yield* doGenerate(lists, 0, []);
}



const list1 = [1, 2, 3, 4, 5];
const list2 = [6, 7, 8, 9, 10];
const list3 = [11, 12, 13, 14, 15];
const list4 = [16, 17, 18, 19, 20];

const table = document.querySelector('table');

// Example 1: without mapper, get each combination one after the other.
for (let c of generateIndexCombinations([list1, list2, list3, list4])) {
  const tr = document.createElement('tr');
  for (let v of c) {
    const td = document.createElement('td');
    td.textContent = v;
    tr.appendChild(td);
  }
  table.appendChild(tr);
}

// Example 2: Store all combinations in an array, using the new optional mapper to map 
// each value to another.
function listCombinationValueMapper(value, listIndex, valueIndex, lists) {
  return {
    value,
    listIndex,
    valueIndex,
    // The source list.
    source: lists[listIndex]
  };
}
const combinations = [...generateIndexCombinations(
  [list1, list2, list3, list4],
  listCombinationValueMapper
)];
console.log(JSON.stringify(combinations));

table td {
  padding: 0 0.25em;
}

<table>
</table>

Please signup or login to give your own answer.

Click here to cancel reply.