aquablaze's blog

By aquablaze, history, 9 months ago, In English,

Is there a way to prove/disprove that you can always make a binary string length 2^k+k-1 that contain all permutations of binary string length k as substring?

Originally, i just want to get the shortest strings that contains all permutations of binary strings length k.

For example:

For k=2, you can get 00110 (contains 00,01,10,11 as substrings)

For k=3, you can get 0111010001 (contains 000,001,010,011,100,101,110,111 as substrings)

For k=4, you can get 0000100110101111000

(Im sorry if my english is bad T^T)

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aquablaze (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aquablaze (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +26 Vote: I do not like it

De Bruijn Sequence you can construct it and after that append the prefix of length k-1 to the end of the sequence.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much!!!! I never knew about De Bruijn sequence before