Knit lace patterns often move segments of loops to the left or right -- this results in a decorative hole at one end of the moved loops and a stack of stitches at the other end. The order that the stitches appear in this stack influences the appearance of the finished lace. In hand-knitting terminology, this stacking order determines the lean of the decrease -- so one might have a left-leaning or right-leaning decrease.

For example, in this "Open Diamonds" pattern (from The Essential Stitch Collection), left- and right- leaning decreases flank each diamond:

the Open Diamonds lace pattern

In order to make it easy to program lace patterns on a knitting machine, it would be nice to have an algorithm that can automatically translate a description of the desired loop movements to a series of transfer operations (i.e., a sequence of xfer instructions in knitout). In our 2016 knit compiler paper we described an algorithm that will get all the loops to their correct positions; but that transfer planning algorithm doesn't make any guarantees about loop ordering (and it's also quite complicated because it works on tubes as well as sheets).

This post talks about a much simpler transfer planning algorithm that works specifically for the case of lace patterns on sheets.

The Problem Statement

Our lace transfer planning algorithm will take as input two arrays of the same length, an array of offsets, called offsets, and an array that designates which stitches should arrive first at their destination needles, called firsts. It will produce a series of transfer operations that move the loops to their desired offsets, ordered such that the proper loops arrive first.

Our algorithm will guarantee that:

  1. Loops will never be moved further apart than in the starting or ending configurations. In other words, the yarn will not be overly stressed.
  2. Each loop will either not be transferred, or will transferred exactly twice: first to the needle of the same index on the back bed, and then to the needle at the appropriate offset on the front bed.
  3. Further, the final version of the algorithm will produce transfers that can be performed in at most eight passes, regardless of the number of loops in the input.

However, our algorithm will require that:

  1. Loops can't move more than one step left or right. That is, the offsets array must contain only -1, 0, or 1.
  2. Loops must remain in the input range. That is, the first element of offsets must be non-negative, and the last element must be non-positive.
  3. Loops can't cross. That is, the subsequence 1,-1 can't appear in offsets.

The Basic Idea

Given the restrictions we've placed on the offsets array, we can break it into blocks consisting of zero or more 1's, a 0, and zero or more -1's. 

offsets: 0, -1, 0, 1, 1, 0, -1, 1, 1, 0, 0, -1, -1, 0, 1, 0
 blocks:[-----][-][-----------][-------][---------][-][----]

Notice that the only place that two loops can be stacked is within the same block; so our algorithm can deal with each block individually:

Center-Leaning Blocks

offsets: 1, 1, 0,-1  | 0, -1 | 1, 0, -1, -1 | 0
 firsts:       *     | *     |

We call any block that has either the 0 or no loop at all marked first a center-leaning block.

Our algorithm processes a center-leaning block using the following steps:

  1. [T0.b-] Transfer all the -1's to the back bed.
  2. [T0.f-] Return all the -1's to the front bed at an offset of -1.
  3. [T0.b+] Transfer all the 1's to the back bed.
  4. [T0.f+] Return all the 1's to the front bed at an offset of +1.

Notice that this procedure moves all the stitches in the block to their desired offsets in the proper order without stretching the yarn. This last note -- the yarn stretching -- results from the definition of a block; particularly, the offset before the leftmost 1 must be 0 or -1 and the offset after the rightmost -1 must be 0 or 1.

Right-Leaning Blocks

offsets: 1, 1, 0,-1  | 1, 0
 firsts:    *        | *

Right-leaning blocks have the rightmost of the 1's marked first, so require the 0 stitch to be transferred out of the way:

  1. [T+.b+0] Transfer all the 1's and the 0 to the back bed.
  2. [T+.f+] Return all the 1's to the front bed at an offset of +1.
  3. [T+.f0] Return the 0 to the front bed at an offset of 0.
  4. [T+.b-] Transfer all the -1's to the back bed.
  5. [T+.f-] Return all the -1's to the front bed at an offset of -1.

Left-Leaning Blocks

offsets: 1, 1, 0,-1  | 0, -1
 firsts:          *  |     *

Left-leaning blocks have the leftmost of the -1's marked first, and are resolved similarly to right-leaning blocks:

  1. [T-.b-0] Transfer all the -1's and the 0 to the back bed.
  2. [T-.f-] Return all the -1's to the front bed at an offset of -1.
  3. [T-.f0] Return the 0 to the front bed at an offset of 0.
  4. [T-.b+] Transfer all the 1's to the back bed.
  5. [T-.f+] Return all the 1's to the front bed at an offset of 1.

Making it More Efficient

In knitting machines, needles are actuated by a carriage that slides across the needle beds, taking about the same amount of time to move whether it is working the needles or not. This means that knitting machines can perform any number of transfers with the same source and destination beds and the same offset in the same time.

As written above, our algorithm requires (up to) five of these carriage passes per block; indeed, many machines set the back-to-front / front-to-back orientation of their transfers using the carriage direction, so there might actually be an extra (empty) pass required between, say, [T+.f+] and [T+.f0].

However, we can revise our algorithm to work in just eight total passes by noticing that the transfers from each block can be performed in parallel:

  1. Transfer all 1's and 0's from right-leaning blocks to the back. [T+.b+0]
  2. Return all 1's from right-leaning blocks to the front at an offset of +1. [T+.f+]
  3. Return all 0's from right-leaning blocks to the front at an offset of 0. [T+.f0]
  4. Transfer all -1's from all blocks, and all 0's from left-leaning blocks to the back. [T+.b-], [T0.b-], [T-.b-0]
  5. Return all -1's from all blocks to the front at an offset of -1. [T+.f-], [T0.f-], [T-.f-]
  6. Return all 0's from left-leaning blocks to the front at an offset of 0. [T-.f0]
  7. Transfer all 1's from left-leaning and center-leaning blocks to the back. [T-.b+], [T0.b+]
  8. Return all 1's from left-leaning and center-leaning blocks to the front at offset +1. [T-.f+], [T0.f+]

This is pretty good, though the caveat about empty passes between back-to-front transfer passes means this might actually come out to ten passes. Also, in cases where there are no left-leaning blocks, it would be more efficient to move the center-leaning transfers in steps 7 and 8 to steps 1 and 2; but this makes the (full) stacking order of some blocks depend on other blocks elsewhere in the row, which seems awkward.

A Javascript Implementation

If you are interested in using this algorithm in your own knit design, I've written a javascript implementation called lace-transfers.js.

You can run it standalone to perform some test cases, or use it from your own code with node.js require syntax as let lace_transfers = require('lace-transfers.js').lace_transfers. The function takes as its first and second arguments an offsets and firsts array, as described above, and provides outputs back to you by calling xferToBack and xferToFront functions that you provide as the third and fourth arguments.

Further Improvements

This transfer planning algorithm is very constrained, and leaves a fair amount of options for future improvement. Notably, it would be nice to be able to relax the max-offset-size requirements. However, this seems to require thinking beyond simple block-by-block solutions -- for example: 

 blocks:[A][---------B-----------][C]
offsets: 0, +1, +1, +2, +2, +1, 0, 0
 firsts:                 *

In the above case, block B cannot be transferred as desired while blocks A and C remain on the front bed. Though one can still find a solution that matches all of our criteria above by transferring blocks A and C to the back bed while resolving block B, this doesn't seem to generalize. I suspect that eventually we will need to, e.g., relax the "never stack loops on the back bed" requirement implied by the guarantees.