3

与えられたリストのすべてのサブリストを整数で出力したいこの関数を書いています。これらの整数の合計は、指定された数に等しくなければなりませんn。i値0で始まるヘルプ変数もあります。リストと各サブリストはどちらもArrayListです。したがって、メソッドは現在次のようになります。

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
            int i) {

        if (sublist.sum() == n) {
            System.out.println(sublist.toString());
        } 
        else {
            for (int j = 0; j < numbers.size(); j++) {
                sublist.add(numbers.get(i));
                printSublists(numbers, sublist, n, i + 1);
                sublist.remove(numbers.get(i));
            }
        }
    }

もちろん、私はすでにメソッドを持っていますsum()。メソッドはこれを実行します。とするnumbers = [1, 3 , 4]とn == 4、メソッドは[4]and[1 ,3]を出力する必要がありますが、出力するのは[1, 3]？forループはそのトリックを正しく実行する必要があると思いますか？誰かが私を正しい軌道に乗せてくれれば幸いです。

更新：メソッドに与える値： 

numbers = [1, 3, 4]
n = 4
i = 0
sublist = []

更新2：

再帰的にしたいと言うのを忘れました:)

4

4 に答える 4

2

合計が。の最初のサブリストが表示されると、再帰は停止しますn。問題は（のみ）ループではなく、終了基準です。サブリストの長さが0になると、再帰関数は停止するはずです。

ここで、私はあなたの問題に対して機能する再帰的な解決策を書きました。違いますが、直せませんでした。空のサブリストから始めますが、私は完全なリストで再帰を開始し、それをより小さなサブリストに分割することを選択しました。これにより、ツリーのような構造が作成されます。

                        [1234]
                     [123]  [234]
                   [12] [23]   [34]
                  [1][2]  [3]    [4]

最初の葉（）に到達するまで「右」に歩かなければならないことがすぐにわかります1。その後は「左」にしか歩きません。このようにして、すべてのサブリストに1回だけアクセスします。

Javaで書かれたアイデアは次のとおりです。

public static void main (String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(1);
  list.add(3);
  list.add(4);
  list.add(0);
  printSublists(list, list, 4, true, 0);
}

public static void printSublists(List<Integer> numbers, List<Integer> sublist, int n, boolean walkRight, int level) {

  // the test
  if (sum(sublist) == n)
     System.out.println(sublist);

  // the exit criteia (leaf reached)
  if (sublist.size() == 1)
     return;

  // visit the right sublist
  if (walkRight) 
    printSublists(numbers, sublist.subList(0, sublist.size()-1), n, walkRight, level+1);

  // we only walk the right path once
  walkRight = false;

  // visit the left sublist
  printSublists(numbers, sublist.subList(1, sublist.size()), n, walkRight, level+1);
}

そしてそれが出力です：

[1, 3]
[4]
[4, 0]
于 2012-03-13T11:54:53.090 に答える
2 
@Test
public void test() {
    printSublists(new HashSet<Integer>(Arrays.asList(2, 3, 4, 1, 2)), new HashSet<Integer>(), 4);
}

private void printSublists(Set<Integer> numbers, Set<Integer> subList, int expected) {

    for (Integer element : numbers) {
        subList.add(element);
        if (sum(subList) == expected) {
            System.out.println("result =" + subList);
        }
        Set<Integer> listWithoutElement = withoutElement(numbers, element);
        printSublists(listWithoutElement, subList, expected);
        subList.remove(element);

    }
}

private Set<Integer> withoutElement(Set<Integer> numbers, Integer element) {
    Set<Integer> newList = new HashSet<Integer>(numbers);
    newList.remove(element);
    return newList;
}

private int sum(Collection<Integer> sublist) {
    int sum = 0;
    for (Integer e : sublist) {
        sum += e;
    }
    return sum;

}

これがあなたの解決策です。この問題は、リストではなくセットにあるはずです。

[2,3,4,1,2]を設定した場合、解は[3,1][4][2,2]になります。次に、問題は再帰的である必要があります。もちろん重複を削除する必要があります:)

于 2012-03-13T11:54:54.560 に答える
0

コードのforループ：

        for (int j = 0; j < numbers.size(); j++) {
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, i + 1);
            sublist.remove(numbers.get(i));
        }

変数jが使用されることはありません。ですから、あなたはまったく同じことを繰り返し行っていますが、それがあなたのやりたいことだと私は真剣に疑っています。

于 2012-03-13T12:10:02.353 に答える
0

おそらくあなたはこのように何かをする必要があるでしょう-

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
        int i) {

    if (sublist.sum() == n) {
        System.out.println(sublist.toString());
        sublist.removeAll(sublist);//added remove all here
    } 
    else {
        //for (int j = 0; j < numbers.size(); j++) {//commented this line
        while(i<number.size()){//need while loop
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, ++i);//i+1 changed to ++i
            //sublist.remove(numbers.get(i));// commented here
        }
    }
}
于 2012-03-13T12:29:01.080 に答える