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

Question

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

如果序列 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 ^ 序列长度)。

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

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

更新:我用 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)。