1

我试图概括代码以查找给定字符串的所有子集（重复的元素将被视为不同的元素）到一个适用于任何列表的子集中。

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
4

2 回答 2

1

这个（在伪代码中）的逻辑通常是：

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-21T16:53:26.083 回答
1

您的程序实际上几乎是正确的，只是子列表逻辑有点错误。

List.sublist的 javadoc说

返回此列表在指定的 fromIndex（包括）和 toIndex（不包括）之间的部分的视图。

这里的“排他性”这个词很关键。

如果你只是改变

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

到

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

你的代码有效。

于 2012-04-21T18:28:11.453 回答