Spider spinning for dummies
Richard S. Bird · Cambridge University Press eBooks · 2010
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 1 a 2 … 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 1 ≤ a 2 and a 3 ≤ a 2 . 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 1 ≤ a 2 ≤ a 4 and a 1 ≤ a 3 ≤ a 4 , 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 .