如何找到第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