n番目のバイナリ置換を見つける方法は？

これは私の圧縮アルゴリズム、新しいものを完成するために必要な最後に欠けている部分です。たとえば、2ビットが1,1100に設定された4ビットがあるとします。この数の順列の総数は0011,0101,11010,1001,1010,1100,6ケースです。これは計算を使用して計算できます。n番目のバイナリ置換を見つける方法は？

4！ /（（2！）（4-2）！）= 6

ここで、n番目のシーケンスを見つけることができます。例えば、1番目の番号は0011、2番目の番号は0101です。したがって、n = 5と言うと、私は、最初の0011から5番目の置換シーケンス1010を得ることができるようにしたいと思います。これをどうやって行うのですか？

出典

2016-10-02 user1352777

あなたはそれらを反復することができます、この解決策は63ビットの数字まで動作します：https://codereview.stackexchange.com/a/162983/21279 – RobAu

バイナリに1つしかない場合は、あまり難しくありません。

xの位置に上位1ビットがある場合、置換の数はxです。

したがって、最も高いビット位置は、a*(a+1)/2 >= nに従うと、a（0から開始）の最小値です。 O（n）ループでaを簡単に見つけることができます。

そして少なくともビット位置はa*(a+1)/2-n（0から始まる）

たとえばがnが5である場合、最小aは3であり、答えは1010

なるように前記ビット位置が1であります

出典

2016-10-02 06:45:23

こんにちは、00111とn = 8のような大きな数字についてはどうですか？ – user1352777

私は中間ビットを見つけることを意味します – user1352777

n番目のバイナリ置換を見つける方法は？

答えて

関連する問題