How can I find all possible binary representations given the number of 1s?

Question

Given N as the number of bits and K as the Number of 1s, how can i generate all binary representations that contain K ones and N-k zeros?

in other words i have:

N=4 //number of bits
K=2 //number of ones

All possible binary values containing N bits,K ones and N-K zeros are:

i have nothing so far. i am not asking for code. i am just asking for the best way to do it? an algorithm? a pseudocode? maybe a discussion?

Edit: I am asking for code/pseudocode to solve the problem... and not a math formula...

This is just N choose K, = n!/((n-k)! * k!) - heh, just realized he wasn't asking for the count. — deepee1, Jul 29 '11 at 16:29
Did anyone read the question? They're not asking how to find out the number of combinations. They're asking how to *generate* all the combinations. — Artomegus, Jul 29 '11 at 16:31
This same question has come up on at least once on SO before - if it weren't about to be closed as "off topic" I'd go and find the dupe(s). — Paul R, Jul 29 '11 at 16:44

score 5 · Answer 1 · edited Jul 29 '11 at 16:26

5

Remember combinations and permutations from math class?

Google it and find the equation, use: http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html for a quick calculation :)

edited Jul 29 '11 at 16:26

answered Jul 29 '11 at 16:25

John Humphreys

37,047
37
155
255

*fix* that calculator is a little bogus, but its still that kind of problem. Sorry about that, I hadn't played with it. – John Humphreys Jul 29 '11 at 16:30

Guillaume Thomas · Answer 2 · 2011-07-29T16:46:39.317

4

I would say 'recursively' :

Let's say f(K,N) gives you all the possible strings then :

def f(K,N):
  if N=0:
    return []
  else if (K=N):
    return [ones(K)]
  else 
    union(concat('1',f(K-1,N-1)), concat('0',(K,N-1)))

with:

def concat(c,vec):
  retval= []
  for x in vec:
    retval.append(c&x) //& is the concatenation operator
  return retval

ones(K) returns a string composed of K "1"

union(x,y) merge the two vectors x and y

edited Jul 29 '11 at 16:46

answered Jul 29 '11 at 16:30

Guillaume Thomas

2,220
2
24
33

This is great, but its missing an end condition for K: `function f(N,K){ if (N==0) return ['']; if (N==K) return ['1'.repeat(K)]; if (K==0) return ['0'.repeat(N)]; return [...(f(N-1,K-1).map((e)=>'1'+e)),...(f(N-1,K).map((e)=>'0'+e))] }` – Thomas Handorf Sep 24 '18 at 13:18

Andy Hunt · Answer 3 · 2011-07-29T16:36:33.263

1

This is more of a maths question than anything. You're looking for a string of N length with K of them being 1. So you've got N choose K, which is N!/K!*(N-K)! if memory serves - others please correct if I'm wrong!

edited Jul 29 '11 at 16:36

answered Jul 29 '11 at 16:24

Andy Hunt

1,053
1
11
26

Your formula is close but not quite: `n choose k = n!/[k!*(n-k)!]`. – cheeken Jul 29 '11 at 16:28
Sorry, yeah, I should have added in the "*", seeing as this isn't a hand-written form. Added to my answer now. – Andy Hunt Jul 29 '11 at 16:36

score 1 · Answer 4 · answered Jul 29 '11 at 16:25

You want to find all subsets of size K of a set of N elements, say S = {1,2,...,N}. You can easily express this recursively:

A subset of size K of S is either a subset of size K of {1,2,...,N-1}, or it is the union of {N} and a subset of size K-1 of {1,2,...,N-1}. (This is precisely the recurrence relation for the binomial coefficients.)

Once the subset size is bigger than the ambient set size there are no subsets, so that branch of the recursion stops.

score 0 · Answer 5 · answered Jul 29 '11 at 16:25

0

Generate all binaries with N bits. Check each if the have K zeros and K ones. ?. Profit.

answered Jul 29 '11 at 16:25

Vinicius Kamakura

7,665
1
29
43

generate binaries with 64 bit. where's the profit. – fazo Jul 29 '11 at 16:27
you don't _need_ to keep them in memory, you can generate one and test. understand the problem first, come up with a solution. make it work. improve it later. POITROAE – Vinicius Kamakura Jul 29 '11 at 16:30
1

say you need OP's algorithm for 1000 bits. how's your fast? – fazo Jul 29 '11 at 16:32
1

Upvote for trying to answer the actual question instead of giving formula for number of combinations/permutations. – Artomegus Jul 29 '11 at 16:33

score 0 · Answer 6 · answered Jul 29 '11 at 16:26

0

pseudocode:

loop for every position starting at left, pos=position:
 loop for every position starting at pos+1 -> pos2;
   set 1 at pos and pos2;

answered Jul 29 '11 at 16:26

fazo

1,807
12
15

score 0 · Answer 7 · edited May 23 '17 at 12:11

The Binomial Coefficient will give you the total number of solutions. (See "N Choose K").

Use a Hamming Weight to count the number of bits.

int main()
{
    int k = 2;
    for(int i = 0;  i < 16; i++)
       if(BitCount(i) == k)
          cout << i << endl;
}

// Got this function from an SO question (see below)
int BitCount(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Reference: How to count the number of set bits in a 32-bit integer?

score 0 · Answer 8 · answered Jul 29 '11 at 16:34

This is a place to start. I don't have a compiler on me to test, though.

size_t n = 4;
size_t k = 2;

std::vector<bool> bits;

for (size_t i = 0; i < n; i++)
  bits.push_back(i < k ? true : false);

std::sort(bits.begin(), bits.end());

do {
  for (size_t i = 0; i < n; i++)
    cout << ( bits[i] ? '1' : '0' );
  cout << endl;
while(std::next_permutation(bits.begin(), bits.end());

score 0 · Answer 9 · answered Jul 29 '11 at 16:50

0

Recursion will be a good solution here given that you memoize the results somehow or for large n & k , the program might blow and you dont print (and go into further recursion) the cases when n=0 OR n0 (only n>=k will be legal states).

answered Jul 29 '11 at 16:50

Shankhoneer Chakrovarty

690
1
6
19

score -1 · Answer 10 · answered Jul 29 '11 at 16:33

-1

This problem is not unusual, and can be difficult to implement, so you'll be happy to find that most languages have some sort of open source solution (or part of the DK) to solve it.

Java: Permutations and Combinations
Python: itertools

answered Jul 29 '11 at 16:33

cheeken

33,663
4
35
42

score -1 · Answer 11 · answered Jul 29 '11 at 16:34

I think you've already got an algorithm there :)

Start by laying out K number of 1's on the left side padding the rest with 0's

Shift the rightmost 1 N-K-1 times to the right, replacing the previous position with a 0 and capturing the result each time

Keep shifting the 1's until they're all on the right side

done.

score -2 · Answer 12 · edited Jun 04 '12 at 17:34

-2

Each bit can only have 2 possibilities, so just raise your N to power 2.

1 bit, can have two combinations,
2 bit, can have 4 combinations.
3 bit, can have 9 combinations
4 bit, can have 16 combinations

edited Jun 04 '12 at 17:34

Fahim Parkar

30,974
45
160
276

answered Jul 29 '11 at 16:30

Saint

1

That doesn't account for the fact that repeats aren't different answers. 1001 would be present multiple times in that set of 16 combinations which means it wouldn't be unique. His question noted the combinations in a set of 4 bits with 2 forced to 1. I did the same thing wrong at first, that's why I thought the link I provided would work originally :( – John Humphreys Jul 29 '11 at 16:47

How can I find all possible binary representations given the number of 1s?

12 Answers12