Little math question

[Jan Brouwer]

Hi,

I have a little math question for all you smart people out there

Does anyone know how to construct a as short as possible sequence of numbers 0..n such that each possible sub-sequence of length 1 up to (n + 1)
of these numbers is contained within that sequence, if you ignore the order of numbers within the sub-sequences, and the sub-sequences are allowed to overlap?

For example with n = 7 this could be used to construct a small look-up table to de-serialize a bit vector 8 bits at a time.
The sequence 0 1 2 3 4 5 6 7 then already contains 36 of the 255 sub-sequences (if I counted correctly).

Thanks,
Jan

[rjgibert]

Hi,

I have a little math question for all you smart people out there

Does anyone know how to construct a as short as possible sequence of numbers 0..n such that each possible sub-sequence of length 1 up to (n + 1)
of these numbers is contained within that sequence, if you ignore the order of numbers within the sub-sequences, and the sub-sequences are allowed to overlap?

For example with n = 7 this could be used to construct a small look-up table to de-serialize a bit vector 8 bits at a time.
The sequence 0 1 2 3 4 5 6 7 then already contains 36 of the 255 sub-sequences (if I counted correctly).

Thanks,
Jan

It's hard to figure out from your example what you mean, but I will take a hopefully correct guess.

By subsequences of 0 1 2 3 4 5 6 7, I'm guessing you mean the set of subsequences 0 1 2 3 4 5 6 7 01 12 23 34 45 56 67 012 123 234 345 456 567 0123 1234 2345 3456 4567 01234 12345 23456 34567 012345 123456 234567 0123456 1234567 01234567 of which there are T(n) = n*(n + 1)/2 or T(8) = 8*(8 + 1)/2 = 36 in your example?

However, because of the 0, you seem to be doing some double counting, i.e. 1 and 01, 12 and 012, 123 and 0123, etc. A total of 7 double counts? So really there are only 29 distinct numbers formed by the subsequences?

BTW, this reminds me of debruin sequences which are somewhat related, but where the subsequences are in base 2 and are of fixed length. They are used by some chess programmers to "de-serialize bit vectors" as you put if I am guessing right. Check out the following for more on this:

http://supertech.csail.mit.edu/papers/debruijn.pdf
http://en.wikipedia.org/wiki/De_Bruijn_sequence

I'm sure I've got this wrong, but it is hard for me to guess what your intent is from the information you have given. Please clarify.

[Jan Brouwer]

It's hard to figure out from your example what you mean, but I will take a hopefully correct guess.

By subsequences of 0 1 2 3 4 5 6 7, I'm guessing you mean the set of subsequences 0 1 2 3 4 5 6 7 01 12 23 34 45 56 67 012 123 234 345 456 567 0123 1234 2345 3456 4567 01234 12345 23456 34567 012345 123456 234567 0123456 1234567 01234567 of which there are T(n) = n*(n + 1)/2 or T(8) = 8*(8 + 1)/2 = 36 in your example?

However, because of the 0, you seem to be doing some double counting, i.e. 1 and 01, 12 and 012, 123 and 0123, etc. A total of 7 double counts? So really there are only 29 distinct numbers formed by the subsequences?

Yes, the 36 sub-sequences you list are the ones I had in mind. The 0 here has no special meaning, it is just one of the 8 numbers in this case.
For example, if I want to deserialize the 8-bit number 0x05, the corresponding sub-sequence would be 02 (or 20), i.e. the bit positions of the '1's in 0x05.

I have written out an example for n = 4:

Code: Select all

all sub-sequences of length 1..4:
---------------------------------
0001 0
0010 1
0011 01 (or 10)
0100 2
0101 02 (or 20)
0110 12 (or 21)
0111 012 (or 021/102/120/201/210)
1000 3
1001 03 (or 30)
1010 13 (or 31)
1011 013 (or 031/103/130/301/310)
1100 23 (or 32)
1101 023 (or 032/203/230/302/320)
1111 0123 (or 4! - 1 = 23 other orders)

an example sequence which contains all the above sub-sequences:

13012302

Hope this clarifies it a bit.