如何使用JS实现数组元素全排列并生成短横线拼接的组合字符串

你之前的代码生成的是笛卡尔积，仅支持从每个子数组按原顺序取元素拼接，要实现全排列效果，可先提取所有待排列元素，再通过回溯法生成全排列后做字符串拼接，代码如下：

// 生成指定数组的全排列
function permute(arr) {
  const result = [];
  const backtrack = (currentPath, usedMarks) => {
    // 排列长度等于原数组长度时存入结果
    if (currentPath.length === arr.length) {
      result.push([...currentPath]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      // 跳过已使用的元素
      if (usedMarks[i]) continue;
      usedMarks[i] = true;
      currentPath.push(arr[i]);
      backtrack(currentPath, usedMarks);
      // 回溯撤销选择
      currentPath.pop();
      usedMarks[i] = false;
    }
  };
  backtrack([], new Array(arr.length).fill(false));
  return result;
}

// 处理输入嵌套数组，返回最终排列结果
function getFullPermutation(inputArr) {
  // 扁平化嵌套数组，拿到所有待排列的元素
  const allItems = inputArr.flat();
  // 生成全排列后按要求拼接字符串
  return permute(allItems).map(item => item.join('-'));
}

测试验证 #

双元素场景测试 #

const test1 = [['Blue'], ['Small']];
console.log(getFullPermutation(test1));
// 输出：['Blue-Small', 'Small-Blue']

三元素场景测试 #

const test2 = [['Blue'], ['Small'], ['New']];
console.log(getFullPermutation(test2));
// 输出：['Blue-Small-New', 'Blue-New-Small', 'Small-Blue-New', 'Small-New-Blue', 'New-Blue-Small', 'New-Small-Blue']

该实现支持任意长度的输入嵌套数组，n个元素将自动生成n!种排列结果。如果你的实际场景中单个子数组存在多个元素，可先做笛卡尔积拿到所有元素组合，再对每个组合单独做全排列即可。

内容的提问来源于stack exchange，提问作者H John