如何使我的静态函数递归？（ordered/forward 组合）

Question

我在为看似简单的递归函数获取正确的逻辑时遇到问题。（最终目标是将不同长度的文本包装在不同大小的圆圈内，松散地基于 Knuth's (Tex) algorithm...我想我已经盯着这个看了太久了。）

我无法将我的静态函数更改为动态版本，因此我可以列出所有可能的组合，n 单词可以拆分成任意行 （数组 L[]）。

每行必须至少包含 1 个单词
这些是句子，所以顺序很重要！（我们可以假设 L.length <= n < 0）

例如，5个字（0-4）进入3行（0-2），所有6种组合都是:

 Line0  Line1  Line2 
   0      1    2+3+4 
   0     1+2    3+4  
   0    1+2+3    4   
  0+1     2     3+4  
  0+1    2+3     4   
 0+1+2    3      4

...我可以通过嵌套循环的简单函数获得：

//for 3 lines (L[0] to L[2])
const n=5; //number of words
var L=[0], ret=[]; //always starts at word#0 on line#0
for(L[1]=L[0]+1; L[1]<n; L[1]++){            // line#1
  for(L[2]=L[1]+1; L[2]<n; L[2]++){          // line#2
    ret.push( L );
  }
}                    // returns array of combinations of the start word# for each line,
console.log( ret );  // like: [[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4]]  ✔️

这可行（与上面的示例组合相匹配）...但仅硬编码 3 行。

因此，我试图将其重写为递归函数，以便行数（和字数）可以动态变化。

感谢任何帮助。

Answer 1

实现此目的的一种方法是将元素之间的空间视为可移动的边界。如果我们有单词 a - e，并且我们想将它们分成三个非空序列，那么我们需要选择其中两个空格（隐含的空格总是在两端。）

   a   b   c   d   e     indices    words
--------------------------------------------
     |   |               [1, 2]  (a, b, cde)
     |       |           [1, 3]  (a, bc, de)
     |           |       [1, 4]  (a, bcd, e)
         |   |           [2, 3]  (ab, c, de)
         |       |       [2, 4]  (ab, cd, e)
             |   |       [3, 4]  (abc, d, e)
--------------------------------------------
 0   1   2   3   4   Infinity

我们可以使用这些边界以及原始数组来相当容易地重建您的单词集合。

所以困难的问题是找到那些边界集。但是现在这是从四个选项中选择两个元素的问题（一般来说，从 words .length - 1 选项中选择 n - 1 选项）并且这是一个众所周知的问题。使用它的递归版本和两个辅助函数，我们可以这样写：

const inPairs = (xs) => xs .slice (1) .map ((x, i) => [xs [i], x])
const range = (lo, hi) => Array .from ({length: hi - lo}, (_, i) => i + lo)

const choose = (n) => (xs) =>
  n < 1 || n > xs .length
    ? []
  : n == 1
    ? [...xs .map (x => [x])]
  : [
      ...choose (n - 1) (xs .slice (1)) .map (ys => [xs [0], ...ys]),
      ...choose (n) (xs .slice (1))
    ]

const wordBreaks = (ws) => (n) => 
  choose (n - 1) (range (1, ws .length)) .map (
    (ns) => inPairs ([0, ...ns, Infinity]) .map(([a, b]) => ws .slice (a, b))
  )

console .log (wordBreaks (['Simplicity', 'is', 'the', 'ultimate', 'sophistication']) (3))

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

帮助者相当琐碎。

toPairs 将数组分组为连续对的集合：

toPairs (['a', 'b', 'c', 'd']) //=> [['a', 'b'], ['b', 'c'], ['c', 'd']]

range创建一个整数范围，左边包含，右边不包含：
```
range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11]
```

这里的重要函数是 choose，它从值数组中收集每组 n 项。

choose (2) (['a', 'b', 'c', 'd']) //=>
// [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]

主要功能是wordBreaks。它使用 range 从图表中获取那些间隙索引，然后使用 choose 到 select n - 1 这些索引，给我们类似 [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]] 的东西。这些中的每一个都被包装以包括 0 和 Infinity，因此 [1, 3, 4] 变成 [0, 1, 3, 4, Infinity]。我们使用 toPairs 将其拆分为 [[0, 1], [1, 3], [3, 4], [4, Infinity]]，然后将它们用作原始数组的 slice 边界，将 ["Here's", "looking", "at", "you", "kid"] 变为 [["Here's"], ["looking", "at"], ["you"], ["kid"]]。我们对每个索引集合都这样做。

如果我们添加一点显示功能，我们可以将七字的莎士比亚名言分成四段，如下所示：

const display = (xss) => console .log (
  (xss .map (xs => `["${xs .map (x => x .join (' ')) .join ('", "')}"]`) .join ('\n'))
)


display (wordBreaks (['Now', 'is', 'the', 'winter', 'of', 'our', 'discontent']) (4))

获得

["Now", "is", "the", "winter of our discontent"]
["Now", "is", "the winter", "of our discontent"]
["Now", "is", "the winter of", "our discontent"]
["Now", "is", "the winter of our", "discontent"]
["Now", "is the", "winter", "of our discontent"]
["Now", "is the", "winter of", "our discontent"]
["Now", "is the", "winter of our", "discontent"]
["Now", "is the winter", "of", "our discontent"]
["Now", "is the winter", "of our", "discontent"]
["Now", "is the winter of", "our", "discontent"]
["Now is", "the", "winter", "of our discontent"]
["Now is", "the", "winter of", "our discontent"]
["Now is", "the", "winter of our", "discontent"]
["Now is", "the winter", "of", "our discontent"]
["Now is", "the winter", "of our", "discontent"]
["Now is", "the winter of", "our", "discontent"]
["Now is the", "winter", "of", "our discontent"]
["Now is the", "winter", "of our", "discontent"]
["Now is the", "winter of", "our", "discontent"]
["Now is the winter", "of", "our", "discontent"]

如何使我的静态函数递归？（ordered/forward 组合）

How to make my static function recursive? (ordered/forward combinations)

javascript

recursion

combinations

permutation

word-wrap

如何使我的静态函数递归？ （ordered/forward 组合）

How to make my static function recursive? (ordered/forward combinations)

javascript

recursion

combinations

permutation

word-wrap

如何使我的静态函数递归？（ordered/forward 组合）