Friday, April 3, 2015

Generate all sequences of n bits with all k unique bits

The problem came from Cracking the code interview:
Consider sequences of 36 bits. Each such sequence has 32 5 - bit sequences consisting of adjacent bits. For example, the sequence 1101011… contains the 5 - bit sequences 11010,10101,01011,…. Write a program that prints all 36 - bit sequences with the two properties: 
1. The first 5 bits of the sequence are 00000. 
2. No two 5 - bit subsequences are the same.

I generalized it to print all sequence of n  (n <= 64) bits with: 1. the first k bits of the sequence are 0s and 2. no two k - bit subsequences are the same.

There probably are smarter ways. I used the brutal force search. Start from kth bit, get all permutations of the sequence with the first k bits zero, then for every sequence, check if all bits are unique, and print out those that contain unique k - bit sequence and haven't been printed.

I am looking for a better approach, here is my open question of the problem on Stackoverflow.


import java.util.*;
public class UniquekBitSequence {

 public static void uniqueSequence(int n, int k){
  long rst = 0;
  uniqueSequence(n, k, rst, k - 1, new HashSet ());
 }
 private static void uniqueSequence(int n, int k, long rst, int start, Set printed){
  if(isDistinct(rst, n, k) && printed.add(rst)){
   System.out.println(Long.toBinaryString(rst));
  }
  for(int i = start + 1; i < n; i++){
   rst |= (1 << i);
   uniqueSequence(n, k, rst, i, printed);
   rst = setZero(rst, i);
   uniqueSequence(n, k, rst,  i, printed);
  }
 }
 public static int getInt(long rst, int right, int left){
  int mask = (1 << (left + 1)) - 1 - ((1 << (right)) - 1);
  return ((int)rst & mask) >> right;
 }
 public static long setZero(long rst, int start){
  int mask = ~(1 << start);
  return rst & mask;
 }
 private static boolean isDistinct(long rst, int n, int k){
  Set bits = new HashSet ();
  for(int i = k - 1; i < n; i++){
   if(!bits.add(getInt(rst, i - k + 1, i)))
    return false;
  }
  return true;
 }
 public static void main(String[] args){
  uniqueSequence(10, 5);
 }
}

No comments:

Post a Comment