和が7の倍数となる3つの数字の組み合わせを効率よく数えたいです。

Question

いくつかの数字が集まったデータあります。
例えば、{1,5,4,48,4,2,33,5,2,4,2,1,52,3,2,1,4}のような感じです。
ここから7の倍数となる3つの数字の組み合わせがいくつあるか数えたいです。

私の現在のベストな考え

(I)2重for文を使って7で割ったときの余りがそれぞれいくつかあるか数えます。

　　//受け取ったデータを7で割った余りに変換しました。
   int []count = new int[7];
   for(int i = 0; i < data.length; i++){
       for(int j = 0; j < 7; j++){
           if(data[i] == j){
               count[j]++;
           }
       }
   }

(II)和が7の倍数となる組み合わせは
(i)(0 0 0), <-すべて同じ数字
(ii)(0 1 6),(0,2,5),(0,3,4),(1,2,4),(3,5,6)　<-すべて異なる数字
(iii)(1,1,5),(1,3,3),(2,2,3),(2,6,6),(4,4,6),(4,5,5) <-数字の種類は2つ
のように12通りあります。
7で割った余りが0となる数字の個数がa個の場合
(i)の(0,0,0)は　(a)(a - 1)(a - 2) / 6　通りと求めることができます。
(ii),(iii)も同様にして場合の数を高校数学I・Aで習った知識で求めることができます。

一応、これで組み合わせの個数を求めることはできますが、データが多くなると
非効率だと感じました。
特に最初、7で割ったときの余りをそれぞれ数えるところでデータの個数がN個の時
2重for文で N * 7回もループするのでループする回数を減らすことができたら、さらに効率よく求まると思いました。しかし、他の方法は全く思いつかず,これが今の精一杯です。
どなたか、もっと効率の良い方法がありましたら、ご教授できないでしょうか?
もしかしたら、根本から変えるべきかもしれません。
よろしくお願い致します。

Answer 1

（1）のforは1重で捌けます。

   int []count = new int[7];
   for(int i = 0; i < data.length; i++){
       count[data[i] % 7]++;
   }

そして、「二重ループ」といっても、片方の回数が7と固定なので、計算理論上はO(n)（データ量比例）という扱いです。そんなに気にしなくて構いません。

Comments

[退会済みユーザー]

言われてみれば、(i)のfor文は２重にしなくてもいいと気づきました。
こういう考え方が重要だと改めて感じました。
また、O(n) (データ量比例)という語句を知ることもできました。
おかげで、効率よく求めることができました。
回答ありがとうございました。

Answer 2

解きかたの方針を述べます。

1. 整数配列を 7 で割った余りで分類する。
2. 7 を 3 つの整数に分割する方法を列挙する。
3. 2 の各ケース毎に、1 で求めた情報から組み合わを計算し、それらを合計する。

整数配列から、
7 での 余り -> {数字: 個数}
でグループ分けするコードをかいてみました。

import java.util.HashMap;
import java.util.Map;

public class SampleApp {
    public static void main(String[] args) {
        int[] nums = { 1, 5, 4, 48, 4, 2, 33, 5, 2, 4, 2, 1, 52, 3, 2, 1, 4 };
        // <7 での余り-> <数字 -> 個数>>
        Map<Integer, Map<Integer, Integer>> counts = new HashMap<>();
        for (int n : nums) {
            int r = n % 7;
            if (counts.get(r) == null) {
                counts.put(r, new HashMap<Integer, Integer>());
            }
            Integer count =  counts.get(r).get(n);
            if (count == null) {
                counts.get(r).put(n, 1);
            } else {
                counts.get(r).put(n, count + 1);
            }
        }

        for (int r : counts.keySet()) {
            System.out.println("" + r + ": " + counts.get(r));
        }
    }
}

実行結果

1: {1=3}
2: {2=4}
3: {3=1, 52=1}
4: {4=4}
5: {33=1, 5=2}
6: {48=1}

(0..6) から重複をゆるして和が 7 の倍数になるものは
0 0 0　　// 和が 0 になるもの
0 1 6 // 和が 7 になるもの
0 2 5
0 3 4
1 1 5
1 2 4
1 3 3
2 2 3
2 6 6 // 和が 14 になるもの
3 5 6
4 4 6
4 5 5
の様に分類・列挙していくのがよいです。
これはプログラムでも列挙できると思います。

ぜひ 質問文に現れる 7 , 3 といった定数を、変数にして、汎用的なコードを書くことに挑戦してみるとよいと思います。

Comments

[退会済みユーザー]

回答ありがとうございます。
「HashMapを使って解く」勉強になりました。7,3をそれぞれn,mに変えて汎用的なコードが
書けるようにしてみます。

Answer 3

大筋にはいいと思いますが、重大な問題があります。
例示されたデータを7で割った余りで分類すると次のようになります。

0:         →0個
1: 1,1,1   →3個
2: 2,2,2,2 →4個
3: 52,3    →2個
4: 4,4,4,4 →4個
5: 5,33    →2個
6: 48      →2個

(II)の方法で(1,2,4)の組を作るとき、個数だけカウントしたものの掛け算をした場合、
344=48通りになりますが、現実には{1,2,4}の1通りのみです。
これは、それぞれの1,2,4を別個のものとして数えたため、大量の重複が発生したためです。

なので、7で割った余りで分類した後、それぞれの数字が何個あるかを数えなければいけません。
その分類をするコード例が次です。

//import static java.util.stream.Collectors.*;
Map<Integer, Map<Integer, Long>> map =
            Arrays.stream(data).boxed()
                .collect(groupingBy(i -> i % 7, groupingBy(i -> i, counting())));

これで、余りの数をキーにmapから取ってきて、1個必要なら種類数、2個なら種類数の組み合わせ+2個以上ある数字の個数　というように処理するべきかと。

Comments

[退会済みユーザー]

まず、初めに
誤解を招いてしまい、すみませんでした。
>3*4*4=48通りになりますが、現実には{1,2,4}の1通りのみです。
これは、それぞれの1,2,4を別個のものとして数えたため、大量の重複が発生したためです。

それぞれの数字を一枚のカードと考えるので重複もあり得ます。
例えば1,2,4がそれぞれ2枚ずつあるとき組み合わせは 2 * 2 * 2 = 8　通りです。

>7で割った余りで分類した後、それぞれの数字が何個あるかを数えなければいけません。

すみませんが、(I)の処理であらかじめ受け取ったデータをそれぞれ7で割った余りに
変換しています。それをカウントしています。

[退会済みユーザー]

でも、HashMapを使うということは勉強になりました。回答ありがとうございました。