0

これを行うための私のコードは次のとおりです。文字列表現では機能しますが、文字列表現では機能しませんArrayList<ArrayList<Integer>>。

public static void partition(int n) {
    partition(n, n, "",
            new ArrayList<ArrayList<Integer>>(),
            new ArrayList<Integer>());
}

public static void partition(int n, int max, String temp,
                             ArrayList<ArrayList<Integer>> master,
                             ArrayList<Integer> holder) {
    if (n == 0) {
        ArrayList<Integer> temp1 = new ArrayList<Integer>();
        for (int i = 0; i <= holder.size(); i++) {
            temp1.add(holder.get(0));
            holder.remove(0);
        }
        master.add(temp1);
        System.out.println(temp);
    }

    for (int i = Math.min(max, n); i >= 1; i--) {
        holder.add(i);
        partition(n - i, i, temp + " " + i, master, holder);
    }
}

私がtemp1で面白いビジネスをしている理由は、マスターに一時を追加すると、前の要素が変更されるためです（マスター内のすべての要素は同じ場所を指す参照になります）。コピー+クリア。

文字列は機能します。なぜそうではないのArrayList<ArrayList<Integer>>ですか？そして、どうすればそれを修正できますか？

の出力ArrayList<ArrayList<Integer>>は次のとおりです。

[[5], [4, 1], [3, 2], [1, 1], [2, 2], [1, 1, 1], [1, 1, 1, 1]]
4

2 に答える 2

3

holderブランチ内で配列を混同しているのですが、ifこれはすべきではありません。次のことを試してください。

public static void partition(int n, int max, String temp,
                             ArrayList<ArrayList<Integer>> master,
                             ArrayList<Integer> holder) {
    if (n == 0) {
        ArrayList<Integer> temp1 = new ArrayList<Integer>();
        for (int i = 0; i < holder.size(); i++) {
            temp1.add(holder.get(i));
        }
        master.add(temp1);
        System.out.println(temp);
    }

    for (int i = Math.min(max, n); i >= 1; i--) {
        holder.add(i);
        partition(n - i, i, temp + " " + i, master, holder);
        holder.remove(holder.size() - 1);
    }
}
于 2011-09-22T13:31:36.797 に答える
0

再帰の後続の各ブランチにコピーholderを渡す必要があります。

Java 7：

public static void main(String[] args) {
    List<List<Integer>> list = partition(5);
    for (List<Integer> comb : list)
        System.out.println(comb);
}

public static List<List<Integer>> partition(int n) {
    List<List<Integer>> list = new ArrayList<>();
    partition(n, n, "", list, new ArrayList<Integer>());
    return list;
}

public static void partition(int i, int max, String indent,
                             List<List<Integer>> master, List<Integer> holder) {
    if (i == 0) {
        master.add(holder);
        System.out.println(
                indent + "i=" + i + ",max=" + max + "    comb=" + holder);
    }

    for (int j = Math.min(max, i); j >= 1; j--) {
        ArrayList<Integer> temp = new ArrayList<>(holder);
        temp.add(j);
        System.out.println(
                indent + "i=" + i + ",j=" + j + ",max=" + max + "  temp=" + temp);
        partition(i - j, j, indent + "  ", master, temp);
    }
}

再帰ツリーの出力n=5：

i=5,j=5,max=5  temp=[5]
  i=0,max=5    comb=[5]
i=5,j=4,max=5  temp=[4]
  i=1,j=1,max=4  temp=[4, 1]
    i=0,max=1    comb=[4, 1]
i=5,j=3,max=5  temp=[3]
  i=2,j=2,max=3  temp=[3, 2]
    i=0,max=2    comb=[3, 2]
  i=2,j=1,max=3  temp=[3, 1]
    i=1,j=1,max=1  temp=[3, 1, 1]
      i=0,max=1    comb=[3, 1, 1]
i=5,j=2,max=5  temp=[2]
  i=3,j=2,max=2  temp=[2, 2]
    i=1,j=1,max=2  temp=[2, 2, 1]
      i=0,max=1    comb=[2, 2, 1]
  i=3,j=1,max=2  temp=[2, 1]
    i=2,j=1,max=1  temp=[2, 1, 1]
      i=1,j=1,max=1  temp=[2, 1, 1, 1]
        i=0,max=1    comb=[2, 1, 1, 1]
i=5,j=1,max=5  temp=[1]
  i=4,j=1,max=1  temp=[1, 1]
    i=3,j=1,max=1  temp=[1, 1, 1]
      i=2,j=1,max=1  temp=[1, 1, 1, 1]
        i=1,j=1,max=1  temp=[1, 1, 1, 1, 1]
          i=0,max=1    comb=[1, 1, 1, 1, 1]

リストの出力n=5：

[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

参照：効率的に合計する順列の構築

于 2021-05-03T12:41:19.550 に答える