Need to get the nth binary permutation.

Oct 2016
33
4
labenon
This is the last missing piece I need to complete my compression algorithm, new one. Let's say I have 4 bits with 2 bits set as 1, 0011. The total number of permutations for this number is 0011, 0101, 0110, 1001, 1010, 1100, 6 cases. This can be computed using the calculation.

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

Now I want to be able to find the nth sequence, for instance 1st number is 0011, second number is 0101. So if I say n=5, I want to be able to get the 5th permutation sequence 1010 from the initial 0011. How do I do this?
 

romsek

Math Team
Sep 2015
2,877
1,609
USA
If you are really using blocks of 4 bits I'd just pre-calculate everything and use a lookup table.

Given available memory these days I'd definitely do this for up to 8 bits, and probably do this for up to 16 bits.
 
  • Like
Reactions: 1 person