De Bruijn sequence

gistfile1.rb

# De Bruijn sequence
# Original implementation by Frank Ruskey (1994)
# translated to C by Joe Sawada
# translated to Ruby by Jonas Elfström (2009)

@n = 4
@k = 10
@a = [0]
@sequence = []

def debruijn(t, p)
  if t > @n
    if @n%p == 0
      1.upto(p) {|j| @sequence << @a[j]}
    end
  else
    @a[t] = @a[t - p]
    debruijn(t + 1, p)
    (@a[t - p] + 1).upto(@k - 1) {|j|
      @a[t] = j
      debruijn(t + 1, t)
    }
  end
end

debruijn(1, 1)
print @sequence.join

# http://alicebobandmallory.com/articles/2009/09/27/a-case-for-using-only-three-different-digits-in-keypad-codes

Used in http://alicebobandmallory.com/articles/2009/09/27/a-case-for-using-only-three-different-digits-in-keypad-codes