社区首页 >问答首页 >选择二值序列集以避免相似性

问选择二值序列集以避免相似性
EN

Stack Overflow用户

提问于 2015-11-16 08:38:03

回答 1查看 163关注 0票数 1

我希望能够编程地生成一组给定长度的二进制序列，同时避免任何两个序列之间的相似性。因此，我将定义两个序列之间的“相似”：

如果序列A可以通过位移位A(非循环)转换为序列B(或B到A)，并且填充了0，则A和B是相似的(注意事项：在其中一个序列上只允许位移位，否则两者总是可以移到仅0的序列)。

例如：A = 01010101 B = 10101010 C = 10010010

在这个例子中，A和B是相似的，因为A的左移位导致B (A << 1= B)。A和C是不相似的，因为一个位的移动不会导致另一个.

定义了序列的集是不同的，如果没有2的子集是相似的。

我相信，对于给定的序列长度，可能存在多个集合，并且想必集合的大小将显著小于总可能性(总可能性=2^序列长度)。

我需要一种方法来生成一个给定序列长度的集合。是否存在能够实现这一目标的算法？在我的用例中，一次只选择一个序列并检查所有先前选择的序列是不可接受的(但如果没有更好的方法，则必须这样做！)

我试着根据素数和黄金比率生成整数集，然后转换成二进制数。这似乎是一个可行的方法，但我一直无法使它按照预期的工作。

Update：我用C#编写了一个函数，它使用素数模块生成集合，但没有成功。此外，我还尝试使用Fibonacci序列，它找到了一个大部分不同的集合，但其大小与可能性的数量相比非常小：

    private List<string> GetSequencesFib(int sequenceLength)
    {
        var sequences = new List<string>();
        long current = 21;
        long prev = 13;
        long prev2 = 8;
        long size = (long)Math.Pow(2, sequenceLength);

        while (current < size)
        {
            current = prev + prev2;
            sequences.Add(current.ToBitString(sequenceLength));                
            prev2 = prev;
            prev = current;
        }

        return sequences;
    }

这将生成一组大小为41的序列，大约60%不同(sequenceLength = 32)。它是从21开始的，因为较低的值产生的序列大多为0，类似于任何其他序列。

通过将相似条件放宽为只允许少量的连续位移位，不同序列的比例接近100%。这在我的用例中可能是可以接受的。

更新2

我按照DCHE的建议实现了一个函数，通过选择大于给定序列长度最大值一半的所有奇数：

    private static List<string> GetSequencesOdd(int length)
    {
        var sequences = new List<string>();
        long max = (long)(Math.Pow(2, length));
        long quarterMax = max / 4;

        for (long n = quarterMax * 2 + 1; n < max; n += 2)
        {
            sequences.Add(n.ToBitString(length));
        }

        return sequences;
    }