选择一组二进制序列以避免相似性

Question

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

如果序列A可以通过移位A（非循环）并用0填充来转换为序列B（或B到A），A和B是相似的（注: 只允许在一个序列上进行位移，否则两个序列总是可以移位到仅 0 的序列）

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

在此示例中，A 和 B 相似，因为 A 的一次左移导致 B (A << 1 = B)。 A 和 C 不相似，因为任何一个的移位都不会导致另一个。

如果大小为 2 的子集不相似，则定义的组序列是不相似的。

我相信给定的序列长度可能有多个集合，并且集合的大小可能会明显小于总可能性（总可能性 = 2 ^ 序列长度）。

我需要一种方法来为给定的序列长度生成一个集合。是否存在可以实现此目的的算法？一次选择一个序列并检查所有先前选择的序列对于我的用例来说是不可接受的（但如果不存在更好的方法，则可能必须如此！）。

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

更新：我用C#编写了一个函数，它使用质数模来生成集合但没有成功。我也试过使用斐波那契数列，它找到了一个大部分不同的集合，但与可能性的数量相比，它的大小非常小：

    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;
    }

这会根据我的要求生成完全不同的集合。我明白为什么这在数学上也有效。

Answer 1

我无法证明，但根据我的实验，我认为你的集合是大于二进制最大数一半的奇数。例如。对于长度为 3 的位集，最大整数为 7，因此该集为 5 和 7 (101, 111)。

选择一组二进制序列以避免相似性

Selecting set of binary sequences to avoid similarity

c#

algorithm

binary

sequence