0

すべての可能な組み合わせを別のコレクションに格納したい文字列の配列リストがあります。

例えば：

[air,bus,car]
->
[air]
[bus]
[car]
[air,bus]
[air,car]
[bus,air]
[bus,car]
[car,air]
[car,bus]
[air,bus,car]
[air,car,bus]
...
[car,bus,air]

繰り返しは重要ではありません。私が今持っているコードは次のとおりです。

public ArrayList<String> comb(ArrayList<String> wrds, ArrayList<String> str, int size)
{
    ArrayList<String> s = new ArrayList<String>();
    s.addAll(str);
    if(size != a1.size())
    {
        Iterator e = a1.iterator();
        while(e.hasNext())
        {
            s.add((String)e.next());
        }
        size++;
    }
}

組み合わせを保存できるように、再帰的に自分自身を呼び出そうとしています。コードのどこに、またはどの部分が欠けているかについて、何か助けを得ることができますか?

4

3 に答える 3

5

これは宿題なので、答えの背景を説明します。

これを解決する鍵は、再帰を使用することです。

まず、配列に 2 つの項目があるとします。最初のアイテムを削除して、最初の組み合わせにすることができます。最初のアイテムに残りのアイテムを追加すると、2 番目の組み合わせが得られます。2 番目の項目を削除すると、3 番目の組み合わせが得られます。残りのアイテムを追加すると、4 番目の組み合わせが得られます。あなたが持っていたなら["air", "bus"]、それは次のようなものになるでしょう：

["air"]
["air", "bus"]
["bus"]
["bus", "air"]

返すメソッドは次のようになります。

String[][] combinations(String[] strings)

注意すべき重要な点は、単一の文字列を含む配列をこのメソッドに渡すことができ、単一の文字列を含む配列を含む配列を返すことができることです。

文字列の組み合わせを集計する必要があるため、問題は少し複雑です。そのため、それを解決する前に、再帰を理解することが重要です。

2 つの数値を取り、それらを乗算する乗算メソッドを作成したいとしますが、自由に使用できるのは加算と減算だけです。次のような、他の数値が終了条件に達するまで数値の 1 つを自分自身に追加する再帰関数を作成できます。

public int multiply(int value1, int value2) 
{
  if (value1 > 1) 
  {
    int remaining = value1 - 1;
    return value2 + multiply(remaining, value2);
  }
  else 
  {
    return value2;
  }
}

配列で同じことを行うことができますが、値がヒットしたときに終了する代わりに1、配列に1つのアイテムが含まれているときに終了します。

public String[][] combinations(String[] strings) 
{
  if (strings.length > 1) 
  {
    ...
  }
  else 
  {
    return new String[][]{strings};
  }
}

Java API の理由により、java.util.List配列よりもはるかに使いやすいため、次のようなものが必要です。

public List<List<String>> combinations(List<String> strings) 
{
  if (strings.size()> 1) 
  {
    ...
  }
  else 
  {
    List<List<String>> result = new ArrayList<List<String>>();
    result.add(strings);
    return result;
  }
}

ここ...が重要な部分です。結果となるリストのリストを保持し、strings. 各文字列について、その文字列を結果に追加してから、現在の文字列を差し引いたサブリストを作成する必要があります。これを使用して、combinationsメソッドを再度呼び出し、結果を反復処理して、現在の各リストに含まれている文字列を追加します。コードでは次のようになります。

public List<List<String>> combinations(List<String> strings) 
{
  if (strings.size() > 1) 
  {
    List<List<String>> result = new ArrayList<List<String>>();

    for (String str : strings) 
    {
      List<String> subStrings = new ArrayList<String>(strings);
      subStrings.remove(str);

      result.add(new ArrayList<String>(Arrays.asList(str)));

      for (List<String> combinations : combinations(subStrings)) 
      {
        combinations.add(str);
        result.add(combinations);
      }
    }

    return result;
  }
  else 
  {
    List<List<String>> result = new ArrayList<List<String>>();
    result.add(new ArrayList<String>(strings));
    return result;
  }
}

要約すると、文字列のリストを 1 つの項目に減らし、それを前の項目と組み合わせて、スレッドがコール スタックを返すときに考えられるすべての組み合わせを生成します。

于 2013-01-23T18:40:08.370 に答える
4 
public static void combination(Object[] array){
         for(int x = 0; x < (1 << array.length); x++){
             System.out.print("[");
             for(int y = 0; y < array.length; y++){
                 if(checkIsOn(x, y){
                    System.out.print(array[y]);
                 }
             }
             System.out.println("]");
         }
    }

    public static boolean checkIsOn(int mast, int position){
         return (mast & (1 << position) > 0);
    }
于 2016-03-15T23:32:04.687 に答える
0

リストを再帰関数のパラメーターとして使用します。最初のアイテムを除くすべてを含む新しいリストを使用して、関数自体から呼び出すことができます。

于 2013-01-23T16:43:20.710 に答える