生成最长的位序列(每个插槽仅0或1)。
在此序列中,所有连续的m-bit
子序列都是不同的。
例如,如果m = 2,则00110
是这样的最长序列。所有2位子序列都是唯一的:00
01
11
10
。
使用蛮力,我们可以肯定地找到一个这样的序列m
。
但是,有什么聪明的方法吗?
您可以在以下方法中找到解决方案:Matousek和Nesetril撰写的“离散数学邀请”,第140页(是该主题上最精美的书之一)。
答案令人惊讶:每个k> = 1时为2 k(在您的情况下为32)。我会引用:
通过以下方式定义图G =(V,E):(%)V是长度为k-1的所有0和1的序列的集合(%)有向边都是(k-1)- ((a 1,...,a k-1),(a 2,...,a k)形式的数字序列。有向边与k位序列(a 1,...,a k)具有双射对应关系。
然后在G中找到欧拉之旅就足够了。
编辑他们将序列视为其结束和开始都被粘上了。例如,00
从0110
我们的最后一位开始,下一位是序列的第一位。因此,可以通过将第一个(k-1)数字附加到末尾来实际扩展2 k序列。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句