多维数组全排列

[Sunny-117]

No description provided.

[kangkang123269]

1. 循环递归

function permute(arr) {
  if (arr.length === 1) return arr[0];
  
  let result = [];
  
  for (let i = 0; i < arr.length; i++) {
    let restArr = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for(let sub of permute(restArr)) {
      result.push([arr[i], ...sub]);
    }
  }
  
  return result;
}

let testArr = [[1,2],[3,4],[5,6]];
console.log(permute(testArr)); 
// 输出：[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2 ,3 ,5] ,[2 ,3 ,6] ,[2 ,4 ,5] ,[2 ，4 ，6]]

2. reduce

function generateCombinations(arr) {
    return arr.reduce((acc, val) => {
        return acc.map(v => val.map(item => [...v, item])).flat();
    }, [[]]);
}

let testArr = [[1, 2], [3, 4], [5, 6]];
console.log(generateCombinations(testArr)); 
// 输出：[[1 ,3 ,5] ,[1 ,3 ,6] ,[1 ,4 ,5] ,[1 ,4 ，6] ,[2 ，3 ，5] ,[2 ，3 ，6] ,[2 ，4 ，5],[2，4，6]]

[Aurora-GSW]

思路：先两两结合，得到结果再跟后面的结合。
例如先 ['A','B'] 跟 ['a','b'] 结合得到结果 [['A','a'],['A','b'],['B','a'],['B','b']] ，然后再跟 [1,2] 结合得到最终结果

let arr = [['A', 'B'],['a', 'b'],[1, 2]];

function permute(arr) {
    let res = arr[0].map(item => [item])
    for (let i = 1; i < arr.length; i++) {
        let list = arr[i]
        let temp = []
        for (const item of res) {
            temp = [...temp, ...list.map(i => [...item, i])]
        }
        res = temp
    }
    return res
}
console.log(permute(arr))
//输出
// [
//     [ 'A', 'a', 1 ],
//     [ 'A', 'a', 2 ],
//     [ 'A', 'b', 1 ],
//     [ 'A', 'b', 2 ],
//     [ 'B', 'a', 1 ],
//     [ 'B', 'a', 2 ],
//     [ 'B', 'b', 1 ],
//     [ 'B', 'b', 2 ]
// ]

[Lupengcheng7]

// 回溯

let testArr = [[1,2],[3,4],[5,6]];
console.log(permute(testArr));
function permute(arr){
    let res = [];
    let track = [];
    let backTrack = (n) => {
        if(n === arr.length){
            res.push([...track]);
            return
        }
        for(let i = 0; i < arr[n].length; i++){
            track.push(arr[n][i]);
            backTrack(n+1);
            track.pop();
        }
    }
    backTrack(0);
    return res;
}

[dizao006]

// 回溯算法
function permute(arr) {
  let path = [];
  let result = [];
  let n = arr.length;
  function DFS(index) {
    if (path.length === n) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length - 1; i++) {
      path.push(arr[index][i]);
      DFS(index + 1);
      path.pop();
    }
  }
  DFS(0);
  return result;
}

let testArr = [
  [1, 2],
  [3, 4],
  [5, 6],
];
console.log(permute(testArr));