給定字符串中所有可能不同的字符子集JAVA

Question

如標題所示，我需要執行以下操作。但我不知何故會得到錯誤的答案，或許有些循環是錯誤的？

這是我迄今爲止編碼的內容，但它似乎給了我錯誤的結果。任何想法，幫助，提示，修復？

import java.util.ArrayList; 

public class pro1 
{ 
private String lettersLeft; 
private ArrayList<String> subsets; 

public pro1(String input) 
{ 
    lettersLeft = input; 
    subsets = new ArrayList<String>(); 
} 

public void createSubsets() 
{  
    if(lettersLeft.length() == 1) 
    { 
     subsets.add(lettersLeft); 
    } 
    else 
    { 
     String removed = lettersLeft.substring(0,1); 
     lettersLeft = lettersLeft.substring(1); 
     createSubsets(); 
     for (int i = 0; i <= lettersLeft.length(); i++) 
     { 
      String temp = removed + subsets.get(i); 
      subsets.add(temp); 
     } 
     subsets.add(removed); 
    } 
} 

public void showSubsets() 
{ 
    System.out.print(subsets); 
} 
} 

我的測試類是在這裏：

public class pro1 
{ 
public static void main(String[] args) 
{ 
    pro1s = new pro1("abba"); 
    s.createSubsets(); 
    s.showSubsets(); 
} 
} 

Answer 1

嘗試

int numSubsets = (int)java.lang.Math.pow(2,toSubset.length()); 
for (int i=1;i<numSubsets;i++) { 
    String subset = ""; 
    for (int j=0;j<toSubset.length();j++) { 
     if ((i&(1<<j))>0) { 
      subset = subset+toSubset.substring(j,j+1); 
     } 
    } 
    if (!subsets.contains(subset)) { 
     subsets.add(subset); 
    } 
} 

其中toSubset是要子集（在你的例子String toSubset="abba"）和subsets字符串是ArrayList中來包含結果。

要做到這一點，我們實際上遍歷了大小爲2^A的冪集（所有子集的集合），其中A是原始集合的大小（在此例中爲字符串的長度）。

每個子集可以用從0到2^A-1的數字唯一標識，其中第j位（0索引）的值指示該元素是否存在，1表示存在，0表示不存在。請注意，數字0表示對應於空集的二進制字符串00 ... 0。因此，我們從1開始計數（您的示例沒有將空集顯示爲期望的子集）。

對於每個值，我們通過查看每個位的位置並使用按位算法確定它是1還是0來構建子集字符串。 1<<j是第j個二進制位中有1的整數，而i&(i<<j)是隻有在整數有1的地方纔有1的整數（因此如果我在第j個二進制數中有1，則爲0或1）。如果我在第j個二進制數字中有1，我們追加字符串的第j個元素。

最後，當您詢問唯一子集時，我們檢查是否已經使用該子集，如果沒有，我們將其添加到ArrayList。

Answer 2

使用遞歸很容易讓你的頭轉過身。一般來說，我懷疑你的問題是你在存儲在遞歸方式下的遞歸方式中的一個字符串是一個類成員變量，並且遞歸方法是同一個類的一個方法。嘗試在createSubsets()方法中使用lettersLeft局部變量。喜歡的東西：

public class Problem1 
{ 
private String originalInput; 
private ArrayList<String> subsets; 

public Problem1(String input) 
{ 
    originalInput = input; 
    subsets = new ArrayList<String>(); 
} 

// This is overloading, not recursion. 
public void createSubsets() 
{  
    createSubsets(originalInput); 
} 
public void createSubsets(String in) 
{  
    if(in.length() == 1) 
    { 
     // this is the stopping condition, the bottom of the rabbit hole 
     subsets.add(in); 
    } 
    else 
    { 
     String removed = in.substring(0,1); 
     String lettersLeft = in.substring(1); 

     // this is the recursive call, and you know the input is getting 
     // smaller and smaller heading toward the stopping condition 
     createSubsets(lettersLeft); 

     // this is the "actual work" which doesn't get performed 
     // until after the above recursive call returns 
     for (int i = 0; i <= lettersLeft.length(); i++) 
     { 
      // possible "index out of bounds" here if subsets is 
      // smaller than lettersLeft 
      String temp = removed + subsets.get(i); 
      subsets.add(temp); 
     } 
     subsets.add(removed); 
    } 
} 

的東西時，你走你的代碼試圖想通過它怎麼會跑到記得......你有結構的遞歸方法使得執行指針超出一路下跌遞歸兔子然後再做任何「真正的工作」，只需從輸入中拉出字母並將它們推入堆棧。所有的「真正的工作」正在從兔子洞裏走出來，而字母從堆棧中彈出。因此，子集列表中的第一個'a'實際上是輸入字符串'abba'中的最後一個'a'。 I.E.添加到您的子集列表中的第一個字母是因爲lettersLeft.length() == 1。 （在我的例子中爲in.length() == 1）。另外，調試器是你的朋友。逐步調試是驗證您的代碼是否實際執行您期望它在每個步驟中所做的事情的好方法。