Легко видеть, что для любого существует отображение 1-1 F из {0,1} n в {0,1} n + O ( log n ) такое, что для любого x вектор F ( x ) равен " сбалансированный », т. е. имеет равное количество единиц и нулей. Можно ли определить такое F, чтобы при заданном x мы могли эффективно вычислить F ( x ) ?
Спасибо.
Ответы:
Давайте рассмотрим битные строки x . Определения:n x
Теперь исправьте строку . Рассмотрим функцию g ( i ) = b ( f ( x , i ) ) . Замечания:x g(i)=b(f(x,i))
Теперь следует, что существует такое , что - 1 ≤ g ( i ) ≤ + 1 .i −1≤g(i)≤+1
Следовательно, мы можем построить -битную строку y следующим образом: объединить f ( x , i ) и двоичное кодирование индекса i . Абсолютное значение дисбаланса у составляет O ( log n ) . Более того, мы можем восстановить x с учетом y ; отображение биекция.(n+O(logn)) y f(x,i) i y O(logn) x y
Наконец, вы можете добавить фиктивных битов, которые уменьшают дисбаланс y с O ( log n ) до 0 .O(logn) y O ( журналн ) 0
источник
Используйте отображение, которое сохраняет лексикографический порядок. Для того, чтобы найти -м длина- п сбалансированный вектор с п / 2 1 - х, это сделать рекурсивно: если к ≤ ( п - 1k n n/2 , затем установите первый бит 0 и затем найдитевекторk-йдлины-(n-1)сn/21 для завершения оставшихсяn-1битов. В противном случае установите первый бит 1 и найдитеk-(n-1k≤(n−1n/2) k (n−1) n/2 n−1 -йвектордлины(n-1)сn/2-11.k−(n−1n/2) (n−1) n/2−1
источник