存储二进制字符串的所有可能序列，Java

Question

目的：给定一个二进制字符串作为输入，存储将字符串中的全部1都切换为1和0的所有可能组合所产生的字符串。

示例给定二进制串“110”，每个“1”值可以切换为“1”或“0”。 “0”值必须保留“0”并且顺序很重要。

字符串011产生： [011，010，001，000]

字符串101产生： [101，100，001，000]

字符串111产生： [111，110， 101，100，011，010，001 000]

问题我面临：当给定字符串“111”时，我的代码不存储每个对应子序列的所有可能组合。

输出的我的代码

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] 

在那里它们被不存储所有可能的组合入散列几个例子：010（不包含000），101（不包含000或001） 。

111,011,001全都正确地存储组合，当功能最初被赋予“111”作为输入时。

代码：

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; 
    } 
} 

Answer 1

还有就是有点伎俩，允许枚举给定的位的所有submasks掩盖

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 

对于面膜5 (binary 101)这个伪给人输出5,4,1,0 (binary 101, 100, 001, 000)

Answer 2

你实施是正确的。你可能执行错了。你应该position=0执行你的subsequence方法：

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

的输出上面的应该是：

[010, 000] 

Answer 3

我试过，只是输出所有结果从0到给定的二进制字符串。跟踪0的位置。这显然不是有效的。但是如果你愿意，你可以优化它。

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); 

    } 

Answer 4

迄今为止的解决方案似乎相当史诗般的。这是另一种选择。

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); 
    } 
}