Generate all binary strings of length n with k bits set

Question

What is the best algorithm to find all binary strings of length n containing k bits? For example, if n = 4 and k = 3, then there are ...

0111 1011 1101 1110 

I need a good way to generate this data for any n and any k, so I would prefer it to be done with strings.

Answer 1

This method will generate all integers with exactly N '1' bits.

From https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Calculate the lexicographic next permutation of bits

Suppose we have a pattern of N bits set to 1 in an integer, and we want the next permutation of N 1 bits in the lexicographical sense. For example, if N is 3 and the bit bit is 00010011 , the following patterns will be 00010101 , 00010110 , 00011001 , 00011010 , 00011100 , 00100011 , and so on. The following is a quick way to calculate the next permutation.

 unsigned int v; // current permutation of bits unsigned int w; // next permutation of bits unsigned int t = v | (v - 1); // t gets v least significant 0 bits set to 1 // Next set to 1 the most significant bit to change, // set to 0 the least significant ones, and add the necessary 1 bits. w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 

The __builtin_ctz(v) GNU C compiler, built-in for x86 processors, returns the number of trailing zeros. If you use Microsoft compilers for x86, the internal value is _BitScanForward . They both emit a bsf but equivalents may be available for other architectures. If not, then consider using one of the counting methods the consecutive zero bits mentioned earlier. Here is another version that tends to be slower due to its division operator, but it does not require counting trailing zeros.

 unsigned int t = (v | (v - 1)) + 1; w = t | ((((t & -t) / (v & -v)) >> 1) - 1); 

Thanks to Dario Sneijdermani (Argentina) who provided this on November 28, 2009.

Answer 2

python

 import itertools def kbits(n, k): result = [] for bits in itertools.combinations(range(n), k): s = ['0'] * n for bit in bits: s[bit] = '1' result.append(''.join(s)) return result print kbits(4, 3) Output: ['1110', '1101', '1011', '0111'] 

Explanation:

Essentially, we need to select 1-bit positions. There are n choices for k bits out of n total bits. itertools is a good module that does this for us. itertools.combination (range (n), k) selects k bits from [0, 1, 2 ... n-1], and then simply constructs the string based on these bit indices.

Since you are not using Python, see the pseudo-code for itertools.combination here:

http://docs.python.org/library/itertools.html#itertools.combinations

It should be easily implemented in any language.

Answer 3

Forgetting about implementation ("do it with the help of strings", obviously, is an implementation problem!) - think about the algorithm , for Pete's sake ... just like in your first TAG, man!

What you are looking for are all combinations of K elements from a set of N (indices from 0 to N-1 of the set bits). This is obviously easiest to express recursively, for example, pseudo-code:

 combinations(K, setN): if k > length(setN): return "no combinations possible" if k == 0: return "empty combination" # combinations INcluding the first item: return (first-item-of setN) combined combinations(K-1, all-but-first-of setN) union combinations(K-1, all-but-first-of setN) 

ie, the first element is either present or absent: if it is present, you have K-1 remaining to the end (from the tail of aka all-but-firs), if it is absent, it still remains on the left.

Functional languages ​​with a matching pattern, such as SML or Haskell, can best express this pseudocode (procedural languages ​​like my great love Python can actually mask the problem too deeply, including features that are too rich like itertools.combinations , which does all the hard work for you, and therefore OPENS it from you!).

What are you most familiar with for this purpose - Scheme, SML, Haskell, ...? I will be happy to translate the above pseudo code for you. I can also do this in languages ​​like Python, but since you need to understand the mechanics for this homework, I won’t use too rich functions like itertools.combinations , but rather recursion (and eliminating recursion, if necessary) on more obvious primitives (such as head, tail, and concatenation). But please tell us which language with the pseudo-code are most familiar to you! (You understand that the problem you are reporting is equally equipotent to “get all combinations of K elements or range (N),” right?).

Answer 4

This C # method returns an enumerator that creates all the combinations. Since it creates combinations when you list them, it uses only the stack space, so it is not limited by the memory space in the number of combinations that it can create.

This is the first version I came across. It is limited by a stack space of about 2700:

 static IEnumerable<string> BinStrings(int length, int bits) { if (length == 1) { yield return bits.ToString(); } else { if (length > bits) { foreach (string s in BinStrings(length - 1, bits)) { yield return "0" + s; } } if (bits > 0) { foreach (string s in BinStrings(length - 1, bits - 1)) { yield return "1" + s; } } } } 

This is the second version, which uses a binary bit rather than splitting the first character, so it uses the stack much more efficiently. It is limited only by the memory space for the line that it creates at each iteration, and I checked it to 10,000,000:

 static IEnumerable<string> BinStrings(int length, int bits) { if (length == 1) { yield return bits.ToString(); } else { int first = length / 2; int last = length - first; int low = Math.Max(0, bits - last); int high = Math.Min(bits, first); for (int i = low; i <= high; i++) { foreach (string f in BinStrings(first, i)) { foreach (string l in BinStrings(last, bits - i)) { yield return f + l; } } } } } 

Answer 5

One of the problems with many standard solutions to this problem is that the entire set of lines is generated, and then iterates through, which can exhaust the stack. It quickly becomes cumbersome for any, but the smallest sets. In addition, in many cases only partial sampling is required, but standard (recursive) solutions usually interrupt the task into pieces that are strongly biased in one direction (for example, consider all solutions with a zero start bit, and then all solutions with a single start bit).

In many cases, it would be more desirable to be able to pass a bit string (indicating the choice of an element) to a function and return the next bit string in such a way as to have a minimal change (this is known as gray code) and have a representation of all the elements.

Donald Knuth covers a range of algorithms for this in his Fascicle 3A, Section 7.2.1.3: Creating All Combinations.

There is an approach to solving the Gray Code iterative algorithm for all methods of choosing k elements from n in http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl with a link to the final PHP code indicated in the comment (click to expand it ) at the bottom of the page.

Answer 6

One algorithm that should work:

 generate-strings(prefix, len, numBits) -> String: if (len == 0): print prefix return if (len == numBits): print prefix + (len x "1") generate-strings(prefix + "0", len-1, numBits) generate-strings(prefix + "1", len-1, numBits) 

Good luck

Answer 7

More generally, the function below will give you all possible combinations of indices for the N selection problem K, which you can apply to a string or something else:

 def generate_index_combinations(n, k): possible_combinations = [] def walk(current_index, indexes_so_far=None): indexes_so_far = indexes_so_far or [] if len(indexes_so_far) == k: indexes_so_far = tuple(indexes_so_far) possible_combinations.append(indexes_so_far) return if current_index == n: return walk(current_index + 1, indexes_so_far + [current_index]) walk(current_index + 1, indexes_so_far) if k == 0: return [] walk(0) return possible_combinations 

Answer 8

Python (functional style)

Using python itertools.combinations , you can generate all the options k our n and match these options with a binary array with reduce

 from itertools import combinations from functools import reduce # not necessary in python 2.x def k_bits_on(k,n): one_at = lambda v,i:v[:i]+[1]+v[i+1:] return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)] 

Usage example:

 In [4]: k_bits_on(2,5) Out[4]: [(0, 0, 0, 1, 1), (0, 0, 1, 0, 1), (0, 0, 1, 1, 0), (0, 1, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 0, 0), (1, 0, 0, 0, 1), (1, 0, 0, 1, 0), (1, 0, 1, 0, 0), (1, 1, 0, 0, 0)] 

Answer 9

One possible 1.5 liner:

 $ python -c 'import itertools; \ print set([ n for n in itertools.permutations("0111", 4)])' set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')]) 

.. where k is the number 1 in "0111" .

The itertools module explains equivalents for its methods; see equivalent for call forwarding method .

Answer 10

I would try recursion.

There are n digits with k of them 1s. Another way to see this is a sequence of k + 1 slots with nk 0s distributed between them. That is (mileage 0s followed by 1) k times, then another mileage 0s follows. Any of these runs can have a length of zero, but the total length must be nk.

Think of it as an array of k + 1 integers. Convert to a string at the bottom of the recursion.

Recursively call depth nk, a method that increments one element of an array to a recursive call, and then decreases it, k + 1 times.

Print at a depth of nk.

 int[] run = new int[k+1]; void recur(int depth) { if(depth == 0){ output(); return; } for(int i = 0; i < k + 1; ++i){ ++run[i]; recur(depth - 1); --run[i]; } public static void main(string[] arrrgghhs) { recur(n - k); } 

Some time has passed since I made Java, so there are some errors in this code, but the idea should work.

Answer 11

Are strings faster than an ints array? All solutions that offer strings probably result in a copy of the string at each iteration.

Thus, the most efficient way could be an int or char array to which you are adding. Java has efficient containers for growing, right? Use this if it is faster than a string. Or, if BigInteger is efficient, it is certainly compact, since each bit takes only a bit, not a whole byte or int. But then, to iterate over the bit that you need, and mask a bit, and drag the mask to the next bit position. So it's probably slower if the JIT compilers do not work at this time.

I would post this comment on the original question, but my karma is not high enough. Unfortunately.

Answer 12

Good for this question (where you need to iterate over all the subpatterns in increasing order of their number of set bits), which was marked as a duplicate of this.

We can simply iterate over all the subpatterns, add them to the vector, and sort them by the number of bits set.

 vector<int> v; for(ll i=mask;i>0;i=(i-1)&mask) v.push_back(i); auto cmp = [](const auto &a, const auto &b){ return __builtin_popcountll(a) < __builtin_popcountll(b); } v.sort(v.begin(), v.end(), cmp); 

Another way would be to iterate through all the submasks N times and add a number to the vector if the number of bits set is equal to i in the ith iteration.

Both methods have complexity O (n * 2 ^ n)