BinaryStateToIndex.cpp

#include <iostream>
#include <bitset>
#include <cmath>
#include <iomanip>

#define NUM_DIGITS 4

using namespace std;

long long C(int m, int n)
{
    if (m<=0)
        return 0;
    if (n==0 || m==n)
        return 1;
    
    int n2 = m-n;
    if (n2 < n) { n = n2; }
    
    long long ans=1;
    for (int i=0; i<n; ++i) {
        ans *= (m-i);
    }
    
    for (int i=0; i<n; ++i) {
        ans /= (i+1);
    }
    
    return ans;
}

int convertBinaryStateToIndex(int bs, int numDigits)
{
    bitset<numDigits> b(bs);
    
    int oneCount = b.count();
    int base = 0;
    int inGroup = 0;
    
    for (int i = 1; i < oneCount; ++i) {
        base += C(numDigits, i);
    }
    
    int oneRemain = oneCount;
    for (int i = numDigits-1; i >= 0; --i) {
        if (b[i] == 1) {
            if (i+1==oneRemain) {
                break;
            }
            inGroup += C(i, oneRemain);
            oneRemain -= 1;
        }
    }
    if (oneCount > 0) inGroup++;
    
    //cout << oneCount << ": " << setw(2) << base << "," << setw(2) << inGroup ;
    return base + inGroup;
}

int main()
{
    int max = pow(2, NUM_DIGITS);
    for (int i=0;i<max;++i) {
        cout << setw(6) << i << " == " << bitset<NUM_DIGITS>(i) << " => " << convertBinaryStateToIndex(i, NUM_DIGITS) << endl;
    }
   
   return 0;
}