递归查找字符串（powerset）的所有子集的Java算法

Question

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

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”，这将导致重复。有没有办法解决这个问题

对于powerset，我的意思是如果字符串是abc，它将返回“，”a“，”b“，”c“，”ab“，”ac“，”bc“，”abc“

Answer 1

要消除重复，只需将它们全部添加到Set中，这可以通过某种帮助器轻松完成：

static ArrayList<String> powerSet(String s) {
    return new ArrayList<>(_powerSet(s));
}

static HashSet<String> _powerSet(String s) {
    HashSet<String> set = new HashSet<>();
    set.add(s);

    for(int i = 0; i < s.length(); i++) {
        String tmp = s.substring(0, i) + s.substring(i+1, s.length());
        set.addAll(_powerSet(tmp));
    }

    return set;
}

顺便说一句，您的代码本质上处理了边缘情况。你不必为此担心

Answer 2

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    public class MainClass {

        static List<List<char[]>> list = new ArrayList<List<char[]>>();

        // static List<int[]> list1 = new ArrayList<int[]>();
        public static void main(String[] args) {
            List<char[]> list1 = new ArrayList<char[]>();
            String string = "abcd";
            char[] a = string.toCharArray();
            generate(a, 0, 0, list1);

            for (List<char[]> l : list) {
                for (char[] b : l) {
                    for (char c : b) {
                        System.out.print(c + ",");
                    }
                    System.out.println();
                }
            }

        }

        public static void generate(char[] array, int offset, int index, List<char[]> list1) {
            if (offset >= array.length)
                return;
            char[] newArray = Arrays.copyOfRange(array, offset, index);
            list1.add(newArray);
            if (index >= array.length) {
                list.add(list1);
                offset++;
                index = offset;
                generate(array, offset, index, new ArrayList<char[]>());
            } else {
                index++;
                generate(array, offset, index, list1);
            }
        }
    }

Answer 3

我发现在设计递归算法时，首先考虑简单的角点情况是很有帮助的，即空字符串和带一个字符的字符串。然后，通常分割问题并对字符串的其余部分/尾部进行递归调用。有点像这样：

    static List<String> nuPowerSet(String s) {

    if (s.length() == 0) { // trivial, subset of empty string is empty
        return emptyList();
    }

    String head = s.substring(0, 1);
    if (s.length() ==1) // the subset of a one character string is exactly that character
        return asList(head);

    String tail = s.substring(1);

    ArrayList<String> ps = new ArrayList<String>();

    ps.add(head); // one of the subsets is the current first character


    List<String> tailSubsets = nuPowerSet(tail); // all the subsets of the remainder.

    List<String> tailSubsetsWithCurrentHeadPrepended = tailSubsets
            .stream()
            .map(element -> head + element) 
            .collect(Collectors.toList());

    ps.addAll(tailSubsets);
    ps.addAll(tailSubsetsWithCurrentHeadPrepended);

    return ps;
}

Answer 4

没错，您确实有重复项，因为您要多次创建temp（每次都没有其他字符），所以当您递归调用时，将有不同的子集共享相同的字符并创建dup。例如，“abc”将创建一个带有：[“ab”、“ac”、“bc”]的temp，它们中的每一个都将只使用一个字符进行递归调用，因此您将获得“a”、“b”和“c”中的每一个两次

避免这种情况的一种方法是使用集合而不是列表，这将省略所有DUP：

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

    for (int i = 0; i < s.length(); i++) {
        String temp = s.replace(Character.toString(s.charAt(i)), "");
        Set<String> ps2 = powerSet(temp);
        for (String x : ps2) {
            ps.add(x);
        }
    }
    return ps;
}

现在输出为：

bc
a
ab
b
ac
abc
c

另一种解决方案：

public static List<String> powerset(String s) {
    List<String> ans = new LinkedList<>();
    if (null == s) {
        return ans;
    }
    return powerset(s, ans);
}

private static List<String> powerset(String s, List<String> ans) {
    if ("".equals(s)) {
        return ans;
    }
    String first = s.substring(0, 1);
    String rest = s.substring(1);
    ans.add(first);
    List<String> pAns = new LinkedList<>(ans);
    for (String partial : ans.subList(0, ans.size()-1)) {
        pAns.add(partial + first);
    }
    return powerset(rest, pAns);
}

输出

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

Answer 5

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

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

   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

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

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]

Answer 6

有一种不使用递归的方法可以做到这一点，它依赖于位字符串和子集之间的简单对应关系

因此，假设您有一个三个字符的字符串“abc”，那么，正如您所指出的，子集将是“，”c“，”b“，”bc“，”a“，”ac“，”ab“，”abc”

如果创建一个字符表，并为子集中的每个字符写入1，为不在子集中的每个字符写入0，则可以看到一个模式：

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

对于每个长度为n的唯一字符字符串，您将有2个ⁿ子集，您可以通过简单地从i=0到i=2ⁿ-1创建一个for循环来生成所有子集，并且只包含与i中的位1对应的字符

我编写了一个Java示例here和一个C示例here