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

user_8112776 0
Viewed 57

I'm having trouble getting the logic right for a seemingly simple recursive function. (End-goal is wrapping text of varying length inside circles of varying sizes, loosely based on Knuth's (Tex) algorithm... I think I've just been staring at this too long.)

I'm stuck changing my static function to a dynamic version, so I can list all possible combinations that n words can be split among any number of lines (array L[]).

  • Each line must contain at least 1 word
  • These are sentences, so order matters! (and we can assume L.length <= n < 0)

For example, with 5 words (0-4) going into 3 lines (0-2), all 6 combinations are:

 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

...which I can get with a simple function of nested loops:

//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]]  ✔️

This works (matching the example combinations above)... but is hardcoded for 3 lines only.

So, I'm trying to rewrite this as a recursive function so the number of lines (and words) can change dynamically.

Any help is appreciated.

combinations permutation recursion word-wrap javascript
1 Answers

One way to do this is to think of the spaces between elements as movable boundaries. If we have words a - e, and we want to break them into three non-empty sequences, then we need to choose two of these spaces (with implied ones always at either end.)

   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

We can use these boundaries along with the original array to fairly easily reconstruct your collection of words.

So the hard problem is finding those sets of borders. But this is now the problem of choosing two elements from four options (in general, choosing n - 1 options from words .length - 1 options) and that's a fairly well-known problem. Using a recursive version of that and two minor helper functions, we can write this:

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}

The helpers are fairly trivial.

  • toPairs groups an array into a collection of consecutive pairs:

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

  • range creates an integer range, inclusive on the left, exclusive on the right:

    range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11]

The important function here is choose, which collects every set of n items from an array of values.

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

The main function is wordBreaks. It uses range to get get those interstitial indices from the diagram, then uses choose to select n - 1 of those indices, giving us something like [[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]]. Each one of these is wrapped to include 0 and Infinity as well, so that [1, 3, 4] becomes [0, 1, 3, 4, Infinity]. We use toPairs to split this into [[0, 1], [1, 3], [3, 4], [4, Infinity]], then uses those as slice boundaries on our original array, turning ["Here's", "looking", "at", "you", "kid"] into [["Here's"], ["looking", "at"], ["you"], ["kid"]]. And we do this for every collection of indices.

If we add a little display function, we can break a seven-word Shakespeare quote into four segments, like this:

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))

to get

["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"]
user_12436410
Related