Алгоритм нахождения k-го двоичного числа с определенными свойствами
Предположим, мы рассмотрим двоичные числа, которые имеют длину 2n а также n может быть о 1000, Мы ищем kth число (k ограничено 10^9) который имеет следующие свойства:
- Количество
1'sравно количеству0'sчто можно описать следующим образом:#(1) = #(0) - Каждый префикс этого номера должен содержать как минимум столько же
0'sкак1's, Это может быть легче понять после отрицания предложения, а именно: нет префикса, который бы содержал больше1'sчем0's,
И в основном это все. Итак, чтобы прояснить это, давайте сделаем несколько примеров:n=2, k=2мы должны взять двоичное число длины 2n:
0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...
И теперь мы должны найти 2nd число, которое соответствует этим двум требованиям. Итак, мы видим 0011 является первым, и 0101 это второй. Если мы изменим k=3, тогда ответа не существует, так как существуют числа, которые имеют одинаковое количество противоположных битов, но для 0110есть префикс 011 так что число не соответствует второму ограничению, и то же самое будет со всеми числами, которые имеют 1 как наиболее значимый бит.
Так что я сделал до сих пор, чтобы найти алгоритм?
Ну, моя первая идея состояла в том, чтобы сгенерировать все возможные настройки битов и проверить, есть ли у них эти два свойства, но генерация их всех займет O(2^(2n)) что не вариант для n=1000,
Кроме того, я понимаю, что нет необходимости проверять все числа, которые меньше, чем 0011 за n=2, 000111 за n=3и так далее... честно говоря, те, чья половина старших разрядов остается "нетронутой", потому что эти числа не имеют возможности выполнить #(1) = #(0) состояние. Используя это, я могу уменьшить n вдвое, но это мало помогает. Вместо 2 * навсегда у меня есть вечно работающий алгоритм. Это все еще O(2^n) сложность, которая слишком велика.
Есть идеи для алгоритма?
Заключение
Этот текст был создан в результате моих мыслей после прочтения поста Энди Джонса.
Прежде всего, я бы не стал публиковать код, который использовал, поскольку это пункт 6 в следующем документе из публикации Энди Каса 2009. Все, что вам нужно сделать, это рассмотреть nr как то, что я описал как k, Разбирая алгоритм слов Дейка, мы могли бы найти ответ намного быстрее. Однако у этого есть одно узкое место.
while (k >= C(n-i,j))
Учитывая, что n <= 1000Каталонское число может быть довольно огромным, даже C(999,999), Мы можем использовать некоторую арифметику больших чисел, но с другой стороны, я придумал небольшую хитрость, чтобы обойти ее и использовать стандартное целое число.
Мы не хотим знать, насколько велико каталонское число, если оно больше, чем k, Так что теперь мы будем создавать каталонские числа, кеширующие частичные суммы в n x n Таблица.
... ...
5 | 42 ...
4 | 14 42 ...
3 | 5 14 28 ...
2 | 2 5 9 14 ...
1 | 1 2 3 4 5 ...
0 | 1 1 1 1 1 1 ...
---------------------------------- ...
0 1 2 3 4 5 ...
Для генерации это довольно тривиально:
C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y) where y > 0 && y < x
C(x,y) = C(x,y-1) where x == y
Так что мы можем видеть только это:
C(x,y) = C(x,y-1) + C(x-1,y) where y > 0 && y < x
может вызвать переполнение.
Остановимся на этом и дадим определение.
k-flow - это не реальное переполнение целого числа, а скорее информация, значение которой C(x,y) больше чем k,
Моя идея состоит в том, чтобы после каждого запуска вышеуказанной формулы проверять, C(x,y) терше чем k или любой из компонентов суммы -1, Если это мы ставим -1 вместо этого, который будет действовать как маркер, что k-flow случилось. Я думаю, это совершенно очевидно, что если k-flow число суммируется с любым положительным числом, это все еще будет k-flowed в частности сумма 2 k-flowed числа k-flowed,
Последнее, что мы должны доказать, это то, что нет возможности создать реальное переполнение. Реальное переполнение может произойти, только если мы подведем итог a + b который не из них k-flowed но в сумме они породили реальное переполнение.
Конечно, это невозможно, поскольку максимальное значение можно описать как a + b <= 2 * k <= 2*10^9 <= 2,147,483,647 где последним значением в этом неравенстве является значение int со знаком. Я предполагаю также, что int имеет 32 бита, как в моем случае.
2 ответа
Числа, которые вы описываете, соответствуют словам Дейка. Часть 2 Kasa 2009 дает простой алгоритм для перечисления их в лексикографическом порядке. Его ссылки должны быть полезны, если вы хотите продолжить чтение.
В качестве отступления (и предупреждаю, что я наполовину сплю, когда пишу это, так что это может быть неправильно), статья в Википедии отмечает, что количество слов Дейка длины 2n это n каталонское число, C(n), Возможно, вы захотите найти самый маленький n такой, что C(n) больше чем k Вы ищете, а затем перечислите слова Дейка, начиная с X^n Y^n,
Прошу прощения за неправильное понимание этой проблемы в прошлый раз, поэтому я редактирую ее, и теперь я могу обещать исправление, и вы можете сначала протестировать код, сложность O(n^2)подробный ответ следующий
Во-первых, мы можем сопоставить проблему со следующей
Мы ищем kth largest число (k ограничено 10^9) который имеет следующие свойства:
- Количество
1'sравно количеству0'sчто можно описать следующим образом:#(1) = #(0) - Каждый префикс этого номера должен содержать как минимум столько же [[
1'sкак0's]], что означает: нет префикса, который бы содержал больше [[0'sчем1's]].
Давайте приведем пример, чтобы объяснить это: пусть n=3 а также k=4количество удовлетворенных чисел 5, и картина ниже объясняет, что мы должны определить в предыдущей проблеме и новой проблеме:
| 000111 ------> 111000 ^
| 001011 ------> 110100 |
| 001101 ------> 110010 |
| previous 4th number 010011 ------> 101100 new 4th largest number |
v 010101 ------> 101010 |
так что после того, как мы решим новую проблему, нам просто нужно поразрядно нет.
Теперь главная проблема - как решить новую проблему. Во-первых, пусть A будет массивом, поэтому A[m]{1<=m<=2n} только может быть 1 или 0, пусть DP[v][q] быть количеством чисел, которые удовлетворяют условию 2 и условию #(1)=q в {A[2n-v+1]~A[2n]}, Итак DP[2n][n] количество удовлетворенных чисел.
A[1] может быть только 1 или 0, если A[1]=1, количество номеров DP[2n-1][n-1], если A[1]=0, количество номеров DP[2n-1][n]Теперь мы хотим найти kth largest номер, если k<=DP[2n-1][n-1], kth largest номер-х A[1] должно быть 1, то мы можем судить A[2] с DP[2n-2][n-2]; если k>DP[2n-1][n-1], kth largest номер-х A[1] должно быть 0 и k=k-DP[2n-1][n-1]тогда мы можем судить A[2] с DP[2n-2][n-1], Так что с той же теорией, мы можем судить A[j] один за другим, пока нет номера для сравнения. Теперь мы можем привести пример, чтобы понять (n=3, k=4)
(Мы используем динамическое программирование для определения матрицы DP, уравнение DP - это DP [v] [q] = DP [v-1] [q-1] + DP [v-1] [q])
Intention: we need the number in leftest row can be compared,
so we add a row on DP's left row, but it's not include by DP matrix
in the row, all the number is 1.
the number include by bracket are initialized by ourselves
the theory of initialize just follow the mean of DP matrix
DP matrix = (1) (0) (0) (0) 4<=DP[5][2]=5 --> A[1]=1
(1) (1) (0) (0) 4>DP[4][1]=3 --> A[2]=0, k=4-3=1
(1) (2) (0) (0) 1<=DP[3][1]=3 --> A[3]=1
(1) (3) 2 (0) 1<=1 --> a[4]=1
(1) (4) 5 (0) no number to compare, A[5]~A[6]=0
(1) (5) 9 5 so the number is 101100
Если вы не поняли ясно, вы можете использовать код, чтобы понять
Намерение：DP[2n][n] очень быстро увеличивается, поэтому код может работать только тогда, когда n<=19в проблеме n<1000, так что вы можете использовать программирование больших чисел, а код можно оптимизировать с помощью битовой операции, поэтому код является лишь справочным
/*--------------------------------------------------
Environment: X86 Ubuntu GCC
Author: Cong Yu
Blog: aimager.com
Mail: funcemail@gmail.com
Build_Date: Mon Dec 16 21:52:49 CST 2013
Function:
--------------------------------------------------*/
#include <stdio.h>
int DP[2000][1000];
// kth is the result
int kth[1000];
void Oper(int n, int k){
int i,j,h;
// temp is the compare number
// jishu is the
int temp,jishu=0;
// initialize
for(i=1;i<=2*n;i++)
DP[i-1][0]=i-1;
for(j=2;j<=n;j++)
for(i=1;i<=2*j-1;i++)
DP[i-1][j-1]=0;
for(i=1;i<=2*n;i++)
kth[i-1]=0;
// operate DP matrix with dynamic programming
for(j=2;j<=n;j++)
for(i=2*j;i<=2*n;i++)
DP[i-1][j-1]=DP[i-2][j-2]+DP[i-2][j-1];
// the main thought
if(k>DP[2*n-1][n-1])
printf("nothing\n");
else{
i=2*n;
j=n;
for(;j>=1;i--,jishu++){
if(j==1)
temp=1;
else
temp=DP[i-2][j-2];
if(k<=temp){
kth[jishu]=1;
j--;
}
else{
kth[jishu]=0;
if(j==1)
k-=1;
else
k-=DP[i-2][j-2];
}
}
for(i=1;i<=2*n;i++){
kth[i-1]=1-kth[i-1];
printf("%d",kth[i-1]);
}
printf("\n");
}
}
int main(){
int n,k;
scanf("%d",&n);
scanf("%d",&k);
Oper(n,k);
return 0;
}