Skip to content

Instantly share code, notes, and snippets.

@tzengyuxio
Last active August 29, 2015 14:03
Show Gist options
  • Save tzengyuxio/5478a1f29cb2a8532238 to your computer and use it in GitHub Desktop.
Save tzengyuxio/5478a1f29cb2a8532238 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment