查找数组元素的所有排列作为串联字符串

Question

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

说明所需功能的示例：

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

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

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

Answer 1

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

这是一个快速 javascript 实施：

// 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!)。

Answer 2

我相信堆的算法仍然是效率的黄金标准。维克多的回答很好地涵盖了这一点。

但由于任何算法都必须至少 O(n!)，我们永远不会在生成排列方面获得惊人的性能。我们可能还想看看简单性。

另一种实现显然更简单：

const excluding = (i) => (xs) => 
  [... xs .slice (0, i), ... xs .slice (i + 1)]

const permutations = (xs) => 
  xs .length == 0 
    ? [[]] 
    : xs .flatMap ((x, i) => permutations (excluding (i) (xs)) .map (p => x + p))

console .log (permutations (['5', '6', '7']))

这里我们使用一个小的辅助函数 excluding，它 return 是一个数组的副本，删除了给定索引处的值。然后 permutations 遍历数组中的值，依次将每个值作为一组排列的第一个值，并通过在排除当前索引找到的数组上重复查找这些排列的其余部分。

这有一个很好的特点，即排列是按明显的顺序 returned 的。如果原始数组已排序，比如 ['a', 'b', 'c']，则结果 return 按字母顺序排列：['abc', 'acb', 'bac', 'bca', 'cab', 'cba']。这通常不是必需的，但可能很有用。

请注意，此解决方案通常用以下行编写：

    : xs .flatMap ((x, i) => permutations (excluding (i) (xs)) .map (p => [x, ... p]))

其中 return 是数组数组 ([['5', '6', '7'], ['5', '7', '6'], ...]) 而不是字符串数组 (['567', '576', ...])。

我最近看到的另一个版本更简单。它不是原创的，但我不记得我是在哪里看到它的——可能是在 Whosebug 上。这是我自己对这个想法的实现，但我认为它非常接近原始版本：

const rotations = ([l, ...ls], rs = []) => 
  l == undefined ? [] : [[l, ...ls, ...rs], ... rotations (ls, [...rs, l])]

const permutations = ([l, ...ls]) =>
  l == undefined ? [[]] : [...permutations (ls) .flatMap (p => rotations ([l, ...p])) ]

console .log (permutations (['5', '6', '7']) .map (p => p .join ('')))

.as-console-wrapper {max-height: 100% !important; top: 0}

这里我们使用一个函数rotations，它接受一个数组和return该数组的所有环绕旋转。例如：

rotations(['x', 'y', 'z'])
//=> [['x', 'y', 'z'], ['y', 'z', 'x'], ['z', 'x', 'y']]

我们用它来编写 permutations，方法是取出第一个元素，递归地查找剩余元素的排列，然后对每个元素重新粘贴第一个元素，然后 return 合并所有元素旋转。

这篇文章很短，也很聪明。我可能会坚持使用 Heap 的速度算法或上面的算法以获得有序的输出。不过为了简单起见，这个还是值得考虑的。

虽然此算法最多可以修复 return 个字符串，但它会比以前的版本更具侵入性，涉及对 rotations 和 permutations 的更改，以及我宁愿坚持在它的输出上生成字符串，就像上面用 .map (p => p .join ('')) 所做的那样。不过，如果你想这样做，它可能看起来像这样：

const rotations = ([l, ...ls], rs = '') => 
  l == undefined ? [] : [l + ls.join('') + rs, ... rotations (ls, rs + l)]

const permutations = ([l, ...ls]) =>
  l == undefined ? [[]] : [...permutations (ls) .flatMap (p => rotations (l + p)) ]

permutations (['5', '7', '7']) //=> ['577', '775', '757', '577', '775', '757']

Answer 3

一个有趣的问题！我想使用生成器来实现。这允许您在生成排列时一个一个地处理它们，而不必在提供整个答案之前计算 all 个排列 -

const input =
  ["","","",""]

for (const p of permutations(input))
  console.log(p.join(""))

这让我们可以做一些很酷的事情，比如找到特定的模式 -

// find all permutations where red is left of green
for (const p of permutations(input))
  if (p.indexOf("") < p.indexOf(""))
    console.log(p.join(""))

// find all permutations where blue and yellow are adjacent
for (const p of permutations(input))
  if (Math.abs(p.indexOf("") - p.indexOf("")) == 1)
    console.log(p.join(""))

如果我们想找到唯一的 第一个 排列，其中这种条件为真，我们可以使用 return 或 break 到停止生成器，不再计算排列。

我们只需要执行 permutations -

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

这取决于rotations -

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

这取决于两个用于处理可迭代对象的通用函数，map 和 chain -

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

展开代码段以在您自己的浏览器中验证结果

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

const input =
  ["","","",""]

console.log("\nred is left of green")
for (const p of permutations(input))
  if (p.indexOf("") < p.indexOf(""))
    console.log(p.join(""))

console.log("\nblue and yellow are adjacent")
for (const p of permutations(input))
  if (Math.abs(p.indexOf("") - p.indexOf("")) == 1)
    console.log(p.join(""))

我希望你喜欢这个 post 就像我喜欢写它一样:D

要使用类似的技术计算组合，请参阅。

Answer 4

调整参数以接受数组而不是数字后，以下内容可能会满足您的需要。

function combinator(nbr) {
  if (typeof nbr !== 'number' || nbr>999999999) return 'NaN'
 const combinedArr = []
 const _nbr = `${nbr}`.split('')
 combinatorRec(_nbr, [])

 function combinatorRec(_nbr, prev){
   if (_nbr.length === 0) {
     combinedArr.push(parseInt(prev))
     return
   }
  _nbr.forEach((char,i)=>{
    const _nbrI = [..._nbr]
    _nbrI.splice(i,1)
    combinatorRec(_nbrI, prev+char )
  })
 }

  const uniqueArray = combinedArr.filter((item, pos) => (combinedArr.indexOf(item) === pos))
 return uniqueArray
}

查找数组元素的所有排列作为串联字符串

Finding all permutations of array elements as concatenated strings

javascript

arrays

algorithm

recursion

permutation