A bay window wastes less than a wall

A half-drop wastes less, cut in the right order found a choice in a cutting room that nobody thought was there. A half-drop’s alternate widths start half a repeat lower, which gives the cutter two remainders in place of one, and cutting like drops together or alternating them, whichever is cheaper, loses a quarter of a repeat a gap on a long job where a straight match loses a half.

All of that was worked out with every drop one length. A wall of curtains is like that. A bay window is not, nor a window with a radiator under one side, nor a stairwell, nor a room whose ceiling steps. The first essay named those as the next question and left it there, for a good reason: a job has to fit the width before it fits anything else, and with one length the job has two prices and a linear choice between them, and with several it could have looked like a hard scheduling problem.

It turns out to be easier and better. Mixing the lengths makes a half-drop cheaper to cut, and the reason it is cheaper is the shape of the problem: an order is a walk across two islands, in which each drop is a bridge or a loop of its own.

A drop sets its own price #

The whole of what follows comes from reading one formula twice. The cloth lost after a drop is the distance from where it ended to the next place the next drop may start:

$$\text{gap} = (\varphi_2 - \varphi_1 - L) \bmod r.$$

A half-drop has two classes of drop, A and B, half a repeat apart. For a drop of length $L$, the gap to a next drop of its own class is $u = (-L) \bmod r$ and the gap to one of the other is $v = (r/2 - L) \bmod r$. Nothing else enters. The next drop’s length does not appear, since the next drop has not been cut. The previous drop’s length does not appear, since the roll has already been wound on. So with mixed lengths the cost of an order is still a sum of one number per drop, and each number depends only on that drop and on one binary fact about its successor.

That is the structure that makes the problem tractable. Each drop has a preference, for its own class next or the other, and a price, the smaller of $u$ and $v$:

$$\text{price} = (-L) \bmod \tfrac{r}{2},$$

which never exceeds half a repeat and averages a quarter of one.

The bay window’s two lengths happen to disagree, and that is what makes it a good example. On a 64 centimetre repeat a 250 centimetre drop is six centimetres short of four repeats, so it pays six to stay with its class and thirty-eight to change. A 140 centimetre drop is twelve past two repeats and pays fifty-two to stay and twenty to change. A long drop wants its own class next and a short drop wants the other.

An order is a walk between two islands #

Draw the two classes as two islands. A drop that wants its own class next is a loop at its island: it leaves the cutter where it was. A drop that wants the other is a bridge across. A cutting order in which every drop gets its preference is then a route that uses every loop and every bridge exactly once, each from the island the drop belongs to.

That is Euler’s problem from 1736, on the smallest possible map. On two islands the condition is short: such a walk exists when the bridges from A to B and those from B to A differ by at most one, and when at least one bridge exists if both islands hold a drop. The last drop gets a further concession, since the cloth after the last cut is the roll’s. Its bridge need not be walked at all.

So a job has a floor. It is the sum of every drop’s price, less the largest price, since the most expensive drop can be cut last and excused. In the bay window that is six plus six plus six plus six plus twenty plus twenty, less twenty: forty-four centimetres. The walk exists, so the floor is reached: two long A drops, a short A drop that crosses, two long B drops, a short B drop that does not need to. The condition is exact in both directions: on 2,880 jobs in five arrangements of the lengths across the classes, the search reached the floor on every job whose bridges balance and on no other.

Hanging order on the same job loses a hundred and fifty-four. Six equal drops of 250 centimetres, in their best order, lose sixty-two. So the mixed job beats the wall, in spite of its short drops having the less convenient length, because one of them does the crossing that the wall has to pay for at full price.

Why one length was the hard case #

Look again at the equal drops in those terms. All six share a length, so all six share a preference, and that preference cannot be satisfied.

If all want to stay, there are no bridges, and both islands hold drops, so one drop must cross against its preference and pays the expensive side once: that is the forced change the earlier essay’s formula carried. If all want to cross, they alternate, which is fine, but then it is the alternation that has the bridges balanced. Half of all drop lengths fall each way. A job of one length therefore meets its floor on half of all drop lengths and misses it by a whole forced move on the other half.

With two lengths, the job only misses in the case where both happen to want to stay. Taken over independent lengths that happens on a quarter of jobs, so the floor is reached on three quarters of them; the search confirms 75 per cent on two lengths of two drops each and of three each.

The averages follow. At four drops a half-drop of one length loses a third of a repeat a gap, the earlier essay’s figure. Two lengths of two drops each lose 0.264, and four different lengths 0.239. At six drops one length loses three tenths, two lengths 0.258 and six different lengths 0.246. At eight it is 0.286 against 0.256.

One length comes down towards a quarter of a repeat from above as the job grows, because the forced move is spread across more gaps. Mixed lengths are already close to a quarter at four drops, since the forced move has mostly gone, and an all-different job sits a little under it at first, because the excused last drop is a bigger share of a smaller job. The floor for all different lengths has a closed form,

$$\frac{1}{n-1}\left(\frac{n}{4} - \frac{n}{2(n+1)}\right),$$

which is a fifth of a repeat at four drops and 0.222 at eight, and the search sits above it because not every set of lengths can be walked.

A straight match gets almost nothing #

Mixing does much less for a straight match, and the reason is exact. A straight match has one class, so every drop pays $u$ whatever follows it. Every order costs the same sum, except for which drop’s gap is left off at the end. So the entire choice open to a straight-match cutter is which drop to cut last.

The bay window as a straight match has fifteen distinct orders and exactly two outcomes. Cut a short drop last and the job loses 76 centimetres. Cut a long one last and it loses 122. That is the whole decision, and it is the same rule at every size: leave till last the drop that would lose the most. It holds exactly, tested on a hundred and forty-four jobs against the sum of remainders less the largest and less the smallest.

With all-different lengths, the rule averages $\left(\frac{n}{2} - \frac{n}{n+1}\right)/(n-1)$ of a repeat a gap, or 0.40 at four drops and 0.44 at eight. That returns towards the half a straight match costs anyway, because one excused gap counts for less on a longer job. So the saving from mixing shrinks as the job grows, which is the opposite of the half-drop’s gain from size.

The half-drop’s reputation as the awkward match is now wrong three ways. It costs the same in hanging order, less in its best order, and less again on the mixed jobs that a straight match cannot exploit at all. And it has a risk the straight match lacks, visible in the lower row of the figure: the same six drops run up to 218 centimetres on an unlucky order, where a straight match cannot lose more than 122. An order chosen without thought is more dangerous on a half-drop, and the averages say so: the worst order costs 0.74 of a repeat a gap on six mixed drops, against 0.53 for a straight match.

Hanging order is still the expensive one #

In hanging order a half-drop alternates classes at every gap whatever the lengths are, so each drop pays $v$. That is half a repeat on average at any size and any mixture, exactly as the earlier essay found for equal drops.

Across a repeat of short-drop lengths the hanging order averages 179 centimetres on this job and the best order 56, a saving of more than two thirds. That sweep fixes the long drop at a fortunate length: at 250 centimetres the straight match pays only six for each long gap, and it matches the half-drop on average. The comparison between matches needs the length averaged too, and that is what the earlier figure did. The comparison between orders does not, since at every length in the sweep the best order beats hanging order, and by more than any mixing does.

Against that scale the benefit of mixing itself is modest. On a 64 centimetre repeat, six drops at a quarter of a repeat a gap against three tenths is sixteen and a half centimetres a gap against nineteen, or about thirteen centimetres on the job. It is real, and worth knowing because it is free, and it should not be mistaken for the main saving. Hanging order costs a hundred and sixty centimetres on such a job on average, the best order about eighty. The first decision is whether to reorder at all, and the mixture only improves what reordering does.

What the arrangement across the classes does #

Which class each drop falls in is not up to the cutter. It comes from where the drop hangs, since alternate widths have to alternate. But how the lengths fall across the classes differs from one hanging to another, and it matters.

If long and short drops are each split evenly between the classes, 0.259 of a repeat a gap. If the long drops fall three to one and the short ones both on the lesser side, 0.308. If every long drop is in one class and every short drop in the other, 0.388, with the island map showing why: all the bridges of a length run in one direction, so wherever a length wants to cross, it can do so only once before it is stranded, and the rest pay against their preference.

That last arrangement occurs in real rooms. A wall hung long, short, long, short, in which panels alternate with low widths below a run of windows, puts every long drop in one class and every short in the other, and it is the mixture that gains least from a half-drop. It is still cheaper than the straight match, whose 0.467 sits below it in the figure, but the good of the half-drop has mostly gone.

So an arrangement that seems awkward in a room is cheap to cut, and one that looks tidy is not, and the difference is only visible by asking which class each length falls in. It is a fact about the hanging as well as about the design, since a weave read as a plane pattern is a lattice and a room is not: a half-drop’s seam offset belongs to the design and its width together, and here the arrangement belongs to those and to the room.

The rule, written for a cutter #

The result collapses to three steps, needing nothing but a calculator and the ticket.

Divide each drop length by half the repeat and look at what is short of the next multiple. That is the price. If the same subtraction on the whole repeat gives the same number, the drop wants to stay; if it gives the price plus half a repeat, it wants to cross.

Then cut the classes in runs, changing class only straight after a drop that wants to cross. With both classes holding such drops, alternate between them; with too few of them, one forced change has to be paid, and it should be paid by whichever drop loses least by it.

And leave till last whichever drop has the largest price.

That needs no search on any job a curtain maker would meet, and it gives the exact best wherever the bridges balance. The exhaustive search was there to check it and not to be used.

The same thing has been solved for machines #

The structure here has a history outside textiles, and it is a surprising one to find behind a pair of curtains. Each drop has a state it requires at the start and a state it leaves at the end, and the cost of a transition depends only on those two states. That is a one-state-variable sequencing problem, solved in general by Gilmore and Gomory in 1964 for a machine whose changeover cost depends on a single setting, and their method builds an assignment first and then patches it into one cycle, exactly as the two islands do here.

The general problem has a repeat’s worth of possible states. A half-drop reduces it to two, which is why the answer is a matter of counting bridges on a map a child could draw. A third-drop would have three islands, and the same analysis should apply with a more interesting walk: the earlier essay’s third-drop limit of a sixth of a repeat is the average of a smaller minimum, and mixed lengths on three islands have not been counted here.

The guarantee stays where it was #

A cutting room orders against a guarantee rather than an average, and mixing does not lower the guarantee. The largest cloth lost a gap in the best order is two thirds of a repeat on four drops of one length, as before, and it is the same on two lengths of two drops each; on six drops it is three fifths, again at either mixture.

The reason is short. Two lengths can always happen to share a remainder, which makes the job a job of one length. A cloth order has to allow for that coincidence, so a cutter cannot order less for a bay window. The saving appears as cloth left on the roll. That is a useful distinction, since a guarantee is what is paid for and an average is what is kept, and it is the same as the distinction drawn in the essay on fitting a repeat to a panel between the allowance and the expected use.

How the orders were counted #

The search is a memo on the counts of drops left and the drop just cut, so it reaches the exact best and worst without visiting each order singly. It was tested against an independent walk through every order on 256 jobs of six drops, at two lengths, and the best and worst agreed at all of them. With one length it reproduces the earlier essay’s closed form at 18 lengths and four job sizes. On 144 straight-match jobs it returns the sum of remainders less the largest as its best, and less the smallest as its worst, with no exceptions. No order on any job beat the floor.

The averages take each length’s remainder over an even grid across a whole repeat, every combination for up to two lengths, and a seeded stride through the product where there are many lengths, so the same call returns the same number. One length at 64 grid points returns exactly a third at four drops, and a straight match of four different lengths returns the closed form’s 0.40 to within a hundredth.

What the arithmetic leaves out #

The lengths are taken as independent and evenly spread, which is the same population argument the earlier essays made about drop lengths. Real jobs are not random. A bay window’s long and short drops are related through a sill height, and a particular job has particular remainders, so the averages describe a season’s work and not a window. The rule is exact for any window.

A match is exact and there is no allowance for slop. Hems and headings are in the drop length as given, and so is any allowance for a cloth cut dry and hung in a damp room. A cutter who adds a few centimetres to be safe moves a drop along the saw-tooth, and it can cross from one preference to the other: an allowance is a choice of price, and it is free to choose well.

Everything comes from one roll. Flaws, two lots, a part-used roll and a cloth cut and sewn as it is hung each remove some of the freedom to reorder. Two lots of one cloth drift apart down a drop is the reason a workroom might not want to separate drops at all, and a skew steps at every seam is a reason to want adjacent widths cut from nearby cloth. How often that overrides the saving is a question of practice.

No drop is cut from the waste. A gap is simply lost here. A short drop or a pelmet that fitted inside a long gap would use it, and that is another kind of problem, a packing one, which the search does not attempt. The gaps here run up to a repeat, and a drop is longer than that, so for ordinary drops it does not arise, but a valance could.

Who found it, and when #

Euler’s walk is from 1736 and Gilmore and Gomory’s sequencing from 1964. The saw-tooth of a straight match is written out in the panel essay and the half-drop’s two remainders in its successor. What a repeat repeats supplies the lattice underneath both.

Pricing each drop separately, reading the order as a walk between the two classes, finding that a mixed job beats an equal one, and showing that a straight match’s order can only choose its last drop are worked out here and are not known to be in the trade’s literature. The arithmetic is checkable by anyone with a tape, though nobody is known to have checked it in a workroom.

Still open: what a second roll is worth #

Everything here takes one roll and one excused drop. A job cut from two rolls has two last drops, and each of them is excused, so the cutter can leave off the two largest prices instead of the largest and has a second walk in which to balance the bridges. A second roll looks like a saving and may not be one, since a roll end is cloth too and how much of it is lost depends on what the workroom does with remnants.

The calculation is the same search with the job partitioned between the rolls, and it needs one number the arithmetic cannot supply: what a remnant of a given length is worth to the workroom. If it is worth its full price, the second roll changes nothing. If it is worth nothing, the job should stay on one roll. Between the two there is a remnant value above which a job is better split, and a record of what a workroom’s remnants actually get used for would give it.