形成 2^n 组合字符串

Question

从给定的字符串，考虑公式2^n（2次方n），形成不同的组合集。

例如考虑下面的示例字符串 (AA%0%0%)。其中“%”是可选值，因此“%”可以添加到字符串组合中，也可以从字符串组合中删除，因此不同字符串组合的可能性如下。

示例字符串： AA%0%0% {% 索引位置为 [2,4,6]}

示例字符串的不同可能组合：(2^n，其中 n=3（因为“%”计数为 3 ) 等于 2^3 = 8 组合)

为了便于理解，我将以下组合中的“%”替换为“*”。

1. AA*0*0* [no % omitted]
2. AA*0*0  [index 6 % omitted]   
3. AA*00*  [index 4 % omitted]
4. AA0*0*  [index 2 % omitted]
5. AA*00   [index 4,6 % omitted]
6. AA0*0   [index 2,6 % omitted]
7. AA00*   [index 2,4 % omitted]
8. AA00    [index 2,4,6 % omitted]

现在的问题是，“%”字符串的数量会根据用户输入而变化，因此，每次形成这种组合，我想在java中编写一个程序，这将根据 2^n 公式 自动针对此组合。是否有任何现有的算法可以这样做？请建议。

已编辑：

为了更好地理解，我给出了不同的索引，可以由 3 个计数 (2^3 = 8) 组成。这取决于索引位置，例如，% 索引为 2,4,6 表示

[2]
[4]
[6]
[2,4]
[2,6]
[4,6]
[2,4,6]
[没有索引 (%) 删除了所有可用的字符]

Answer 1

你可以写一个递归实现。这个想法是在提供的字符串中检查索引 i 处的 character（您可以将其作为参数传递给函数）是否为 %，如果是，则采取两项行动：

通过 not 省略索引 i 处的字符进行递归调用（无论如何，在这两种情况下，您都需要进行此调用，即 i 是否为 %)
通过省略索引 i 处的字符（即 %，我们已经检查过）进行递归调用

当 i 到达字符串的末尾时，您就得到了一个组合。（因为你已经做了这么多递归调用，所以你会找到所有的组合）

下面我将利用上面的思路来实现：

public static void allCombinations(String s, int i){
    if (i < s.length()){
        // Make a recursive call without removing the character
        allCombinations(s, i + 1);

        if (s.charAt(i) == '%'){
            // Remove character at index i and make a recursive call with new string
            String temp = s.substring(0, i) + s.substring(i + 1);
            allCombinations(temp, i);
        }

    }
    else{
        // print the combination found.
        System.out.println(s);
    }
}

并通过传递 0 作为起始索引（因为您需要从 0 开始）来调用此递归实现，如下所示：allCombinations("AA%0%0%", 0);

编辑

在这里，您可以找到在 ideone

上使用提供的字符串 (AA%0%0%) 测试的实现

形成 2^n 组合字符串

Form 2^n combination string

java

algorithm

combinations

permutation