Как найти n-ю бинарную перестановку?

Question

Это последний недостающий элемент, который мне нужен для завершения моего алгоритма сжатия, нового. Предположим, у меня есть 4 бита с 2 битами, установленными как 1, 0011. Общее количество перестановок для этого номера - 0011, 0101, 0110, 1001, 1010, 1100, 6 случаев. Это можно вычислить с помощью расчета.

4!/((2!) (4-2)!) = 6

Теперь я хочу, чтобы найти n-ю последовательность, например, 1-й номер 0011, второе число 0101. Так что если я скажу n = 5 , Я хочу иметь возможность получить 5-ю последовательность перестановок 1010 от начального 0011. Как мне это сделать?

Answer 1

Если в двоичном коде всего два, это не так сложно.

Когда самый высокий 1 бит находится на позиции x, число перестановок составляет x.

Таким образом, наивысшее положение бита является наименьшим a (начиная с 0), при условии, что a*(a+1)/2 >= n. Вы можете легко найти a петлей O (n).

Тогда наименьшее положение бит a*(a+1)/2-n (начинается с 0)

Например, когда n 5, наименьший a равен 3, а наименьшее положение бит равен 1, так что ответ 1010