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.sublistのjavadocは言う

指定された fromIndex (これを含む) と toIndex (これを含まない) の間のこのリストの部分のビューを返します。

ここでの「排他的」という言葉は重要です。

変えるだけなら

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

に

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

あなたのコードは動作します。

于 2012-04-21T18:28:11.453 に答える
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 に答える