找到子集的邏輯錯誤

我試圖將代碼概括爲find all subsets of a given string（重複的元素將被視爲不同），將其用於任何列表。找到子集的邏輯錯誤

public class Subsets{ 
private static <T> void RecursiveSubsets(List<List<T>> list, ArrayList<T> soFar, List<T> rest) 
{ 
if(rest.isEmpty()) 
{ 
    list.add(soFar); 
} 
else 
{ 
    List<T> remaining; 
    if(rest.size() == 1) 
    { 
    remaining = new ArrayList<T>(); 
    } 
    else 
    { 
    remaining = rest.subList(1, rest.size() - 1); 
    } 
    //include the element 
    ArrayList<T> includeFirst = new ArrayList<T>(soFar); 
    includeFirst.add(rest.get(0)); 
    RecursiveSubsets(list, includeFirst, remaining); 
    //exclude the element 
    RecursiveSubsets(list, soFar, remaining); 
} 
} 

public static <T> List<List<T>> getAllSubsets(List<T> set) 
{ 
List<List<T>> subsets = new ArrayList<List<T>>(); 
RecursiveSubsets(subsets,new ArrayList<T>(),set); 
return subsets; 
} 

public static void main(String [] args) 
{ 
List<Integer> ints = new ArrayList<Integer>(){ 
    { 
    add(0);add(1);add(2);add(3); 
    } 
}; 

List<List<Integer>> allSubsets = getAllSubsets(ints); 
System.out.println("Total Subsets returned : " + allSubsets.size()); 
for(int i=0; i<allSubsets.size(); ++i) 
    { 
    for(int j=0; j<allSubsets.get(i).size(); ++j) 
    { 
    System.out.print(allSubsets.get(i).get(j) + " "); 
    } 
    System.out.println(); 
    } 
} 
}

經過幾次嘗試後，我能夠得到這個編譯，但這是我得到的輸出。即使我有更多的整數，它仍然會返回這個。我無法弄清楚我錯過了什麼，需要幫助找到它。

$ java Subsets 
Total Subsets returned : 4 
0 1 
0 
1

來源

2012-04-21 nikhil

我也需要重複。 – nikhil 2012-04-21 16:23:15

哦，對不起，我看錯了問題:) – 2012-04-21 16:25:03

你的程序實際上幾乎是正確的，而你只是子列表邏輯有點不對。

List.sublist爲的JavaDoc說

返回指定fromIndex（包括）元素範圍爲排他性之間此列表的所述部分的視圖。

這裏的「獨佔」一詞至關重要。

如果你只需要改變

remaining = rest.subList(1, rest.size() - 1);

到

remaining = rest.subList(1, rest.size());

你的代碼工作。

來源

2012-04-21 18:28:11

非常感謝您花時間幫助我。它真的很感激。 – nikhil 2012-04-21 19:56:04

這樣做的邏輯（在僞代碼）通常是：

List<List<T>> subsets(List<T> list){ 

    if(list is empty) return a list containing the empty list; 

    // else: 

    subsetsWithout = subsets(list w/o 0th element); 

    result.addAll(subsetsWithout); 

    for(subset in subsetsWithout) 
     result.add(subset + list[0]) 

    return result; 
}

看起來你正在做的事情是不同的，而事實上，你想通過函數返回的東西參數使它更加混亂。

來源

2012-04-21 16:53:26 trutheality

找到子集的邏輯錯誤

回答

相關問題