Java - 递归地查找String（powerset）的所有子集 [英] Java - Finding all subsets of a String (powerset) recursively

问题描述

所以，我需要递归地找到给定字符串的所有子集。到目前为止我所拥有的是：

So, I need to find all subsets of a given string recursively. What I have so far is:

static ArrayList<String> powerSet(String s){
        ArrayList<String> ps = new ArrayList<String>();
        ps.add(s);


        for(int i=0; i<s.length(); i++){
            String temp = s.replace(Character.toString(s.charAt(i)), "");
            ArrayList<String> ps2 = powerSet(temp);
            for(int j = 0; j < ps2.size(); j++){
                ps.add(ps2.get(j));
            }
        }   

        return ps;

我想我知道现在的问题，但我不知道如何修复它。目前，我找到所有temp的幂集，分别是bcd，acd，abd，abc，这将导致重复。有想法该怎么解决这个吗？

I think I know what the problem is now, but I dont know how to fix it. Currently, I find all the power sets of temp, which are "bcd", "acd", "abd", "abc", which will cause duplicates. Any ideas on how to fix this?

通过powerset，我的意思是如果字符串是abc，它将返回，a，b，c，ab，ac ，bc，abc。

By powerset, I mean if the string is abc, it will return "", "a", "b", "c", "ab", "ac", "bc", "abc".

推荐答案

具有n个元素的集合的子集数量为2 ^ñ。例如，如果我们有字符串abc，我们将有2个 ⁿ = 2 ³ = 8个子集。

The number of subsets of a set with n elements is 2ⁿ. If we have, for example, the string "abc", we will have 2ⁿ = 2³ = 8 subsets.

可以用n位表示的状态数也是2 ⁿ 。我们可以证明枚举n位的所有可能状态与具有n个元素的集合的所有可能子集之间存在对应关系：

The number of states that can be represented by n bits is also 2ⁿ. We can show there is a correspondence between enumerating all possible states for n bits and all possible subsets for a set with n elements:

   2 1 0   2 1 0
   c b a    bits
0          0 0 0
1      a   0 0 1
2    b     0 1 0
3    b a   0 1 1
4  c       1 0 0
5  c   a   1 0 1
6  c b     1 1 0 
7  c b a   1 1 1

例如，如果我们考虑第5行，则第2位和第0位有效。如果我们 abc.charAt（0）+ abc.charAt（2），我们得到子集 ac 。

If we consider line 5, for example, bits 2 and 0 are active. If we do abc.charAt(0) + abc.charAt(2) we get the subset ac.

为了枚举n位的所有可能状态，我们从0开始，加1，直到我们达到2 ⁿ - 1.在这个解决方案中，我们将开始在2 ⁿ - 1并且递减到0，所以我们不需要另一个参数来保持子集的数量，但效果是相同的：

To enumerate all possible states for n bits we start at 0, and sum one until we reach 2ⁿ - 1. In this solution we will start at 2ⁿ - 1 and decrement until 0, so we don't need another parameter just to keep the number of subsets, but the effect is the same:

static List<String> powerSet(String s) {
    // the number of subsets is 2^n
    long numSubsets = 1L << s.length();
    return powerSet(s, numSubsets - 1);
}

static List<String> powerSet(String s, long active) {
    if (active < 0) {
        // Recursion base case
        // All 2^n subsets were visited, stop here and return a new list
        return new ArrayList<>();
    }

    StringBuilder subset = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        // For each bit
        if (isSet(active, i)) {
            // If the bit is set, add the correspondent char to this subset
            subset.append(s.charAt(i));
        }
    }
    // Make the recursive call, decrementing active to the next state,
    // and get the returning list
    List<String> subsets = powerSet(s, active - 1);
    // Add this subset to the list of subsets
    subsets.add(subset.toString());
    return subsets;
}

static boolean isSet(long bits, int i) {
    // return true if the ith bit is set
    return (bits & (1L << i)) != 0;
}

然后你只需要调用它：

System.out.println(powerSet("abc"));

并获得所有8个子集：

[, a, b, ab, c, ac, bc, abc]

这篇关于Java - 递归地查找String（powerset）的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！