Быстрый способ вычисления n-й последовательности битов размера b с установленным k битами?

Question

Я хочу разработать способ представления всех комбинаций битов b с установленным битом k (равным 1).Это должен быть способ, который с учетом индекса может быстро связать двоичную последовательность, и наоборот.Например, традиционный подход, который я подумал, заключается в том, чтобы генерировать числа в следующем порядке, например: для b = 4 и k = 2:

0-0011

1-0101

2- 0110

3- 1001

4-1010

5-1100

Если мне дана последовательность '1010', яЯ хочу иметь возможность быстро сгенерировать число 4 в качестве ответа, и если я дам число 4, я хочу иметь возможность быстро сгенерировать последовательность «1010».Однако я не могу найти способ сделать это без необходимости генерировать все последовательности, которые идут до (или после).Нет необходимости генерировать последовательности в таком порядке, вы можете выполнить 0-1001, 1-0110, 2-0011 и т. Д., Но не должно быть повторений между 0 и (комбинация b выбирает k) - 1и все последовательности должны быть представлены.

Как бы вы подошли к этому?Есть ли лучший алгоритм, чем тот, который я использую?

Answer 1

Предложение

pkpnd находится на правильном пути, по сути, обрабатываете по одной цифре за раз, и если это 1, подсчитайте количество вариантов, которые существуют под ним, с помощью стандартной комбинаторики.

nCr() можно заменить на предварительное вычисление таблицы, требующее O(n^2) хранения / времени.Может быть другое свойство, которое вы можете использовать, чтобы уменьшить количество nCr, которое вам нужно сохранить, используя свойство абсорбции вместе со стандартной рекурсивной формулой .

Даже с тысячами битов эта таблица не должна быть слишком большой.Хранение ответа также не должно быть слишком плохим, так как 2 ^ 1000 - это ~ 300 цифр.Если бы вы имели в виду сотни тысяч , тогда это был бы другой вопрос.:)

import math

def nCr(n,r):
    return math.factorial(n) //  math.factorial(r) //  math.factorial(n-r)

def get_index(value):
  b = len(value)
  k = sum(c == '1' for c in value)
  count = 0
  for digit in value:
    b -= 1
    if digit == '1':
      if b >= k:
        count += nCr(b, k)
      k -= 1
  return count

print(get_index('0011')) # 0
print(get_index('0101')) # 1
print(get_index('0110')) # 2
print(get_index('1001')) # 3
print(get_index('1010')) # 4
print(get_index('1100')) # 5

Хороший вопрос, кстати.