Найдите, что все способы вставить обнуляют в небольшой шаблон

Я не собираюсь давать вам код Objective-C в основном потому, что:

• Я знаю Objective-C только на очень поверхностном уровне.
• У меня нет желания писать весь код управления памятью, необходимый для того, чтобы это работало, на таком языке, как C, и в любом случае это только снизит удобочитаемость.

Вместо этого я дам вам несколько идей и код, показывающий, как я могу реализовать это на более высоком языке с генераторами и сборкой мусора (в данном случае Python), а также подскажу, как это сделать без генераторов. Надеюсь, кто-то другой сможет перенести код за вас, если вы не можете сделать это самостоятельно.

Я бы подумал о вашей проблеме немного по-другому:

• Сколько ведущих нулей есть в вашем исходном шаблоне «смыть вправо».
• Сколько существует способов разделить это количество нулей на n разделов?

В вашем последнем примере у вас есть два ведущих нуля и три раздела с разделителями «10» и «1»:

2 0 0: 00101  
1 1 0: 01001   
1 0 1: 01010   
0 2 0: 10001   
0 1 1: 10010   
0 0 2: 10100

Разделители всегда имеют форму 111..10 , за исключением последнего, который является просто 111..1 без конечного нуля.

Для перечисления перечисленных выше разделов используйте функцию, подобную следующей в Python:

def partitions(n, x):
    if n == 1:
        yield [x]
    else:
        for i in range(x + 1):
            for p in partitions(n - 1, x - i):
                yield [i] + p

for p in partitions(3, 2):
    print p

Результат:

[0, 0, 2]
[0, 1, 1]
[0, 2, 0]
[1, 0, 1]
[1, 1, 0]
[2, 0, 0]

После того, как у вас есть эти разделы, легко построить шаблоны.

Одна из проблем заключается в том, что Objective-C не имеет встроенной поддержки конструкции yield. Следующая переписанная выше функция может быть легче преобразована в Objective-C:

def partitions(n, x):
    if n == 1:
        return [[x]]
    else:
        result = []
        for i in range(x + 1):
            for p in partitions(n - 1, x - i):
                result.append([i] + p)
        return result

Я надеюсь, что это будет полезно для вас.

Надеюсь, это облегчит вам задачу (пожалуйста, читайте это с ручкой и бумагой в руках).

Скажем, количество нулей (начиная справа) равно x₁, x₂, ..., x_n. Например: если битовая схема 00001110001001, то x₁ = 0, x₂ = 2, x₃ = 3, x₄ = 4. n на единицу больше числа блоков единиц. Заметим, что знания x₁, x₂, ..., x_n достаточно, чтобы вычислить битовый шаблон.

Теперь, если общее количество единиц равно S, а общее количество доступных битов равно M, то мы должны иметь, что

x₁ + x₂ + ... + x_n = M - S

и x₁ ≥ 0, x_n ≥ 0, x₂ ≥ 1, x₃ ≥ 1, ...

Пусть z₁ = x₁ + 1 и z_n = x_n + 1

Таким образом, имеем

z₁ + x₂ + ... x_n-1 + z_n = M - S + 2

Где z₁ ≥ 1, x₂ ≥ 1, x₃ ≥ 1, ..., z_n ≥ 1.

Теперь рассмотрим разбиение из M-S+2 элементов, где в каждом разбиении есть хотя бы один элемент. Любое разбиение соответствует решению вышеприведенного уравнения, а решение соответствует разбиению в моде 1-1.

Расположите M-S+2 элементов вдоль линии. Чтобы получить разбиение, рассмотрим размещение n-1 палочек в M-S+2-1 = M-S+1 доступных местах между предметами.

Таким образом, решение (и, в конечном счете, необходимый вам битовый шаблон) однозначно соответствует способу выбора n-1 мест среди M-S+1 мест.

В случае 5 битов, и 1 бит - это 1 и 1.

У вас есть n = 3, M = 5, и S = 2.

Таким образом, у вас есть M-S+1 выбрать n-1 = 4 выбрать 2 = 6 возможностей.

Перечисление комбинаций n choose r является стандартной задачей, и в Интернете можно найти множество решений (некоторые из них очень умные!) для этого.

Пример см. здесь: http://compprog.files.wordpress.com/2007/10/comb1.c, который, похоже, поддерживает "ленивое" перечисление: next_combination и не требует огромного количества памяти.

Это теоретическая или практическая проблема? Вам нужно оптимальное O(N) или достаточно хорошее время выполнения? Если это практическая задача, и если только это не во внутреннем цикле чего-либо, то просто проверка каждого 15-битного числа должна быть достаточно быстрой. Это всего 32k чисел.

Просто получите разделы для вашего числа, примерно так:

void get_groups(ushort x, int* groups) {
  int change_group = 0;
  while(x) {
    if (x & 1) {
      ++(*groups);
      change_group = 1;
    } else {
      if (change_group) {
        ++groups;
        change_group = 0;
      }
    }
    x >>= 1;
  }
}

А затем, для каждого 15-битного числа, проверьте, создает ли оно тот же массив групп, что и ваше исходное число.

Примечание: Массив groups должен вмещать максимальное количество групп (например, должен иметь размер 8 для 15-битных чисел).

Предположим, у нас есть:

000101101

Сначала посчитаем нули ( 5 ) и посчитаем группы нулей, окруженные единицами ( 1 ) . Мы можем пока забыть о единицах.Количество нулей в группе в любой комбинации может быть списком, описанным как (где + означает «или больше»):

[0+, 1+, 1+, 0+] where the sum is 6

Это всего лишь вариант аналогичной задачи: найти все наборы из N non -отрицательные целые числа, которые в сумме равны K. Например:

[0+, 0+, 0+, 0+] where the sum is 6

Теперь, чтобы решить эту проблему, начните с N = 1. Решение очевидно просто [6]. При N = 2 решение следующее:

[0,6] [1,5] [2,4] [3,3] [4,2] [5,1] [6,0]

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

sumsTo k n
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [0..k]
        s <- sumsTo (k-i) (n-1)
        return (i : s)

Случай n == 1 довольно прост для понимания: он просто возвращает одну комбинацию : [k] . В случае n> 1 здесь действительно происходит вложенный цикл. По сути, он говорит:

for each number i from 0 to k
    for each s in sumsTo (k-i) (n-1)
        prepend i to s

Хотя этот алгоритм не совсем решает вашу проблему, в целом полезно знать.

Теперь мы хотим, чтобы алгоритм работал иначе, чтобы обрабатывать то, как элементы среднего списка не могут быть нулевыми. В таких случаях мы хотим использовать i <- [1..k] вместо i <- [0..k] . Это не имеет значения для конечного числа, поскольку у него нет свободы воли (это зависит исключительно от суммы предыдущих пунктов). Подойдя ближе, мы можем сказать:

sumsTo k n
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [1..k]
        s <- sumsTo (k-i) (n-1)
        return (i : s)

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

sumsTo k n first_start
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [first_start..k]
        s <- sumsTo (k-i) (n-1) 1
             -- make subsequent sumsTo calls start from 1 instead of 0
        return (i : s)

Это дает нам нужные последовательности, заданные K (количество нулей) и N (количество внутренних групп нулей плюс 2). Остается только преобразовать последовательности (например, превратить [1,1,0] в «01»).Мы могли бы пойти дальше и встроить стрингификацию непосредственно в наш рекурсивный алгоритм.

Подводя итог, вот решение на Haskell:

import Data.List

sumsTo k n first_start
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [first_start..k]
        s <- sumsTo (k-i) (n-1) 1
        return (i : s)

-- remove any xes found at the beginning or end of list
trim x list
    = dropWhile (== x)
    $ reverse
    $ dropWhile (== x)
    $ reverse
    $ list

-- interleave [1,3,5] [2,4] = [1,2,3,4,5]
interleave xs ys = concat $ transpose [xs,ys]

solve input = solutions where
    -- pull out groups of 1s and put them in a list
    groupsOfOnes = filter ((== '1') . head) $ group input

    -- count 0s
    k = length $ filter (== '0') input

    -- trim outer 0s
    trimmed = trim '0' input

    -- count inner groups of 0s
    innerGroups = length $ filter ((== '0') . head) $ group trimmed

    -- n is number of outer groups (which is innerGroups + 2)
    n = innerGroups + 2

    -- compute our solution sequences
    -- reverse them so our answer will be in lexicographic order
    sequences = reverse $ sumsTo k n 0

    -- to transform a sequence into a group of zeros,
    -- simply make strings of the indicated number of zeros
    groupsOfZeros seq = [replicate n '0' | n <- seq]

    -- a solution for a sequence is just the zeros interleaved with the ones
    solution seq = concat $ interleave (groupsOfZeros seq) groupsOfOnes

    solutions = map solution sequences

main = do
    input <- getLine
    putStr $ unlines $ solve input

В заключение я рекомендую изучить Haskell, чтобы вы могли быстрее создавать прототипы алгоритмов: -)

Если ваш шаблон 00101 , как в примере, то вы можете рассмотреть один из способов создания шести шаблонов:

Посмотрите на шаблон 0000 , затем выберите два нулей заменить на единицы. Теперь у вас будет что-то вроде 0011 . Теперь просто вставьте 0 после каждого 1 (кроме последнего). Теперь у вас будет 00101 .

Обратите внимание, что вы выбираете два места из четырех, и есть шесть различных возможных способов сделать это (в соответствии с тем, что вы написали). Теперь вам просто нужно выбрать два бита, которые нужно перевернуть. Вы можете использовать что-то вроде алгоритма, указанного по этой ссылке: Генерация комбинаций