Восстановление элемента массива, заданных сумм элементов в индексах, соответствующих битовым маскам

предположим, что существует массив E на 2^n элементы. Например:

E = [2, 3, 5, 7, 11, 13, 17, 19]

к сожалению, кто-то уже вскарабкался массива. Они взяли все элементы, индекс которых в двоичном виде имеет вид 1XX, и добавил их в элементы по индексу 0XX (то есть они сделали E[0] += E[1],E[2] += E[3] и т. д. Затем они сделали то же самое для индексов, таких как X1X на X0X и XX1 на XX0.

более конкретно, они запустили это псевдо-код над массивом:

def scramble(e):
    n = lg_2(len(e))
    for p in range(n):
        m = 1 << p
        for i in range(len(e)):
            if (i & m) != 0:
                e[i - m] += e[i]

С точки зрения нашего примера, это вызывает:

E_1 = [2+3, 3, 5+7, 7, 11+13, 13, 17+19, 19]
E_1 = [5, 3, 12, 7, 24, 13, 36, 19]

E_2 = [5+12, 3+7, 12, 7, 24+36, 13+19, 36, 19]
E_2 = [17, 10, 12, 7, 60, 32, 36, 19]

E_3 = [17+60, 10+32, 12+36, 7+19, 60, 32, 36, 19]
E_3 = [77, 42, 48, 26, 60, 32, 36, 19]

вам дается массив после того, как он был скремблирован (т. е. ваш вход E_3). Ваша цель-восстановить исходный первый элемент E, (т. е. число 2).

один из способов вернуть 2-это отменить все скремблирование. Запустите код шифрования, но с += заменить на -=. Однако, делать это очень дорого. Требуется n 2^n время. Есть ли более быстрый способ?

Альтернативный Вариант

заявленный другой путь, я даю вам массив S где элемент с индексом i - это сумма всех элементов с индексом j удовлетворяя (j & i) == iиз списка E. Например, S[101110] и E[101110] + E[111110] + E[101111] + E[111111]). Как дорого восстановить элемент E, учитывая S?

элемента 111111... легко, потому что S[111111...] = E[111111...], а S[000000...] зависит от все с E неравномерно, так что, кажется, труднее вернуться.

Extended

что делать, если мы не просто хотим восстановить исходные элементы, но хотите восстановить суммы исходных элементов, которые соответствуют маске, которая может указать must-be-1, no-constraint, и должно быть-0? Это сложнее?

1 ответ:

назовите количество элементов в массиве N, и размер используемых битовых масок B так N = 2^B.

вы не можете сделать лучше, чем O(N).

пример решения в вопросе, который просто запускает скремблирование в обратном порядке, принимает O(N B) времени. Мы можем свести это к O(N) отбрасывая элементы, которые не будут способствовать фактическому значению мы читаем в конце. Это делает расшифровку намного проще, на самом деле: просто итеративно вычесть последнее половину массива из первой половины, затем отбросить последнюю половину, пока у вас не останется один элемент.

def unscrambleFirst(S):
    while len(S) > 1:
        h = len(S)/2
        for i in range(h):
            S = S[:h] - S[h:] #item-by-item subtraction
    return S[0]

невозможно ехать быстрее, чем O(N). Мы можем доказать это с помощью линейной алгебры.

  • исходный массив имеет N независимые элементы, т. е. это вектор с N степеней свободы.
  • операция скремблирования использует только линейные операции и поэтому эквивалентна умножению этого вектора на матрицу. (Матрица [[1, 1], [0, 1]] черепица внутри себя B раз; это в конечном итоге выглядит как треугольник Серпинского).
  • матрица операций скремблирования обратима (поэтому мы можем отменить скремблирование).
  • поэтому скремблированный вектор должен иметь N степеней свободы.
  • но наши O(N) решение представляет собой линейную комбинацию каждого элемента скремблированного вектора.
  • а так как элементы скремблированный вектор должен быть линейно независимым, чтобы было N степеней свободы в нем, мы не можем переписать использования какого-либо одного элемента с использованием других.

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