生成最长的位序列,其中所有5位连续子序列都是唯一的

杰克逊故事

生成最长的位序列(每个插槽仅0或1)。

在此序列中,所有连续的m-bit子序列都是不同的。

例如,如果m = 2,则00110是这样的最长序列。所有2位子序列都是唯一的:00 01 11 10


使用蛮力,我们可以肯定地找到一个这样的序列m

但是,有什么聪明的方法吗?

阿图尔·格泽西亚克(Artur Grzesiak)

您可以在以下方法中找到解决方案: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中找到欧拉之旅就足够了。


编辑他们将序列视为其结束和开始都被粘上了例如,000110我们的最后一位开始,下一位是序列的第一位。因此,可以通过将第一个(k-1)数字附加到末尾来实际扩展2 k序列。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

查找具有最佳复杂度的数组中唯一连续增加的子序列的数量

生成具有所有唯一k位子序列的所有n位序列。

在O(n)时间中找到序列的最长连续子序列的长度,其中所有元素均小于10 ^ 6

生成所有唯一的k子序列

BIND文件序列-是否对所有区域都是唯一的?

生成汉明距离t内的所有位序列

在oracle中生成6位唯一随机数生成器序列

如何获取数组中所有连续数字的范围(增加子序列)?

从数组生成所有连续序列

最长连续子序列的 Pythonic 方法

更改 PHP 序列化数据中所有唯一键的值

根据一个数字序列生成一个伪唯一数字(代码),该数字在4位数字之内没有重复

生成所有k的数字序列,该数字序列的第k位从左到右从右到右加到10

连续字母的最长序列

检查最长的连续序列,其中前一个数字是当前数字的除数

生成.NET中所有整数的随机,非重复序列

位序列中N个连续真位的统计概率?

如何生成具有某些属性的位序列

Java:写出所有包含K 1的N位序列

如何确定RNA中所有基因序列,其中至少一次重复G和T的组合

字母数字随机数序列[5位或6位或任何数字]生成

获取一个序列的所有子序列

生成唯一 ID 序列

子序列的最大长度,以使得每个连续元素的按位XOR为k

在数组中找到最长的连续子序列

日期数组中最长的连续子序列

最长等距子序列

最长等距子序列

最长子序列,其中输出中的整数是前一个整数的5倍