Javascript Array String Word Wrap Problem --- 字符串的排列顺序和给定的数组长度

Question

我需要编写一个 JS 函数，它采用 1.an 字符串数组和 2.a 新数组长度以及 returns 每个可能的字符串分组（按顺序）新数组。

这将有助于解决一系列设计的文本自动换行问题。这是一个重要的细节，因为我不需要集合的每一个排列，唯一正确的解决方案将按正确的顺序或顺序排列，并且连接到同一数组元素的单词将由单个 space 分隔。我一直在研究递归解决方案，但没有任何运气。

例如

everyPermutation([A,B,C,D,E], 4);

function everyPermutation(arr, length) {
...
}

会return

[
  ['A B', 'C', 'D', 'E'],
  ['A', 'B C', 'D', 'E'],
  ['A', 'B', 'C D', 'E'],
  ['A', 'B', 'C', 'D E']
]

Answer 1

这是一个递归实现。在递归的每个级别，您迭代第一个块的可能性。递归调用是为了产生删除该块的所有可能性，并且块数少一个：

function partitions(arr, length) {
  if (length === arr.length) return [arr]; // shortcut
  if (length === 1) return [[arr.join(" ")]]; // base case
  let results = [];
  for (let firstlen = arr.length - length + 1; firstlen > 0; firstlen--) {
    let prefix = arr.slice(0, firstlen).join(" ");
    results.push(...partitions(arr.slice(firstlen), length - 1)
                    .map(result => [prefix, ...result]));
  }
  return results;
}


// Example from question
console.log(partitions(["A","B","C","D","E"], 4));
// Example from comments
console.log(partitions(["A","B","C","D","E"], 3));

Answer 2

另一个实现，以我更喜欢表达式而不是语句的风格编写，可能如下所示：

const slicedCombos = (n, xs) => 
  n == xs.length
    ?  [xs.map (x => [x])]
  : [... Array (xs .length)] .map ((_, n) => xs .slice (0, xs .length - n)) .flatMap (
      pf => slicedCombos (n - 1, xs .slice (pf .length)) .map (perm => [pf, ...perm])
    )
    
const partitions = (n, xs) =>
    slicedCombos (n, xs) .map (xss => xss .map (xs => xs .join(' ')))


console .log (partitions (4, ['A', 'B', 'C', 'D', 'E']))
console .log (partitions (3, ['A', 'B', 'C', 'D', 'E']))

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

这将原始数组的切片和切块问题与格式化输出的问题分开了。前者似乎更有可能被重复使用。

在实践中，我可能会提取一个辅助函数来列出数组的前缀，同样是因为我认为它可以重用。看起来像这样：

const prefixes = (xs) =>
  [... Array (xs .length)] .map ((_, n) => xs .slice (0, n + 1))  

const slicedCombos = (n, xs) => 
  n == xs.length
    ?  [xs.map (x => [x])]
  : prefixes (xs) .reverse() .flatMap (
      pfx => slicedCombos (n - 1, xs .slice (pfx .length)) .map (perm => [pfx, ...perm])
    )

额外的 reverse 是按照描述对这些结果进行排序。如果顺序无关紧要，我们可以跳过它。

我没有将主函数或可重用辅助函数命名为“everyPermutation”，因为这有点误导。 “排列”意味着不同的东西。虽然我选择了“分区”，但它有点太笼统了，一个更好的名字会很有用。

Javascript Array String Word Wrap Problem --- 字符串的排列顺序和给定的数组长度

Javascript Array String Word Wrap Problem --- Permutation of Strings in Order and A Given Array Length

javascript

arrays

recursion

word-wrap