查找数组元素的所有排列作为连接字符串 [英] Finding all permutations of array elements as concatenated strings

问题描述

我正在尝试编写一个 JavaScript 函数，该函数返回未知长度数组元素的所有组合.要传递给函数的参数应该是一个单数字符串数组，例如[ 5", 7", 9";].

I am trying to write a JavaScript function that returns all combinations of the elements of an array of unknown length. The argument to be passed to the function should be an array of single digit strings e.g. [ "5", "7", "9" ].

说明所需功能的示例:

• 如果你传入一个 [ "5", "7", "9";]，它应该返回一个数组，其中包含这 3 个数字的所有可能的 3 位组合，即 [ 579"、759"、957"、795"、…<代码>].
• 如果你传入了一个 [ "2", "5", "4", "6";]，你会得到这4个数字的4位组合，即[ "2546", "2654", "2465", ...].
• 如果您传入一个长度为 5 的数组，您将获得这 5 个数字的 5 位组合，依此类推.
• 如果输入的数组多次具有相同的数字，则该数字应在结果数组中出现多次，例如[5"、5"、6"的输入] 产生 [ "556", "655", "565", ...] 的输出.

• If you pass in an array of [ "5", "7", "9" ], it should return an array with all the possible 3-digit combinations of those 3 numbers i.e. [ "579", "759", "957", "795",…].
• If you passed in an array of [ "2", "5", "4", "6" ], you would get the 4-digit combinations of those 4 numbers, i.e. [ "2546", "2654", "2465",…].
• If you passed in an array of length 5, you would get the 5-digit combinations of those 5 numbers, and so on.
• If the inputted array has the same digit multiple times, that number should appear multiple times in the resulting array e.g. an input of [ "5", "5", "6" ] produces an output of [ "556", "655", "565",…].

我环顾四周，似乎递归可能是要走的路，但我正在努力让它工作.我尝试了以下目前适用于 3 位数字的解决方案，但我无法弄清楚如何制作一个适用于未知长度数组的函数.

I have looked around and it seems that recursion might be the way to go, but I am struggling to get it working. I have attempted the below solution which currently works for 3-digit numbers but I can’t figure out how to make a function which works with an array of unknown length.

function getDoubleDigitCombinations(input) {
  let result = [];
  const first = input[0];
  const last = input[1];

  result.push(first + last);
  result.push(last + first);

  return result;
}


function getTripleDigitCombinations(input) {
  let result = [];
  let main; // This is the number in question.
  let other1; // These are the other numbers.
  let other2;

  for (i = 0; i < input.length; i++) {
    let arr = input.slice(); // Make a copy of the input array.
    
    main = input[i];
    arr.splice(i, 1); // Remove the main element from the array …
    other1 = arr[0]; // … so that you are left with the other two numbers.
    other2 = arr[1];

    console.log(`Main is ${main}`);
    console.log(`other1 is ${other1} and other2 is ${other2}`);

    const arr2 = getDoubleDigitCombinations([other1, other2]); // Get the combinations of the others.

    result.push(main + arr2[0]); // Concatenate main with both of the others combinations.
    result.push(main + arr2[1]);
  }

  return result;
}

let result2 = getTripleDigitCombinations([ "6", "7", "8" ]);

console.log("result2 is ...");

for (i = 0; i < result2.length; i++) {
  console.log(result2[i]);
}

推荐答案

堆的algorithm 可用于生成数组元素的所有排列(不重复)，然后您可以使用这些排列与 array.join("") 将它们转换为字符串.这适用于任何大小和任何类型的数组:

Heap's algorithm can be used to generate all permutations (without repetitions) of array elements, you can then use those permutations with array.join("") to convert them to strings. This works for arrays of any size and any type:

这是一个快速的 javascript 实现:

Here is a quick javascript implementation:

// some global variable to store the results
var result = []

// currentSize should be invoked with the array size
function permutation(arr, currentSize) {
    if (currentSize == 1) { // recursion base-case (end)
        result.push(arr.join(""));
        return;
    }
    
    for (let i = 0; i < currentSize; i++){
        permutation(arr, currentSize - 1);
        if (currentSize % 2 == 1) {
            let temp = arr[0];
            arr[0] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        } else {
            let temp = arr[i];
            arr[i] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        }
    }
}

let array = ["1","2","3","4"];
permutation(array, array.length);

console.log(result);
// use result here

请记住，这在计算上非常昂贵，复杂度为 O(n!).

Keep in mind that this is very computationally expensive, with complexity of O(n!).

这篇关于查找数组元素的所有排列作为连接字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！