30 - Spider spinning for dummies

Summary

Oh what a tangled web we weave when first we practise to derive.

(With apologies to Sir Walter Scott)

Introduction

Consider the problem of generating all bit strings a₁a₂ … an of length n satisfying given constraints of the form a_i ≤ a_j for various i and j. The generation is to be in Gray path order, meaning that exactly one bit changes from one bit string to the next. The transition code is a list of integers naming the bit that is to be changed at each step. For example, with n = 3, consider the constraints a₁ ≤ a₂ and a₃ ≤ a₂. One possible Gray path is 000, 010, 011, 111, 110 with transition code [2, 3, 1, 3] and starting string 000.

The snag is that the problem does not always have a solution. For example, with n = 4 and the constraints a₁ ≤ a₂ ≤ a₄ and a₁ ≤ a₃ ≤ a₄, the six possible bit strings, namely 0000, 0001, 0011, 0101, 0111 and 1111, cannot be permuted into a Gray path. There are four strings of even weight (the numbers of 1s) and two of odd weight, and in any Gray path the parity of the weights has to alternate.

Constraints of the form a_i ≤ a_j on bit strings of length n can be represented by a digraph with n nodes in which a directed edge i ← j is associated with a constraint a_i ≤ a_j.