• Coding

  • Combinations of binary representations

I was following the website for months now... and since i need help.. I'll ask here :D

I need a way (best way) to find all binary representations given the number of ones and the number of bits in the binary.
suppose i have a binary that consists of 4 bits.
2 of these bits should be 1 and the others (other 2) are 0.
how many binary representation can i make?
the answer will be:
1100
1010
1001
0110
0101
0011

how can i generate such a combination...
is there any math formula that can tell me that a number 3 (0011) has 2 ones in its binary?
i know i can convert the number to binary and then count the number of ones in it... is there any faster way to know how many ones does a binary representation of a number has?

i don't care what language is used.. i just need the algorithm...
For the first one i can tell how many combinations there are not what are they:
if you have a binary of x bits which a are zeroes and b are ones (a+b=x)
so there will be xCa or xCb combinasions of this binary (the C is the combination formula , and note that xCa = xCb)

for the second one here is a method but i don;t know if it's faster:
let's say your number is 1993 you start to subtract the biggest power of two that will not make the number negative so here it's 1024 ... and so on until you get 0

1993 -2^10 -2^9 -2^8 -2^7 -2^6 -2^3 -2^0 =0
so in 1993 there are 7 ones (you count how many subtractions you made)
This is for the first one in php: 
<?php
$bits=4;
$ones=2;

$max=pow(2,$bits);
for($i=0;$i<$max;$i++) {
	$binary=str_pad(decbin($i), $bits, "0", STR_PAD_LEFT); 
	if(count(explode("1",$binary))-1==$ones) {
		echo $binary ."<br/>";
	}
}
?>
This is a pure case of combination probability: nCr = n!/r!(n-r)! where n is number of total bits and r is number of one bits

Example:

4 bits total, 2 bits as one => 4C2 = 4!/2!(2!) = 6 (cases you stated)

5 bits total, 3 bits as one => 5C3 = 5!/3!(2!) = 10 which are:
00111
01011
10011
01101
10101
01110
11100
10110
11010
11001

5 bits total, 2 bits as one => 5C2 = 5!/2!(3!) = 10 which are:
00011
00110
01010
10010
00101
01001
10001
11000
10100
10010
What mesa said is true. To understand why, think of it like this:
Number of bits = N. Number of ones = K.
If you assign each one of the bits a number (according to its position in the bit-string), the problem reduces to picking K positions from a bag holding N unique positions.

For a N=3 and K=2: positions {1,2,3}
011: {2,3}
101: {1,3}
110: {1,2}
the combinations can be generated incrementally, using a lexicographic ordering of the positions: 
#include <iostream>
using namespace std;

int fact(int n) {
	return n < 2 ? 1 : n * fact(n - 1);
}

int main (int argc, char const *argv[]) {
	int n = atoi(argv[1]);
	int r = atoi(argv[2]);
	int m = fact(n) / (fact(r) * fact(n - r));
	int *cbs = new int[m * n];
	int *nbs = new int[m];
	int *current = new int[r + 1];

	for (int k = 0; k < r; k++) {
		current[k] = k;
	}
	current[r] = n + 1;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < r; j++) {
			cbs[i * n + current[j]] = 1;
			cout << current[j] << " ";
		}
		cout << '\n';

		current[r - 1]++;

		for (int k = r - 1; k >= 0; k--) {
			if (current[k + 1] == current[k] + 1) {
				current[k - 1]++;
			} else {
				if (k < r - 1) {
					for (k = k + 1; k < r; k++) {
						current[k] = current[k - 1] + 1;
					}
				}
				k = 0;
			}
		}
	}

	cout << n << 'C' << r << " = " << m << '\n';

	for (int i = 0; i < m; i++) {
		nbs[i] = 0;

		for (int j = n - 1; j >= 0; j--) {
			cout << cbs[i * n + j];
			nbs[i] = 2 * nbs[i] + cbs[i * n + j];
		}
		cout << '\t' << nbs[i] << '\n';
	}

	delete [] current;
	delete [] cbs;
	return 0;
}
binary_combinations 6 3
0 1 2 
0 1 3 
0 1 4 
0 1 5 
0 2 3 
0 2 4 
0 2 5 
0 3 4 
0 3 5 
0 4 5 
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
6C3 = 20
000111	7
001011	11
010011	19
100011	35
001101	13
010101	21
100101	37
011001	25
101001	41
110001	49
001110	14
010110	22
100110	38
011010	26
101010	42
110010	50
011100	28
101100	44
110100	52
111000	56
@geek: any references on this particular instance of lexicographic generation?
thanks a lot for the responses.. and thank you geek for the algorithm... it was really helpful!
mesa thanks for the math explanation... but i have one big issue.
the smallest data I'll be using is:
N=450
r=420
that will give me: 450C420 = 55387347440880259761858516389210250751744820880 results!!
how the heck can i save this into the memory?!?
Search lebgeeks for LebInt to help you with large integers. I think I have a decent enough implementation there.
arithma wroteSearch lebgeeks for LebInt to help you with large integers. I think I have a decent enough implementation there.
Best answer ever to your problem, JIZZ :)
@geek: The algorithm you wrote goes out of bounds on the last iteration of i on this line (the middle one): 
            if (current[k + 1] == current[k] + 1) {
                current[k - 1]++;
            } else {
Here's a recursive implementation of the sequence generation. It returns the list inverted though: 
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> combinations(int n, int c){
	// simple case
	if(c == 0){
		vector<vector<int>> result_arr(1);
		return result_arr;
	}

	// composite case
	vector<vector<int>> acc(0);
	for(int i = n - 1; i >= c - 1; i--){
		vector<vector<int>> rest = combinations(i, c - 1);
		for(unsigned j = 0; j < rest.size(); j++){
			rest[j].insert(rest[j].begin(), i);
			acc.push_back(rest[j]);
		}
	}
	return acc;
}

int main (int argc, char const *argv[]) {
	auto set = combinations(atoi(argv[1]), atoi(argv[2]));
	for(unsigned i = 0; i < set.size(); i++){
		for(unsigned j = 0; j < set[i].size(); j++){
			cout << set[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
I couldn't wrap my head around geek's implementation, so here's my own.
It has a feature that given any combination, it will return the next lexicographic combination. Memory requirements are minimal (for just calculating the next combination).

You do need to output the stuff out though.
#include <iostream>
#include <vector>
using namespace std;

bool my_next(vector<int> & v, int n){
	int L = v.size();
	int k = L-1;
	int max = n-1;

	while(k >= 0 && v[k] == max){
		k--;
		max--;
	}
	
	if(k < 0) return false;

	v[k]++;
	while(++k < L){
		v[k] = v[k-1] + 1;
	}

	return true;
}

int main (int argc, char const *argv[]) {
	vector<int> v;
	v.push_back(0);
	v.push_back(1);
	while(my_next(v, 4));
	return 0;
}
@arithma, you're using the same technique. also, you're right about the out of bounds error, although it only occurs in the last iteration when no longer needed.
@JIZZ, 450C420 would take many many many years.