数列が格納された配列vと基準となる値scoreから条件を満たすパターン数を出力するメソッドを書きたい

ランダムな数列が格納された配列vと基準となる値scoreからある条件を満たすパターン数を出力するメソッドを書きたいのですがうまくいきません。
条件は、例としてscoreが10、配列vが{1,5,5,10}の場合に、{1,5,5,10}同士の和でscore以上となる組み合わせを1つのパターンとしてカウントします。この時求めたいパターンとして{5,5},{10}であり、{5,5,1}や{1,10}は1を除いても条件を満たすため、無駄なものを含んでいるとしてカウントしません。どのようにすればできるでしょうか。

   public  void check(int[] v,int score) {
        int count = 0;
        for(int i = 0; i<v.length-1; i++){
             int e = v[i];
             if(e >= score){
                 count++;
             }else{
                 for(int j = i+1; j<v.length; j++){
                     e += v[j];
                     if(e >= score){
                         count++;
                         continue;
                     }
                 }
             }
           
        }
        System.out.println(count);
}

BeatStar

2020/09/27 11:13

部分和なら { 10, 1 } は 10 とは一致しませんよ。 { 10 }, { 5, 5 } だけですよ。

xebme

2020/09/27 16:35

実行例は以下でよろしいか int[] v = { 2, 3, 5, 1, 8, 3 }; >>> score = 1 : [1][2][3][5][8] >>> score = 2 : [2][3][5][8] >>> score = 3 : [2, 1][3][5][8] >>> score = 4 : [3, 2][3, 3][5][8][3, 1] >>> score = 5 : [3, 2][3, 3][5][8] >>> score = 6 : [8][5, 1][5, 2][5, 3] >>> score = 7 : [8][5, 2][5, 3] >>> score = 8 : [5, 2, 1][8][5, 3]

st5005

2020/09/28 00:54

xebmeさん配列に同じ値が複数、xebmeさんの例ですとvに3が2個ありますが、score1とscore3の時は3を2つともカウントするようにしたいです。なので、 >>> score = 1 : [1][2][3][3][5][8] >>> score = 3 : [2, 1][3][3][5][8] という感じにしたいです。他はその通りです。

xebme

2020/09/28 04:04 編集

3の重複を除去する場合は集合を保持しなければなりませんが、重複もカウントするならカウンターに加算だけでOK。ヒント：配列から数字を大きい順に取り出す。 >>> [2, 3, 5, 1, 8, 3] >>> 1 : [[8], [5], [3], [3], [2], [1]] : 6 >>> 2 : [[8], [5], [3], [3], [2]] : 5 >>> 3 : [[8], [5], [3], [3], [2, 1]] : 5 >>> 4 : [[8], [5], [3, 3], [3, 2], [3, 1]] : 5 >>> 5 : [[8], [5], [3, 3], [3, 2]] : 4 >>> 6 : [[8], [5, 3], [5, 3], [5, 2], [5, 1]] : 5 >>> 7 : [[8], [5, 3], [5, 3], [5, 2]] : 4 >>> 8 : [[8], [5, 3], [5, 3], [5, 2, 1]] : 4 >>> 9 : [[8, 5], [8, 3], [8, 3], [8, 2], [8, 1]] : 5 >>> 10 : [[8, 5], [8, 3], [8, 3], [8, 2]] : 4 >>> 11 : [[8, 5], [8, 3], [8, 3], [8, 2, 1]] : 4 >>> 12 : [[8, 5], [8, 3, 3], [8, 3, 2], [8, 3, 1]] : 4 >>> 13 : [[8, 5], [8, 3, 3], [8, 3, 2]] : 3 >>> 14 : [[8, 5, 3], [8, 5, 3], [8, 5, 2], [8, 5, 1]] : 4 >>> 15 : [[8, 5, 3], [8, 5, 3], [8, 5, 2]] : 3 >>> 16 : [[8, 5, 3], [8, 5, 3], [8, 5, 2, 1]] : 3 >>> 17 : [[8, 5, 3, 3], [8, 5, 3, 2], [8, 5, 3, 1]] : 3 >>> 18 : [[8, 5, 3, 3], [8, 5, 3, 2]] : 2 >>> 19 : [[8, 5, 3, 3], [8, 5, 3, 2, 1]] : 2 >>> 20 : [[8, 5, 3, 3, 2], [8, 5, 3, 3, 1]] : 2 >>> 21 : [[8, 5, 3, 3, 2]] : 1 >>> 22 : [[8, 5, 3, 3, 2, 1]] : 1 >>> 23 : [] : 0

momon-ga

2020/09/28 04:23

あれ？8は、3,3,2抽出するのかと思ったけど、いらないんですね

st5005

2020/09/28 04:25

momon-gaさんすみません。 8の場合は3,3,2もですね。見落としてました。

momon-ga

2020/09/28 04:48

あ、やはり。では、7の3,3,1も同様ですね。

xebme

2020/09/28 05:58 編集

重複する場合の私の理解が誤っているようです。ありがとうございました。

xebme

2020/09/28 09:40

重複について、もう一度だけ質問させてください。この例で3を1つだけ含む組はペアで現れます。これは出題の意図ですか？ v = [2, 3, 5, 1, 8, 3] score 1 : [[8], [5], [3], [3], [2], [1]] score 2 : [[8], [5], [3], [3], [2]] score 3 : [[8], [5], [3], [3], [2, 1]] score 4 : [[8], [5], [3, 3], [3, 2], [3, 1], [3, 2], [3, 1]] score 5 : [[8], [5], [3, 3], [3, 2], [3, 2]] score 6 : [[8], [5, 3], [5, 3], [5, 2], [5, 1], [3, 3], [3, 2, 1], [3, 2, 1]] score 7 : [[8], [5, 3], [5, 3], [5, 2], [3, 3, 2], [3, 3, 1]] score 8 : [[8], [5, 3], [5, 3], [5, 2, 1], [3, 3, 2]] score 9 : [[8, 5], [8, 3], [8, 3], [8, 2], [8, 1], [5, 3, 3], [5, 3, 2], [5, 3, 1], [5, 3, 2], [5, 3, 1], [3, 3, 2, 1]] score 10 : [[8, 5], [8, 3], [8, 3], [8, 2], [5, 3, 3], [5, 3, 2], [5, 3, 2]] score 11 : [[8, 5], [8, 3], [8, 3], [8, 2, 1], [5, 3, 3], [5, 3, 2, 1], [5, 3, 2, 1]] score 12 : [[8, 5], [8, 3, 3], [8, 3, 2], [8, 3, 1], [8, 3, 2], [8, 3, 1], [5, 3, 3, 2], [5, 3, 3, 1]] score 13 : [[8, 5], [8, 3, 3], [8, 3, 2], [8, 3, 2], [5, 3, 3, 2]] score 14 : [[8, 5, 3], [8, 5, 3], [8, 5, 2], [8, 5, 1], [8, 3, 3], [8, 3, 2, 1], [8, 3, 2, 1], [5, 3, 3, 2, 1]] score 15 : [[8, 5, 3], [8, 5, 3], [8, 5, 2], [8, 3, 3, 2], [8, 3, 3, 1]] score 16 : [[8, 5, 3], [8, 5, 3], [8, 5, 2, 1], [8, 3, 3, 2]] score 17 : [[8, 5, 3, 3], [8, 5, 3, 2], [8, 5, 3, 1], [8, 5, 3, 2], [8, 5, 3, 1], [8, 3, 3, 2, 1]] score 18 : [[8, 5, 3, 3], [8, 5, 3, 2], [8, 5, 3, 2]] score 19 : [[8, 5, 3, 3], [8, 5, 3, 2, 1], [8, 5, 3, 2, 1]] score 20 : [[8, 5, 3, 3, 2], [8, 5, 3, 3, 1]] score 21 : [[8, 5, 3, 3, 2]] score 22 : [[8, 5, 3, 3, 2, 1]] score 23 : []

st5005

2020/09/28 11:15 編集

xebmeさん真剣に考えてくださってありがとうございます。 3を1つだけ含む組はペアというのは例えば、score 7 : [[8], [5, 3], [5, 3], [5, 2], [3, 3, 2], [3, 3, 1]]の[5,3]が2つあることでしょうか。そうであれば重複は考えず、2つともカウントしたいです。

行動規範の内容に同意します

回答1件

ベストアンサー

重複ありのカウント

Java
1public static int findListCount_(final int score, final int[] v) {
2  int[] result = {0};
3  Deque<Integer> vlist = IntStream.of(v).mapToObj(Integer::valueOf).sorted().collect(Collectors.toCollection(ArrayDeque::new));
4  go_(score, vlist, 0, result);
5  return result[0];
6}
7
8public static void go_(final int score, final Deque<Integer> rem, final int sum, final int[] acc) {
9    //System.out.println(rem +" - " + candidate + " - " + acc[0]);
10  if (sum >= score) {
11    acc[0]++;
12    return;
13  }
14  while (!rem.isEmpty()) {
15    int val = rem.removeLast();
16    if (val >= score) {
17      acc[0]++;
18      continue;
19    }
20    go_(score, new ArrayDeque<>(rem), sum+val, acc);
21  }
22}

テストコード

Java
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Arrays;
4import java.util.Collection;
5import java.util.Deque;
6import java.util.HashSet;
7import java.util.List;
8import java.util.Set;
9import java.util.stream.Collectors;
10import java.util.stream.IntStream;
11
12public class MinSet_ {
13
14  public static void main(String... args) {
15    int[] v = { 2, 3, 5, 1, 8, 3 };
16    System.out.println("v = " + Arrays.toString(v));  
17    for (int score= 1;  score <= 23; score++) {
18      //System.out.println("score " + score);
19      System.out.println("score " + score + " : " + findList(score, v) + " : " + findListCount_(score, v));
20    }
21    //
22    System.out.println("--------------------------------------");
23    for (int score= 1;  score <= 23; score++) {
24      //System.out.println("score " + score);
25      Collection<List<Integer>> result = findSet(score, v);
26      System.out.println("score " + score + " : " + result + " : " + result.size());
27    }
28  }
29
30  public static Collection<List<Integer>> findList(final int score, final int[] v) {
31    List<List<Integer>> result = new ArrayList<>();
32    Deque<Integer> vlist = IntStream.of(v).mapToObj(Integer::valueOf).sorted().collect(Collectors.toCollection(ArrayDeque::new)); 
33    go(score, vlist, new ArrayList<>(), result);
34    return result;
35  }
36  
37  public static Collection<List<Integer>> findSet(final int score, final int[] v) {
38    Set<List<Integer>> result = new HashSet<>();
39    Deque<Integer> vlist = IntStream.of(v).mapToObj(Integer::valueOf).sorted().collect(Collectors.toCollection(ArrayDeque::new)); 
40    go(score, vlist, new ArrayList<>(), result);
41    return result;
42  }
43
44  public static void go(final int score, final Deque<Integer> rem, final List<Integer> candidate, final Collection<List<Integer>> acc) {
45    //System.out.println(rem +" - " + candidate + " - " + acc);
46    long sum = candidate.stream().collect(Collectors.summingLong(Long::valueOf));
47    if (sum >= score) {
48      acc.add(candidate);
49      return;
50    }
51    while (!rem.isEmpty()) {
52      List<Integer> uu = new ArrayList<>(candidate);
53      int val = rem.removeLast();
54      uu.add(val);
55      if (val >= score) {
56        acc.add(uu);
57        continue;
58      }
59      go(score, new ArrayDeque<>(rem), uu, acc);
60    }
61  }
62  
63  public static int findListCount_(final int score, final int[] v) {
64    int[] result = {0};
65    Deque<Integer> vlist = IntStream.of(v).mapToObj(Integer::valueOf).sorted().collect(Collectors.toCollection(ArrayDeque::new)); 
66    go_(score, vlist, 0, result);
67    return result[0];
68  }
69
70  public static void go_(final int score, final Deque<Integer> rem, final int sum, final int[] acc) {
71    //System.out.println(rem +" - " + candidate + " - " + acc[0]);
72    if (sum >= score) {
73      acc[0]++;
74      return;
75    }
76    while (!rem.isEmpty()) {
77      int val = rem.removeLast();
78      if (val >= score) {
79        acc[0]++;
80        continue;
81      }
82      go_(score, new ArrayDeque<>(rem), sum+val, acc);
83    }
84  }
85
86}