Google Interview Question
Country: India
Interview Type: In-Person
One can make the following observation:
printing for k
is equivalent to
print all combinations of length k with 0 ones
print all combinations of length k with 1 ones
...
print all combinations of length k with k ones
A second observation is:
print all combinations of length k with n ones
is equivalent to
print (prepend 0 to all combinations of length k-1 with n ones)
print (prepend 1 to all combinations of length k-1 with n-1 ones)
This way we get a recursive function where we can cache intermediary results.
This is obviously more space inefficient than just generating all bit combinations and sorting them in place. Can anyone help me out with runtime analysis and tell me if it's faster?
Python class:
class KBitGenerator:
cache = {}
def generate(self, k):
result = []
for i in range(k + 1):
result += self.generate_for_num(k, i)
return result
def generate_for_num(self, length, num_ones):
if (length, num_ones) in self.cache:
return self.cache[(length, num_ones)]
result = []
if num_ones == 0:
result = [[0] * length]
elif length == num_ones:
result = [[1] * length]
else:
for pattern in self.generate_for_num(length - 1, num_ones):
result.append([0] + pattern)
for pattern in self.generate_for_num(length - 1, num_ones - 1):
result.append([1] + pattern)
self.cache[(length, num_ones)] = result
return result
here is a simple solution in C++:
#include <iostream>
#include <vector>
int bitcount(int aArg) {
int c = 0; // bit count
for(; aArg; c++)
aArg &= aArg -1; // clears the least significat bit
return c;
}
void printBitCombinations(int K) {
std::vector<int> A;
for(int i = 0; i <= K; ++i) {
for(int j = 0; j < 1 << K; ++j) {
if(bitcount(j) == i)
A.push_back(j);
}
}
for(auto& a : A) {
std::cout << a << std::endl;
}
}
int
main() {
printBitCombinations(4);
return 0;
}
Here is an O(1) per number algorithm that outputs these numbers in requested order.
If we can assume that k is <= 64, or we can use python long arithmetic, then we can use "gosper hack". This obviously works in O(1) per number, so the whole algorithm works in O(t) where t is number of items we want to print (e.g. 2^k to print everything)
The idea is in comments
def gosper(n):
"""return smallest number > n with the same number of bits set"""
# group is first sequence of 1's in n starting from lowest bits
# 000111110000
# ^---^ - this is "group"
# the idea is simple - take the highest bit in group
# and move it one position left
# the rest of the group will go to the right
# like this:
# 000111110000
# turns into
# 001000001111
# after another iteration this turns into
# 001000010111
# and so forth...
# lowest_set_bit is the lowest 1 in that group
# 000111110000
# ^ here it is
lowest_set_bit = ((~n) + 1) & n
# this points straight before the highest bit
# 0001110000
# ^ here - to the 0
new_group_head = (lowest_set_bit + n) & (~n)
# now let's work with what was left on the left
original_group = n & (new_group_head - 1)
# remove group old head - it has migrated one bit left
new_group = original_group ^ (new_group_head / 2)
# move the tail to the beginning
new_group /= lowest_set_bit
# reassemble result
result = n & ~original_group
result |= new_group_head
result |= new_group
assert result > n
assert bin(result).count('1') == bin(n).count('1')
return result
def all_combinations(k):
yield '0' * k
mask = (1 << k) - 1
for num_bits in xrange(1, k + 1):
n = (1 << num_bits) - 1
while True:
yield bin(n)[2:].rjust(k, '0')
n = gosper(n)
if n > mask:
break
k = 5
result = list(all_combinations(k))
print len(result)
assert len(result) == 2 ** k
assert result[-1] == '1' * k
for s in all_combinations(5):
print s
Example output: ideone.com/FO329N
def getBits(n):
lim = pow(2,n)
opt = {}
for i in range(0,lim):
temp = bin(i)
#print temp[temp.index('b')+ 1:]
temp_int = int(temp[temp.index('b') + 1:])
#print y
y = temp_int
sum = 0
while y > 0:
sum += y % 10
y = y / 10
#print temp_int, sum
val = []
if sum in opt.keys():
val = opt[sum]
val.append(temp_int)
opt[sum] = val
for key in opt.keys():
print key,
for item in opt[key]:
print item,
print
getBits(5)
public static void driver(int k) {
for(int i = 0; i<=k;i++) {
print1s(k,i,new StringBuilder());
}
}
public static void print1s(int k, int ones, StringBuilder prefix) {
if(ones == 0) {
for(int i = 0; i<k; i++)prefix.append('0');
System.out.println(prefix);
prefix.delete(prefix.length()-k,prefix.length());
return;
}
for(int i = k-ones; i>=0; i--) {
for(int j = 0;j<i;j++)prefix.append('0');
prefix.append('1');
print1s(k-(i+1),ones-1,prefix);
prefix.delete(prefix.length()-1-i,prefix.length());
}
}
package com.career.cup;
import java.util.Arrays;
public class BinaryCodeGenerator {
public static String binary(int data)
{
int r;
StringBuffer s=new StringBuffer();
while(data!=0)
{
r=data%2;
data=data/2;
s=s.append(r);
}
return s.reverse().toString();
}
public static void main(String[] args) {
int n=4;
int l=(int)Math.pow(2, n);
String[] container=new String[l];
String ss=binary(l-1);
int size=ss.length();
String k="";
for(int i=0;i<l;i++)
{
container[i]=BinaryCodeGenerator.binary(i);
if(container[i].length()<size)
{
for(int j=container[i].length();j<size;j++)
{
k=k+0;
}
k=k+container[i];
container[i]=k;
}
k="";
}
System.out.println(Arrays.toString(container));
}
}
package com.career.cup;
import java.util.Arrays;
public class BinaryCodeGenerator {
public static String binary(int data)
{
int r;
StringBuffer s=new StringBuffer();
while(data!=0)
{
r=data%2;
data=data/2;
s=s.append(r);
}
return s.reverse().toString();
}
public static void main(String[] args) {
int n=4;
int l=(int)Math.pow(2, n);
String[] container=new String[l];
String ss=binary(l-1);
int size=ss.length();
String k="";
for(int i=0;i<l;i++)
{
container[i]=BinaryCodeGenerator.binary(i);
if(container[i].length()<size)
{
for(int j=container[i].length();j<size;j++)
{
k=k+0;
}
k=k+container[i];
container[i]=k;
}
k="";
}
System.out.println(Arrays.toString(container));
}
}
A simple solution in C++
#include <iostream>
#include <vector>
int bitcount(int aArg) {
int c = 0; // bit count
for(; aArg; c++)
aArg &= aArg -1; // clears the least significat bit
return c;
}
void printBitCombinations(int K) {
std::vector<int> A;
for(int i = 0; i <= K; ++i) {
for(int j = 0; j < 1 << K; ++j) {
if(bitcount(j) == i)
A.push_back(j);
}
}
for(auto& a : A) {
std::cout << a << std::endl;
}
}
int
main() {
printBitCombinations(4);
return 0;
}
public class CombinationNumberKBits {
public static void main(String[] args) {
printCombinationsKBits(3);
}
public static void printCombinationsKBits(int k) {
if (k <= 0) return;
int pow = new Double(Math.pow(2, k)).intValue();
int i = 0, j = 0;
int num = 0;
List<int[]> r = new ArrayList<>();
int[] arr = null;
while (i < pow) {
num = i;
j = k-1;
arr = new int[k];
while(num > 0 && j >= 0) {
if ((num & 1) > 0) {
arr[j] = 1;
}
j--;
num = num >> 1;
}
i++;
r.add(arr);
}
for (int l = 0; l <= k && !r.isEmpty(); l++) {
List<int[]> subset = findArraysWithKBits(r, l);
printArrays(subset);
r.removeAll(subset);
}
}
private static List<int[]> findArraysWithKBits(List<int[]> arr, int k) {
List<int[]> r = new ArrayList<>();
for (int[] is : arr) {
if (countBits(is) == k) {
r.add(is);
}
}
return r;
}
public static int countBits(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
count++;
}
}
return count;
}
public static void printArrays(List<int[]> arr) {
for (int[] is : arr) {
System.out.println();
for (int i = 0; i < is.length; i++) {
System.out.print(is[i] + " ");
}
}
}
}
// ouput:
/*
0 0 0
0 0 1
0 1 0
1 0 0
0 1 1
1 0 1
1 1 0
1 1 1
*/
A solution in C:
static unsigned
bits_set (unsigned v)
{
unsigned c;
for (c=0; v; c++)
v &= (v-1);
return c;
}
int
main (int argc, char **argv)
{
unsigned k = atoi(argv[1]);
unsigned sz = power(2, k);
signed *heads = (signed*)malloc(sizeof(signed) * (k+1));
signed *tails = (signed*)malloc(sizeof(signed) * (k+1));
signed *nexts = (signed*)malloc(sizeof(signed) * sz);
signed i, nbits;
for(nbits=0; nbits<=k; nbits++)
heads[nbits] = tails[nbits] = -1;
for(i=1; i<sz; i++) {
nbits = bits_set(i);
if (tails[ nbits ] == -1) {
heads[ nbits ] = i;
tails[ nbits ] = i;
nexts[ i ] = -1;
continue;
}
nexts[ tails[nbits] ] = i;
nexts[ i ] = -1;
tails[ nbits ] = i;
}
for(nbits=1; nbits<=k; nbits++) {
printf("%d bits: ", nbits);
for(i=heads[nbits]; i>0; i=nexts[i])
printf("%d ", i);
printf("\n");
}
return 0;
}
Just a thought correct me if I am wrong.
Will take an example and try to explain, If input is 4
0 bits set elements : 0
only 1 bit set elements : 1 , 2 , 4 , 8 ( powers of 2 < pow(2,4))
only 2 bit set elements : 3, 5, 6 , 9, 10 , 12 (sum of 2 1 bit set numbers in the above list )
only 3 bit set elements : 7 , 11, 13, 14 ( sum of above list and power of 2 elements)
All bits set ( 4 in this case) elements : 15 ( pow(2,4) -1 )
not a program but just an approach dont really have a working code ready , will try and post it when it is done.
I suppose the worst case would be O(m^2) where m would be maximum elements in a m bits set element array.
package test;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;
public class GoogleBinary {
@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int totalOfBites = in.nextInt();
LinkedHashSet<String> arrayofBits = new LinkedHashSet<String>();
solution (arrayofBits, totalOfBites );
//System.out.println("arrayofBites.size "+arrayofBites.size());
Iterator<String> spacesofBits = arrayofBits.iterator();
while ( spacesofBits.hasNext()){
String listIntegers= spacesofBits.next();
System.out.println(listIntegers);
}
}
private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){
int numberofBitInternal = 0, lengthofNumberOfBits=0,
counterIndexBite=totalOfBits;
String binaryNumberofDecimal = new String();
int totalofLines = (int) Math.pow(2, totalOfBits);
while (numberofBitInternal <= (totalofLines-1) ){
lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
counterIndexBite = lengthofNumberOfBits;
binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
//System.out.println("numberofBiteInternal "+numberofBiteInternal);
if (lengthofNumberOfBits == totalOfBits ){
arrayofBits.add(binaryNumberofDecimal);
}else{
StringBuilder arrayWithBits = new StringBuilder();
while (counterIndexBite < totalOfBits ){
arrayWithBits.append(0);
counterIndexBite++;
}
arrayWithBits.append(binaryNumberofDecimal);
arrayofBits.add(arrayWithBits.toString());
}
numberofBitInternal++;
}
}
}
package test;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;
public class GoogleBinary {
@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int totalOfBites = in.nextInt();
LinkedHashSet<String> arrayofBits = new LinkedHashSet<String>();
solution (arrayofBits, totalOfBites );
//System.out.println("arrayofBites.size "+arrayofBites.size());
Iterator<String> spacesofBits = arrayofBits.iterator();
while ( spacesofBits.hasNext()){
String listIntegers= spacesofBits.next();
System.out.println(listIntegers);
}
}
private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){
int numberofBitInternal = 0, lengthofNumberOfBits=0,
counterIndexBite=totalOfBits;
String binaryNumberofDecimal = new String();
int totalofLines = (int) Math.pow(2, totalOfBits);
while (numberofBitInternal <= (totalofLines-1) ){
lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
counterIndexBite = lengthofNumberOfBits;
binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
//System.out.println("numberofBiteInternal "+numberofBiteInternal);
if (lengthofNumberOfBits == totalOfBits ){
arrayofBits.add(binaryNumberofDecimal);
}else{
StringBuilder arrayWithBits = new StringBuilder();
while (counterIndexBite < totalOfBits ){
arrayWithBits.append(0);
counterIndexBite++;
}
arrayWithBits.append(binaryNumberofDecimal);
arrayofBits.add(arrayWithBits.toString());
}
numberofBitInternal++;
}
}
}
class MyArrayItem {
public int data;
public int next;
public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}
MyArrayItem[] Arr;
public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);
Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);
ArrayList<Integer> headlist = new ArrayList<Integer>();
System.out.println("input "+ k + " has " + numOfCombinations + " combinations to show");
int combinationsToShow = numOfCombinations;
// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;
headlist.add(0,0);
System.out.println(" 0 bits set list ");
int startIdxToShow = headlist.get(0);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);
// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;
headlist.add(1,1);
int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}
System.out.println(" 1 bits set list ");
startIdxToShow = headlist.get(1);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list
for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}
int head = sumIncreasing(a,b,numOfCombinations);
headlist.add(n,head);
System.out.println(n +" bits set list ");
startIdxToShow = headlist.get(n);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
n++;
}
// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;
headlist.add(k,numOfCombinations - 1);
System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );
}
int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;
if (a == b)
return numOfCombinations;
if (Arr[t].data != -1)
return numOfCombinations;
int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);
Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}
return t;
}
I am only printing the decimal numbers herewith increasing number of bits.
To print in binary format you would need a function to convert from decimal to binary string of fixed size
I am not sure of the exact complexity, think it is O(k^2).
Could someone confirm / correct me here. Also any suggestions would be great
class MyArrayItem {
public int data;
public int next;
public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}
MyArrayItem[] Arr;
public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);
Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);
ArrayList<Integer> headlist = new ArrayList<Integer>();
System.out.println("input "+ k + " has " + numOfCombinations + " combinations to show");
int combinationsToShow = numOfCombinations;
// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;
headlist.add(0,0);
System.out.println(" 0 bits set list ");
int startIdxToShow = headlist.get(0);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);
// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;
headlist.add(1,1);
int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}
System.out.println(" 1 bits set list ");
startIdxToShow = headlist.get(1);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list
for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}
int head = sumIncreasing(a,b,numOfCombinations);
headlist.add(n,head);
System.out.println(n +" bits set list ");
startIdxToShow = headlist.get(n);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
n++;
}
// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;
headlist.add(k,numOfCombinations - 1);
System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );
}
int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;
if (a == b)
return numOfCombinations;
if (Arr[t].data != -1)
return numOfCombinations;
int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);
Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}
return t;
}
I am only printing the decimal numbers here.
To print in binary format you would need a function to convert from decimal to binary string of fixed size
Also not sure of complexity, think it is O(k^2) . Please confirm / correct me here.
class MyArrayItem {
public int data;
public int next;
public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}
MyArrayItem[] Arr;
public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);
Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);
ArrayList<Integer> headlist = new ArrayList<Integer>();
System.out.println("input "+ k + " has " + numOfCombinations + " combinations to show");
int combinationsToShow = numOfCombinations;
// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;
headlist.add(0,0);
System.out.println(" 0 bits set list ");
int startIdxToShow = headlist.get(0);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);
// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;
headlist.add(1,1);
int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}
System.out.println(" 1 bits set list ");
startIdxToShow = headlist.get(1);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list
for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}
int head = sumIncreasing(a,b,numOfCombinations);
headlist.add(n,head);
System.out.println(n +" bits set list ");
startIdxToShow = headlist.get(n);
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);
n++;
}
// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;
headlist.add(k,numOfCombinations - 1);
System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );
}
int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;
if (a == b)
return numOfCombinations;
if (Arr[t].data != -1)
return numOfCombinations;
int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);
Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}
return t;
}
I am only printing the decimal numbers here.
To print in binary format you would need a function to convert from decimal to binary string of fixed size
Also not sure of complexity, think it is O(k^2) . Please confirm / correct me here.
A simple recursive solution:
void print_nums(int n) {
for(q = 0; q < n; q++)
print_intern(0, 0, 0, q, n);
}
void print_intern(int x, int next_pos, int bits, int cur_len, int total_len) {
if (bits >= cur_len) {
printf("%d\n", x);
return;
}
for(j = next_pos; j < total_len; j++) {
y = set_bit(x, j);
print_intern(y, j + 1, bits + 1, cur_len, total_len);
}
}
In Python >= 2.6 itertools has a handy combinations method that'll emit r-length subsequences in lexicographic sort order. Using itertools.chain by increasing the number of bits sets creates a space-constant generator.
Arrays are indexed 0 from the left, bits indexed 0 from the right, so we call reversed().
from itertools import chain
from itertools import combinations
def BitsSet(k):
return chain.from_iterable(combinations(range(k), count) for count in range(k+1))
def PrintBits(k):
for bits in BitsSet(k):
print(''.join(reversed('1' if idx in bits else '0' for idx in range(k)))
You are correct with the thought. For getting the number of elements with only ! bit set is similar to knowing the number of ways we can pick one box out of k boxes. This gives us the following formula: (n be the num of set bits)
k! / (n! * (k-n)!)
Thus, if k=4, n=0 => 1 element
if k=4, n=1 => 4!/3!*1! = 4 elements
if k=4, n=2 => 4!/2!*2! = 6 elements
if k=4, n=3 => 4!1!*3! = 4 elements
if k=4, n=4 => 4!/4!*0! = 1 element
That way I think we can get the total number of elements for every set bit reserve space accordingly.
#include "stdafx.h"
#include <vector>
void shiftBits(unsigned long number, int shiftStartIndex, int shiftEndIndex) {
if(shiftStartIndex < 0){
return;
}
if (( (1 << shiftStartIndex) && number )== 0){
return;
}
for(int i = shiftStartIndex; i < shiftEndIndex - 1; ++i) {
unsigned long mask = ~(1 << i);
number = number & mask;
number = number | ( 1 << (i + 1) );
printf("%d ", number);
shiftBits(number, shiftStartIndex - 1, i + 1);
}
}
void insertBits(int bitCount){
unsigned long number = 0;
printf("%d ", number);
for(int i = 0; i< bitCount;++i) {
number = number | (1 << i);
printf("%d ", number);
shiftBits(number, i, bitCount);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int bits;
scanf_s("%d", &bits);
insertBits(bits);
getchar();
getchar();
return 0;
}
import java.util.*;
public class EnumKBitSet {
char[] ch=null;
public void enumKBitSet(int K)
{
ch = new char[K];
for (int i=0; i < ch.length; i++) ch[i]='0';
for (int k =0; k <= ch.length ; k++)
enumKBit(k, ch, ch.length);
}
private void enumKBit(int k, char[] ch, int pos)
{
int n = ch.length-1;
if (k==0)
{
System.out.print(new String(ch)+" ");
return;
}
for (int p=n-(k-1); p > n-pos; p--)
{
ch[p]='1';
enumKBit(k-1, ch, n-p);
ch[p]='0';
}
}
public static void main(String argv[])
{
EnumKBitSet ekbs = new EnumKBitSet();
ekbs.enumKBitSet(4);
}
}
// k = 3
// 000, 001, 010, 100, 011, 101, 110,
// k = 4
// 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111
public class BitSet {
public static void main(String[] args) {
BitSet b = new BitSet();
b.generateBit(3);
}
public void generateBit(int k) {
for (int i = 0; i <= k; i++) {
generateBitSet(k, i, "");
}
}
public void generateBitSet(int size, int d, String suffix) {
if (d < 0) {
return;
}
if (size <= 0) {
System.out.println(suffix);
} else if (size == d) {
generateBitSet(size - 1, d - 1, "1" + suffix);
} else {
generateBitSet(size - 1, d - 1, "1" + suffix);
generateBitSet(size - 1, d, "0" + suffix);
}
}
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
while(!stack.isEmpty()) {
Stack newStack = new Stack<>();
while(!stack.isEmpty()) {
int c = stack.pop();
for(int i = 0; i < n; i++) {
int toAdd = (c | (1 << i));
if(toAdd != c) {
newStack.push(toAdd);
System.out.println(Integer.toBinaryString(toAdd));
} else {
break;
}
}
}
stack = newStack;
}
public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
Code in Java. Complexity of the solution is k * 2 ^ k.
public static void main(String[] args) {
int k = 4;
for (int i = 0; i <= k; i++)
Func(k, 0, "", i);
}
public static void Func(int k, int ones, String prefix, int max_ones)
{
if (prefix.length() == k)
{
if (ones == max_ones)
System.out.println(prefix);
}
else {
Func(k, ones, prefix + "0", max_ones);
if (ones < max_ones)
{
Func(k, ones + 1, prefix + "1", max_ones);
}
}
}
public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
Basically this is the same as printing out all of the binary representation of numbers from 0 to 2^k.
public void printK(int k) {
int N = (int) Math.pow(2,k);
for(int i = 0; i < N; ++i) {
String s = "";
for(int j = 0; j < k; ++j) {
s = String.valueOf(i >> j & 0x1) + s;
}
System.out.println(s);
}
}
import java.util.*;
public class BitSetSorter {
public static void getAllBitSets(int k) {
Set<Integer> currBitSet = new HashSet<>();
currBitSet.add(0);
printBitSet(currBitSet, k);
currBitSet.remove(0);
int num = 1;
for (int i = 0; i < k; i++) {
currBitSet.add(num);
num <<= 1;
}
for (int i = 2; i <= k; i++) {
printBitSet(currBitSet, k);
Set<Integer> nextBitSet = new HashSet<>();
for (int n : currBitSet) {
for (int m : currBitSet) {
if (n != m) {
nextBitSet.add(n | m);
}
}
}
currBitSet = nextBitSet;
}
}
public static void printBitSet(Set<Integer> bitset, int len) {
for (int n : bitset) {
System.out.println(String.format("%" + len + "s",
Integer.toBinaryString(n))
.replace(' ', '0'));
}
}
public static void main(String[] args) {
getAllBitSets(4);
}
}
def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1
def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)
In Python:
def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1
def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)
void printBin(int i) {
if(i <= 0) {
cout << 0 << endl;
}
while(i) {
cout << (i & 1);
i >>= 1;
}
cout << endl;
}
void print(int i) {
if(i == 0) {
cout << i << endl;
return;
}
print(i - 1);
printBin(i);
}
int main() {
int K = 3;
int res = (1 << K) - 1; // for K = 3, res == 1000 - 1 == 111;
print(res);
return 0;
}
First, I think that your sample output is inconsistent to your description of the problem. If two numbers with the same set bits are supposed to be sorted from low to high value, then it should be:
000, 001, 010, 100, 011, 101, 110, 111 (note that 011 should come before 101).
With that said, I took two approaches. The first, naive approach used the Cartesian product of '01' repeated k times. The resulting list is in ascending order. I then sorted it the list by the number of 1 bits in each number.
def bins_product(k): import itertools bits = [''.join(b) for b in itertools.product('01', repeat=k)] bits.sort(key = lambda x: x.count('1')) for x in bits: print xBut that's slow. I'm not even sure what the time complexity is of that code. So, my second sweep was to actually just count in binary up to the 2^k, and then perform the same sort:
- Nate May 27, 2016def bins_count(k): bits = [] b = 0 while b < 2**k: bits.append(bin(b)[2:].zfill(k)) b += 1 bits.sort(key = lambda x: x.count('1')) for x in bits: print x