如何仅在javascript中获取具有不同索引的多个列表的所有可能组合？ [重复]

Question

假设我有以下列表：

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]

如何获得所有可能的组合，但仅具有不同的索引？

因此，例如结果

[1,6,11,16]

不起作用。

我需要所有组合，例如：

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

等等...

所以每个列表的索引只能使用一次。 您不能使用 list1[0] 和另一个列表索引[0] 的值。

我还需要知道返回列表中的每个项目来自哪里。

Answer 1

我能想到的一种方法就是这样生成可能的组合

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

Answer 2

这似乎解决了你想要的问题。

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

编辑：如果您还需要将每个值与其来自的列表相关联，我将使用映射器函数，如下所示：

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