Java - 以遞歸方式查找String（powerset）的所有子集

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; 

我想我知道現在的問題是什麼，但我不知道如何解決它。目前，我發現所有的電源設置爲「bcd」，「acd」，「abd」，「abc」，這會導致重複。有想法該怎麼解決這個嗎？它將返回「」，「a」，「b」，「c」，「ab」，「ac」，「bc」，「abc」。

Answer 1

我覺得在設計遞歸算法時首先想到簡單的角落案例很有幫助，例如空字符串和帶有一個字符的字符串。然後你通常會分解問題，並對字符串的其餘部分/尾部進行遞歸調用。有點像這樣：

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 2

有一個辦法做到這一點不使用遞歸，它依賴於位串和子集之間的簡單對應關係。因此，假設您有三個字符的字符串「abc」，那麼，如您所述，這些子集將是「」，「c」，「b」，「bc」，「a」，「ac」， 「AB」，「ABC」

如果使字符的表和每一個在子集，0不在該子集中字符寫入一個1，你可以看到一個規律：

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製作一個for循環來生成它們全部n ⁿ -1，並且僅包括對應於位在i是1.

我寫一個Java示例here和C例如here這些字符。

Answer 3

，以消除重複的，你只需要所有的人都加入到一個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 4

具有n個元素的集合的子集數爲2 ⁿ。例如，如果我們有字符串「abc」，那麼我們將有2個子集，其中有2個是子組。

可以用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。

要列舉爲我們從0開始的n比特的所有可能的狀態，和一個求和直到我們達到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 5

你是對的，你確實有重複，因爲你創造temp多次（沒有其他角色每一次），所以，當你調用遞歸會有不同的子集，將共享相同的字符，創建dup。例如，「abc」會創建一個temp：[「ab」，「ac」，「bc」]，它們中的每一個將遞歸調用只有一個字符，所以你會得到每個「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); 
} 

OUTPUT

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

Answer 6

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

的