Выбор набора двоичных последовательностей во избежание сходства

Question

Я хочу иметь возможность программно генерировать набор двоичных последовательностей заданной длины, избегая при этом сходства между любыми двумя последовательностями. Таким образом, я определяю «аналогичные» между двумя последовательностями:

Если последовательность A может быть преобразована в последовательность B (или от B до A) с помощью бит-сдвига A (без кругового движения) и отступов с 0s, A и B подобны (примечание: бит сдвига допускается только на одном последовательностей в противном случае оба могут всегда быть сдвинуты к последовательности всего 0s)

Например: A = 01010101B = 10101010C = 10010010

в этом примере , A и B аналогичны, поскольку один левый сдвиг o f A приводит к B (A < < 1 = B). A и C равны , а не, так как ни одно смещение одного из них не может привести к другому.

A набор последовательностей определен неравномерно, если ни одно подмножество размера 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, так как более низкие значения производят последовательности в основном 0s, которые похожи на любую другую последовательность.

Ослабляя условия подобия, допуская только небольшое количество последовательных бит-сдвигов, доля разнородных последовательностей приближается к 100%. Это может быть приемлемым в моем случае использования.

Update 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).