Storing all possible sequences of a binary string, Java

2
votes

Purpose: Given a binary string as input, store strings resulting from toggling all 1's in the string to both 1 and 0 in all possible combinations.

Example Given a binary string "110", each "1" value can be switched to be either "1" or "0". "0" value must be left a "0" and order matters.

String 011 produces: [011, 010, 001, 000]

String 101 produces: [101, 100, 001, 000]

String 111 produces: [111, 110, 101, 100, 011, 010, 001, 000]

Problem I'm facing: My code doesn't store all possible combinations for each corresponding sub sequence when given the string "111".

Output of my code

Set:110 [110]
Set:011 [011, 010, 001, 000]
Set:000 [000]
Set:111 [111, 110, 101, 100, 011, 010, 001, 000]
Set:100 [100]
Set:001 [001, 000]
Set:101 [101, 100]
Set:010 [010]

Few examples where they are not storing all possible combinations into the hash: 010 (doesn't contain 000), 101 (doesn't contain 000 or 001).

111, 011, 001 all have correctly stored combinations when the function is originally given "111" as the input.

The code:

public static List<String> subsequence(char [] set, HashMap<String,List<String>> hs, int position){
    List<String> listOfSubsequence = new ArrayList<String>();

    // Dynamic programming part
    if (hs.containsKey(String.valueOf(set))){
        return hs.get(String.valueOf(set));
    }

    // base case
    else if (position >= set.length ){
        listOfSubsequence.add(String.valueOf(set));
        hs.put(String.valueOf(set), listOfSubsequence);
        return listOfSubsequence;
    } 

    else if (set[position] == '0'){
        return(subsequence(set,hs,position + 1));
    }
    else{
        // Last situation where we have a 1 at position we're looking at
        listOfSubsequence.addAll(subsequence(set,hs,position + 1));
        set[position] = '0';
        listOfSubsequence.addAll(subsequence(set,hs,position));
        set[position] = '1';

        hs.put(String.valueOf(set), listOfSubsequence);
        return listOfSubsequence;
    }
}
4
javaalgorithmdynamic-programming
Seems like a homework question, but one idea that comes to mind would be simple string manipulation. Store the indexes of the individual "1"s, then you can simply introduce a recursive/iterative solution for each permutation. - Rogue
That's essentially what I did. I noticed that when I recursed I wasn't storing each sub problem correctly and couldn't figure out why. I came across a similar question while on a programming competition website. - Martin L
It's not right to use the dynamic programming tag. DP is about finding an optimal solution based on discrete decisions that can be decomposed into like subproblems. Here you're enumerating a set of all possible solutions. That's not DP. - Gene

4 Answers

3
votes

There is bit trick that allows to enumerate all submasks of given bit mask

sub = mask;
while (sub) {
    output sub
    sub = (sub - 1) & mask;
    //clears LSB, sets trailing 0s, removes bits not presenting in mask
}
output sub  ////zero one

For mask 5 (binary 101) this pseudocode gives output 5,4,1,0 (binary 101, 100, 001, 000)

1
votes

Your implementation is correct. You're probably executing it wrong. You should execute your subsequence method with position=0:

char[] set = "010".toCharArray();
HashMap<String, List<String>> hs = new HashMap();
int position = 0;
System.out.println(subsequence(set, hs, position));

The output of the above should be:

[010, 000]
0
votes

I tried, just outputting all the results from 0 to the given binary string. Keeping track of the 0's pos. It's obviously not efficent. But you can optimize it if you want.

printPerm("111");

public static void printPerm(String b)
    {
        double n = Integer.parseInt(b, 2);
        ArrayList<Integer> aList = new ArrayList<>();

        //1.) Notice where the zeros are
        for(int i=0;i<b.length() ;i++)
        {
            if(b.charAt(i) == '0')
            {
                aList.add(i);
            }
        }

        //2. Convert the binary to int
        ArrayList<String> collection = new ArrayList<>();
        String bin ;
        for(int i=0;i<n;i++)
        {
             bin = Integer.toBinaryString(i);
             bin = String.format("%" + b.length() + "s",bin).replace(" ", "0") ;
            Boolean isValid =false;
            if(aList.size() ==0 )
            {
                //No zeros found. Easy
                isValid = true;
            }else
            {
                for(Integer zi : aList)
                {
                    if(bin.charAt(zi) == '0')
                    {
                        isValid = true;
                    }
                    else
                    {
                        isValid = false;
                    }
                }
            }
            if(isValid)
            {
                collection.add(bin);
            }

        }

        //3 Print strings.
        for(String s: collection)
        {
            System.out.println(s);
        }
        System.out.println(b);

    }
0
votes

The solutions so far seem rather epic. Here's an alternative.

import java.util.ArrayList;

public class Experimental {

  static final class BitStringEnumerator {
    final char[] bits;
    final ArrayList<String> results = new ArrayList<>();

    BitStringEnumerator(String bits) {
      this.bits = bits.toCharArray();
      enumerate(0);
    }

    /** Enumerate all strings incorporating bits from position pos. */
    private void enumerate(int pos) {
      if (pos >= bits.length) {
        // All positions have been incorporated. The string is complete.
        results.add(new String(bits));
      } else {
        // The string's not complete yet. Enumerate all strings with this bit as-is.
        enumerate(pos + 1);
        if (bits[pos] == '1') {
          // If this bit is a 1, also enumerate all with it flipped to 0.
          bits[pos] = '0';
          enumerate(pos + 1);
          bits[pos] = '1';
        }
      }
    }
  }

  public static void main(String[] args) {
    System.out.println(new BitStringEnumerator("111").results);
  }
}