Быстрое кодирование сбалансированных векторов

10

Легко видеть, что для любого существует отображение 1-1 F из {0,1} n в {0,1} n + O ( log n ) такое, что для любого x вектор F ( x ) равен " сбалансированный », т. е. имеет равное количество единиц и нулей. Можно ли определить такое F, чтобы при заданном x мы могли эффективно вычислить F ( x ) ?nFnn+O(logn)xF(x)FxF(x)

Спасибо.

Петр
источник
Я предполагаю, что под «эффективным» вы подразумеваете O (n) или около того, исключая аргумент «повторных случайных испытаний»?
Суреш Венкат
@Suresh, Вы могли бы набросать аргумент "повторных случайных испытаний"?
Эмиль
Один из способов доказать, что отображение существует, - это вероятностный метод: выбрать F случайным образом, и затем отображение работает с некоторой вероятностью. это то, что я имел в виду.
Суреш Венкат
1
Вопрос совершенно четко определен, но, на мой взгляд, название вводит в заблуждение. Я бы не назвал отображение F, удовлетворяющее указанному условию, «кодированием сбалансированных векторов», если только F не является биективным. Это больше походит на кодирование п-битовую строку с помощью сбалансированного вектора.
Цуёси Ито
Я имею в виду «совершенно четко определенные», вплоть до, возможно, различных интерпретаций «эффективно». Но это не главное в моем предыдущем комментарии.
Цуёси Ито

Ответы:

12

Давайте рассмотрим битные строки x . Определения:NИкс

  • = строка битов x с последнимидополненными битами i .е(Икс,я)Икся
  • = "дисбаланс" x : число 1 с в x - число 0 с в x .б(Икс)ИксИкс -Икс

Теперь исправьте строку . Рассмотрим функцию g ( i ) = b ( f ( x , i ) ) . Замечания:Иксг(я)знак равноб(е(Икс,я))

  • .г(0)знак равноб(Икс)
  • .г(N)знак равно-г(0)
  • для всех я . Мы либо удаляем один 0 и добавляем один 1, либо наоборот.|g(i)g(i+1)|=2i

Теперь следует, что существует такое , что - 1 g ( i ) + 1 .i1g(i)+1

Следовательно, мы можем построить -битную строку y следующим образом: объединить f ( x , i ) и двоичное кодирование индекса i . Абсолютное значение дисбаланса у составляет O ( log n ) . Более того, мы можем восстановить x с учетом y ; отображение биекция.(n+O(logn))yf(x,i)iyO(logn)xy

Наконец, вы можете добавить фиктивных битов, которые уменьшают дисбаланс y с O ( log n ) до 0 .O(logn)yО(журналN)0

Юкка Суомела
источник
b (x) в 3-й строке должно быть b (y).
Эмиль
Я думаю, что вам, возможно, нужно добавить еще один бит в строку x, чтобы убедиться, что она имеет четную длину (чтобы вы могли быть уверены, что g (i) равно нулю для некоторого i).
Эмиль
@Emil: я не утверждаю, что будет нулем для некоторых i ; достаточно, чтобы абсолютное значение g ( i ) было «довольно малым» для некоторого i (не более логарифмического значения было бы достаточно, но легко показать, что для некоторого i оно будет не более 1 ). г(я)яг(я)я1я
Юкка Суомела
@Jukka: Ах да, я вижу.
Эмиль
1
Но да, вы правы, есть много вариантов одного и того же базового подхода. Например, как вы предложили, вы можете сначала использовать бит дополнения, чтобы гарантировать, что будет равен нулю для некоторого i ; затем вы можете кодировать i , используя пары битов 01 или 10 , то есть 2 log ( n ) дополнительных бит; тогда результат объединения строго сбалансирован, и вам не нужно ничего добавлять. г(я)яя01102журнал(N)
Юкка Суомела
9

Используйте отображение, которое сохраняет лексикографический порядок. Для того, чтобы найти -м длина- п сбалансированный вектор с п / 2 1 - х, это сделать рекурсивно: если к ( п - 1knn/2, затем установите первый бит 0 и затем найдитевекторk-йдлины-(n-1)сn/21 для завершения оставшихсяn-1битов. В противном случае установите первый бит 1 и найдитеk-(n-1k(n1n/2)k(n1)n/2n1-йвектордлины(n-1)сn/2-11.k(n1n/2)(n1)n/21

Zeyu
источник
1
И если вы повторно используете значение биномиального коэффициента для вычисления следующего требуемого биномиального коэффициента, весь алгоритм выполняется за O (n) времени.
Цуёси Ито
Спасибо! Это имеет смысл. Я предполагаю, что время выполнения будет зависеть от вычислительной модели. Если вы можете выполнять операции над n-битными числами в единицу времени, реализация Tsuyoshi Ito будет выполняться за O (n) времени. С другой стороны, если вы посчитаете битовые операции, я думаю, что время будет O (n ^ 2).
Петр