Существует очень эффективное решение этой проблемы, для которого требуется всего несколько строк кода, но это довольно сложно объяснить. В любом случае, у меня будет go.
Предположим, вам нужно уменьшить список, скажем, из 6 чисел, которые все равны нулю, за исключением одного элемента. По симметрии нужно рассмотреть только три случая:
1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 0 0 0 0 1 0 0 1 0 1 0
1 0 0 1 1 0 1 1 1
1 0 0 1 0 0
1 1 0
В первом случае, один «1» на краю на самом деле ничего не делает. Это в основном просто остается на месте. Но в двух других случаях включается больше элементов списка, и ситуация более сложная. «1» во втором элементе списка дает результат «1», а «1» в третьем элементе - «0». Есть ли простое правило, объясняющее это поведение?
Да, есть. Взгляните на это:
Row 0: 1
Row 1: 1 1
Row 2: 1 2 1
Row 3: 1 3 3 1
Row 4: 1 4 6 4 1
Row 5: 1 5 10 10 5 1
Я уверен, что вы видели это раньше. Это треугольник Pascal, где каждая строка получается путем добавления соседних элементов, взятых из строки выше. Большие числа в середине треугольника отражают тот факт, что эти числа получены сложением значений, взятых из более широкого подмножества предыдущих строк.
Обратите внимание, что в строке 5 два числа в середине оба четные, а остальные числа нечетные. Это точно соответствует поведению трех примеров, показанных выше; произведение XOR четного числа «1» равно нулю, а произведение XOR нечетного числа «1» равно «1».
Чтобы прояснить ситуацию, давайте просто рассмотрим четность чисел в этом треугольник (т. е. «1» для нечетных чисел, «0» для четных чисел):
Row 0: 1
Row 1: 1 1
Row 2: 1 0 1
Row 3: 1 1 1 1
Row 4: 1 0 0 0 1
Row 5: 1 1 0 0 1 1
Это фактически называется треугольником Серпинского . Если в этом треугольнике появляется ноль, это говорит нам о том, что не имеет значения, имеет ли ваш список «1» или «0» в этой позиции; это не повлияет на полученное значение, потому что если вы выписали выражение, показывающее значение конечного результата в терминах всех начальных значений в вашем списке, этот элемент будет появляться четное число раз.
Взгляните на строку 4, например. Каждый элемент равен нулю, кроме крайних ребер. Это означает, что если в вашем списке 5 элементов, конечный результат зависит только от первого и последнего элементов в списке. (То же самое относится к любому списку, где число элементов на единицу больше, чем степень 2.)
Строки треугольника Серпинского легко вычислить. Как уже упоминалось в oeis.org / A047999 :
Теорема Лукаса состоит в том, что T (n, k) = 1 тогда и только тогда, когда единицы в двоичном разложении k являются подмножество 1 в двоичном разложении n; или, эквивалентно, k AND NOT n - ноль, где AND и NOT - побитовые операторы.
Итак, после этого длинного объяснения, вот мой код:
def xor_reduction(a):
n, r = len(a), 0
for k in range(n):
b = 0 if k & -n > 0 else 1
r ^= b & a.pop()
return r
assert xor_reduction([1, 0, 0, 1, 0, 1, 1, 1]) == 1
Я сказал, что это было коротко. Если вам интересно, 4-я строка имеет k & -n (k AND минус n) вместо k & ~n (k AND не n), потому что n в этой функции - это число элементов в списке, что на один больше, чем номер строки и ~(n-1) - это то же самое, что и -n (по крайней мере, в Python).