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

我发现此问题：生成所有具有所有唯一k位子序列的n位序列。

考虑36位的序列。每个这样的序列具有由相邻位组成的32个5位序列。例如，序列 1101011 ...包含5位序列11010,10101,01011，...。写一个程序，打印所有36位序列的两个属性： 1.序列的前5位是00000. 2.没有两个5位子序列是相同的。

所以我推广到找到所有具有k位独特子序列的n位序列满足上述要求。然而，我能想到的唯一方法是使用残酷的力搜索：生成n位序列的所有置换，其中前k位为零，然后对每个序列检查是否所有k位子序列都是唯一的。这显然不是一个非常有效的方法。我想知道有没有更好的方法来解决这个问题？

谢谢。

来源

2015-04-03 DoraShine

最简单的方法似乎是回溯方法。您可以跟踪您用平面阵列看到的5位序列。在每一位，尝试加入0 - counter = (counter & 0x0f) << 1并检查您是否曾经看过，然后执行counter = counter | 1并尝试该路径。

可能有更高效的算法可以更快地修剪搜索空间。这似乎与https://en.wikipedia.org/wiki/De_Bruijn_sequence有关。我不确定，但我相信它实际上是相同的;也就是说，序列的最后五位数字必须为10000，使其成为循环。

编辑：这里有一些c代码。由于递归，空间效率低于它，但很简单。最糟糕的是掩模管理。看来我对De Bruijn序列是正确的;这发现了所有2048个。

#include <stdio.h> 
#include <stdlib.h> 

char *binprint(int val) { 
    static char res[33]; 
    int i; 
    res[32] = 0; 
    for (i = 0; i < 32; i++) { 
     res[31 - i] = (val & 1) + '0'; 
     val = val >> 1; 
    } 
    return res; 
} 

void checkPoint(int mask, int counter) { 
    // Get the appropriate bit in the mask 
    int idxmask = 1 << (counter & 0x1f); 

    // Abort if we've seen this suffix before 
    if (mask & idxmask) { 
     return; 
    } 

    // Update the mask 
    mask = mask | idxmask; 

    // We're done if we've hit all 32 
    if (mask == 0xffffffff) { 
     printf("%10u 0000%s\n", counter, binprint(counter)); 
     return; 
    } 

    checkPoint(mask, counter << 1); 
    checkPoint(mask, (counter << 1) | 1); 
} 

void main(int argc, char *argv[]) { 
    checkPoint(0, 0); 
}

来源

2015-04-03 18:37:58 user295691

这是一个非常好的解决方案。我花了一些时间来了解你的方法，所以我会添加一些评论来帮助别人。上面提到的“平面阵列”由32个5位子序列组成。因此，这可以有效地用一个32位的位域来表示，这就是'mask'变量。也就是说，一旦5位值被放入“计数器”（例如，“01101”）的5个最右边位中，则相应的位（例如'13'）被设置在“掩码”中。这就是你如何跟踪重复（'if（mask＆idxmask）return;'）和完成时间（'if（mask == 0xffffffff）'）。 – Matt 2015-04-03 20:52:15

我记得在我的编程面试问题书中看到了这个确切的问题。这里是他们的解决方案：

Explanation of Algorithm 2

Algorithm 2 - Unique 5-bit Sequences

希望它帮助。干杯。

来源

2015-04-03 18:36:38

您似乎已经删除了解释发生了什么的所有部分。 – user2357112 2015-04-03 18:38:26

这只是算法，我屏蔽了它。解释在另一页上。我抓住它并编辑这篇文章。给我一点时间。 – 2015-04-03 18:39:31

这正是我看到问题的地方，但我可能没有正确地得到答案。还是谢谢。 :) – DoraShine 2015-04-04 04:31:36

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

回答

相关问题