Найти число двоичных чисел с определенными ограничениями

Это скорее головоломка, чем проблема с кодированием. Мне нужно найти, сколько двоичных чисел может быть сгенерировано, удовлетворяющее определенным ограничениям. Входы

(integer) Len - Number of digits in the binary number
(integer) x
(integer) y

Двоичное число должно быть таким, что при принятии любых смежных цифр из двоичного числа должно быть не менее y 1.

Например -

Len = 6, x = 3, y = 2

0 1 1 0 1 1 - Длина равна 6, возьмите из нее 3 смежные цифры и будет 2 l

У меня был этот вопрос с кодировкой С#, заданный мне в интервью, и я не могу найти алгоритм для решения этой проблемы. Не ища код (хотя он приветствуется), любая помощь, указатели оцениваются

Ответ 1

Используя пример LEN = 6, X = 3 и Y = 2...

Постройте генератор исчерпывающего битового шаблона для X бит. Простой двоичный счетчик может это сделать. Например, если X = 3 то счетчик от 0 до 7 будет генерировать все возможные битовые шаблоны длины 3.

Шаблоны:

Подтвердите требование смежности по мере создания шаблонов. Отклонить любые шаблоны, которые не соответствуют критериям. В основном это сводится к отказу от любого шаблона, содержащего менее 2 '1' бит (Y = 2). Список сократится до:

Для каждого члена сокращенного списка добавьте бит "1" и повторите проверку первых X бит. Сохраните новый шаблон, если он пройдет критерий смежности. Сделайте то же самое с "0" бит. Например, этот шаг выполняется следующим образом:

1011  <== Keep
1101  <== Keep
1110  <== Keep
1111  <== Keep
0011  <== Reject
0101  <== Reject
0110  <== Keep
0111  <== Keep

Что оставляет:

Теперь повторите этот процесс до тех пор, пока обрезанный набор не станет пустым, или длина элементов станет длиннее LEN. В конце останутся только следующие шаблоны:

Подсчитайте их, и все готово.

Обратите внимание, что вам нужно только протестировать первые X бит на каждой итерации, потому что все последующие шаблоны были проверены на предыдущих шагах.

Ответ 2

Эта проблема может быть решена с помощью динамического программирования. Основная идея - группировать двоичные числа в соответствии с последними битами x-1 и длиной каждого двоичного числа. Если добавление битовой последовательности к одному числу дает число, удовлетворяющее ограничению, то добавление одной и той же последовательности бит в любое число в той же группе приводит к числу, удовлетворяющему также ограничению.

Например, x = 4, y = 2. Оба из 01011 и 10011 имеют одинаковые последние 3 бита (011). Добавляя 0 к каждому из них, в результате получим 010110 и 100110, оба удовлетворяют этому ограничению.

Вот псевдокод:

mask = (1<<(x-1)) - 1
count[0][0] = 1
for(i = 0; i < Len-1; ++i) {
    for(j = 0; j < 1<<i && j < 1<<(x-1); ++j) {
        if(i<x-1 || count1Bit(j*2+1)>=y)
            count[i+1][(j*2+1)&mask] += count[i][j];
        if(i<x-1 || count1Bit(j*2)>=y)
            count[i+1][(j*2)&mask] += count[i][j];
    }
}
answer = 0
for(j = 0; j < 1<<i && j < 1<<(x-1); ++j)
    answer += count[Len][j];

Этот алгоритм предполагает, что Len >= x. Сложность времени равна O (Len * 2 ^ x).

ИЗМЕНИТЬ

Функция count1Bit(j) подсчитывает число 1 в двоичном представлении j.

Единственный вход для этого алгоритма - Len, x, and y. Он начинается с пустой двоичной строки [length 0, group 0] и итеративно пытается добавить 0 и 1 до тех пор, пока длина не будет равна Len. Он также группирует и подсчитывает количество двоичных строк, удовлетворяющих 1-битовому ограничению в каждой группе. Результатом этого алгоритма является answer, который представляет собой число двоичных строк (чисел), удовлетворяющих ограничениям.

Для двоичной строки в группе [length i, group j] добавление 0 к ней приводит к двоичной строке в группе [length i+1, group (j*2)%(2^(x-1))]; добавление 1 к нему приводит к двоичной строке в группе [length i+1, group (j*2+1)%(2^(x-1))].

Пусть count[i,j] - число двоичных строк в группе [length i, group j], удовлетворяющее 1-битовому ограничению. Если в двоичном представлении j*2 есть не менее y 1, то добавление 0 к каждой из этих двоичных строк count[i,j] дает двоичную строку в группе [length i+1, group (j*2)%(2^(x-1))], которая также удовлетворяет 1-битовому ограничению. Поэтому мы можем добавить count[i,j] в count[i+1,(j*2)%(2^(x-1))]. Случай добавления 1 аналогичен.

Условие i<x-1 в приведенном выше алгоритме состоит в том, чтобы сохранить бинарные строки, когда длина меньше x-1.

Ответ 3

Учитывая, что входные значения являются переменными и хотят видеть фактический вывод, я использовал рекурсивный алгоритм для определения всех комбинаций 0 и 1 для заданной длины:

    private static void BinaryNumberWithOnes(int n, int dump, int ones, string s = "")
    {
        if (n == 0)
        {
            if (BinaryWithoutDumpCountContainsnumberOfOnes(s, dump,ones))
                Console.WriteLine(s);
            return;
        }
        BinaryNumberWithOnes(n - 1, dump, ones, s + "0");
        BinaryNumberWithOnes(n - 1, dump, ones, s + "1");
    }

и BinaryWithoutDumpCountContainsnumberOfOnes, чтобы определить, соответствует ли двоичное число критериям

private static bool BinaryWithoutDumpCountContainsnumberOfOnes(string binaryNumber, int dump, int ones)
    {
        int current = 0;
        int count = binaryNumber.Length;
        while(current +dump < count)
        {
            var fail = binaryNumber.Remove(current, dump).Replace("0", "").Length < ones;
            if (fail)
            {
                return false;
            }
            current++;
        }

        return true;
    }

Вызов BinaryNumberWithOnes (6, 3, 2) выводит все двоичные числа, соответствующие

Ответ 4

Наивный подход был бы рекурсивным деревом.

Наш рекурсивный метод будет медленно строить число вверх, например. он должен начинаться с xxxxxx, возвращать сумму вызова с помощью 1xxxxx и 0xxxxx, которые сами возвратят сумму вызова с помощью 10, 11 и 00, 01 и т.д. за исключением случаев, когда условия x/y НЕ удовлетворяются за строну, которую она построила, вызывая себя, она НЕ идет по этому пути, и если вы находитесь в терминальном состоянии (построили номер правильной длины), вы возвращаете 1. ( обратите внимание, что, поскольку мы строим строку слева направо, вам не нужно проверять x/y для всей строки, просто учитывая новую добавленную цифру!)

Возвращая сумму по всем вызовам, все возвращенные 1s объединятся вместе и будут возвращены начальным вызовом, равным числу построенных строк.

Не знаю, какая большая нотация O для временной сложности для этого, она может быть такой же плохой, как O(2^n)*O(checking x/y conditions), но в большинстве случаев она отсекает множество ветвей.

ОБНОВЛЕНИЕ:. Я имел в виду, что все ветки рекурсивного дерева могут быть "объединены", если они имеют идентичные последние цифры x до сих пор, потому что тогда одни и те же проверки будут применены к все цифры в дальнейшем, поэтому вы можете удвоить их и сэкономить много работы. Теперь это требует явного создания дерева вместо неявно с помощью рекурсивных вызовов и, возможно, какой-то схемы хэширования, чтобы обнаружить, когда ветки имеют идентичные окончания x, но для большой длины это обеспечило бы огромное ускорение.

Ответ 5

Похоже, что вложенный цикл будет делать трюк. Псевдокод (не проверен).

value = '0101010111110101010111'   // change this line to format you would need
for (i = 0; i < (Len-x); i++) {    // loop over value from left to right
     kount = 0
     for (j = i; j < (i+x); j++) { // count '1' bits in the next 'x' bits
         kount += value[j]         // add 0 or 1
         if kount >= y then return success
     }
}
return fail

Ответ 6

Итак, в серии двоичных цифр Len, вы ищете x-длинный сегмент, содержащий y 1..

Смотрите выполнение: http://ideone.com/xuaWaK

Здесь мой алгоритм в Java:

import java.util.*;
import java.lang.*;

class Main
{
    public static ArrayList<String> solve (String input, int x, int y)
    {
        int s = 0;
        ArrayList<String> matches = new ArrayList<String>();
        String segment = null;

        for (int i=0; i<(input.length()-x); i++)
        {
            s = 0;
            segment = input.substring(i,(i+x));

            System.out.print(" i: "+i+" ");

            for (char c : segment.toCharArray())
            {
                System.out.print("*");

                if (c == '1')
                {
                    s = s + 1;
                }
            }

            if (s == y)
            {
                matches.add(segment);
            }

            System.out.println();
        }

        return matches;
    }

    public static void main (String [] args)
    {
        String input = "011010101001101110110110101010111011010101000110010";

        int x = 6;

        int y = 4;

        ArrayList<String> matches = null;

        matches = solve (input, x, y);

        for (String match : matches)
        {
            System.out.println(" > "+match);
        }

        System.out.println(" Number of matches is " + matches.size());
    }
}

Ответ 7

Мой подход заключается в том, чтобы начать с получения всех двоичных чисел с минимальным числом 1, что достаточно просто, вы просто получаете каждую уникальную перестановку двоичного числа длины x с y 1 и циклически переключаете каждую уникальную перестановку "Len" раз. Перевернув 0 бит этих семян в любой возможной комбинации, мы гарантируем повторение всех двоичных чисел, которые соответствуют критериям.

from itertools import permutations, cycle, combinations

def uniq(x):
    d = {}
    for i in x:
        d[i]=1
    return d.keys()


def findn( l, x, y ):
    window = []
    for i in xrange(y):
        window.append(1)
    for i in xrange(x-y):
        window.append(0)

    perms = uniq(permutations(window))
    seeds=[]
    for p in perms:
        pr = cycle(p)
        seeds.append([ pr.next() for i in xrange(l) ]) ###a seed is a binary number fitting the criteria with minimum 1 bits

    bin_numbers=[]
    for seed in seeds:
        if seed in bin_numbers: continue
        indexes = [ i for i, x in enumerate(seed) if x == 0] ### get indexes of 0 "bits"
        exit = False
        for i in xrange(len(indexes)+1):
            if( exit ): break
            for combo in combinations(indexes, i): ### combinatorically flipping the zero bits in the seed
                new_num = seed[:]
                for index in combo: new_num[index]+=1
                if new_num in bin_numbers:
                    ### if our new binary number has been seen before
                    ### we can break out since we are doing a depth first traversal
                    exit=True
                    break
                else:
                    bin_numbers.append(new_num)

    print len(bin_numbers)

findn(6,3,2)

Рост такого подхода определенно экспоненциальный, но я думал, что поделюсь своим подходом, если он поможет кому-то получить решение с более низкой степенью сложности...

Ответ 8

Задайте некоторое условие и введите простую справочную переменную.

L = 6, x = 3 , y = 2 introduce d = x - y = 1

Условие: если список следующего числа с гипотетическим значением и предыдущими значениями элементов x - 1 имеет число 0-цифp > d, следующее число должно быть 1, в противном случае добавить два значения с 1 и 0 как конкретное значение.

Начало: проверка (Условие) = > обе 0,1 из-за количества полных нулей в проверке 0-count.

Empty => add 0 and 1

Шаг 1: Проверка (условие)

0 (number of next value if 0 and previous x - 1 zeros > d(=1)) -> add 1 to sequence
1 -> add both 0,1 in two different branches

Шаг 2: проверка (условие)

01 -> add 1

10 -> add 1
11 -> add 0,1 in two different branches

Шаг 3:

011 -> add 0,1 in two branches

101 -> add 1 (the next value if 0 and prev x-1 seq would be 010, so we prune and set only 1)

110 -> add 1
111 -> add 0,1

Шаг 4:

0110 -> obviously 1
0111 -> both 0,1

1011 -> both 0,1

1101 -> 1
1110 -> 1
1111 -> 0,1

Шаг 5:

01101 -> 1
01110 -> 1
01111 -> 0,1

10110 -> 1
10111 -> 0,1

11011 -> 0,1
11101 -> 1
11110 -> 1
11111 -> 0,1

Шаг 6 (Закончить):

Теперь подсчитайте. Я тестировал также L = 6, x = 4 и y = 2, но рассмотрю, чтобы проверить алгоритм для особых случаев и расширенных случаев.

Примечание. Я уверен, что некоторый алгоритм с основами теории диспозиции должен быть действительно большим улучшением моего алгоритма.

Ответ 9

Число шаблонов длины X, содержащих по меньшей мере Y 1 бит, является счетным. Для случая x == y мы знаем, что существует ровно один образец возможных шаблонов 2^x, отвечающих критериям. Для меньшего y нам нужно суммировать количество шаблонов, у которых есть избыточные бит 1 и количество паттернов, которые имеют точно y бит.

 choose(n, k) = n! / k! (n - k)!

 numPatterns(x, y) {
     total = 0
     for (int j  = x;  j >= y; j--)
        total += choose(x, j)
     return total
 }

Например:

X = 4, Y = 4 : 1 pattern
X = 4, Y = 3 : 1 + 4 = 5 patterns
X = 4, Y = 2 : 1 + 4 + 6 = 11 patterns
X = 4, Y = 1 : 1 + 4 + 6 + 4 = 15 patterns
X = 4, Y = 0 : 1 + 4 + 6 + 4 + 1 = 16 
  (all possible patterns have at least 0 1 bits)

Итак, пусть M будет числом шаблонов длины X, которые соответствуют критериям y. Теперь этот шаблон длины X представляет собой подмножество бит N. Для вспомогательного шаблона есть (N - x + 1) "окна", а 2^N возможны общие шаблоны. Если мы начнем с любого из наших шаблонов M, мы знаем, что добавление 1 вправо и переход к следующему окну приведет к одному из наших известных шаблонов M. Вопрос в том, сколько из шаблонов M можно добавить 0 to, сдвинуть вправо и по-прежнему иметь правильный шаблон в M?

Так как мы добавляем нуль, мы должны либо сдвигаться от нуля, либо мы должны уже находиться в M, где мы имеем избыток бит 1. Чтобы перевернуть это, мы можем спросить, сколько из M шаблонов имеет ровно y бит и начать с 1. Это то же самое, что "сколько шаблонов длины X-1 имеют Y-1 бит", которые мы знаем, как отвечать:

shiftablePatternCount = M - choose(X-1, Y-1)

Итак, начиная с возможностей M, мы будем увеличиваться на shiftablePatternCount, когда мы сдвигаемся вправо. Все шаблоны в новом окне находятся в наборе M, а некоторые шаблоны теперь дублируются. Мы собираемся несколько раз меняться, чтобы заполнить N на (N - X), каждый раз, увеличивая счет на shiftablePatternCount, поэтому полный ответ должен быть:

totalCountOfMatchingPatterns = M + (N - X)*shiftablePatternCount

edit - реализована ошибка. Мне нужно подсчитать дубликаты сменных шаблонов, которые генерируются. Я думаю, что это выполнимо. (черновик еще)

Ответ 10

Я не уверен в моем ответе, но вот мой взгляд. Просто взгляните на него,
Len = 4,
х = 3,
у = 2.
я просто вынул два шаблона, шаблон причины должен содержать не менее y 1.
X 1 1 X
1 X 1 X
X - представлять не заботятся
теперь рассчитывается для 1-го выражения: 2 1 1 2 = 4
и для второго выражения 1 2 1 2 = 4
но 2 шаблон является общим для обоих значений минус 2..so будет общая 6 пар, которые удовлетворяют условию.

Ответ 11

Я использую algoritem, подобный вашей проблеме, пытаясь найти способ улучшить его, я нашел ваш вопрос. Поэтому я буду делиться

static int GetCount(int length, int oneBits){
int result = 0;
double count = Math.Pow(2, length);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(length, '0');
        if (str.ToCharArray().Count(c => c == '1') == oneBits)
        {
            result++;
        }
    }
    return result;
}

Не очень эффективно Я думаю, но элегантное решение.