java - 存储二进制字符串的所有可能序列，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”时，111、011、001 都正确存储了组合。

代码:

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

有一个位技巧可以枚举给定位掩码的所有子掩码

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(二进制101)，此伪代码给出输出5,4,1,0(二进制101, 100, 001, 000)