如何找到第n個二進制排列？

Question

這是我需要完成我的壓縮算法，最新的一個失蹤的一塊。假設我有4位，其中2位設置爲1,0011.此數字的排列總數爲0011,0101,0110,1001,1010,1100,6個案例。這可以使用計算來計算。

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

現在我想能夠找到第n個序列，例如第一個數字是0011，第二個數字是0101.所以如果我說n = 5 ，我希望能夠從最初的0011獲得第5個排列序列1010.我該怎麼做？

Answer 1

如果二進制文件中只有兩個1，這並不難。

當最高的1位定位在x的位置時，排列的數量是x。

因此，最高位的位置是最小的a（從0開始），受到a*(a+1)/2 >= n的限制。您可以通過O（n）循環輕鬆找到a。

然後至少比特位置是a*(a+1)/2-n（從0開始）

例如，當n是5，最小a是3，並且至少比特位置是1，因此，答案是1010