2

[条件]
1.配列 ary はソートされている。
2.N は ary の最大値以上

上記条件をみたすような一般の ary、N に対し、
連続 i (> 0) 個の和が N 以下の組み合わせの総数の求めたいと考えています。
どのように求めるのが効率的でしょうか?

例を示しますので、「下記の非効率な箇所」もしくは「より効率的な求め方」
を教えて頂けたら、幸いです。

N = 10

ary = (1..N).to_a # 最大値がN以下の(ソートされた)配列の例
size = ary.size

cnt = size
# 連続i(> 1)個取り出す
i = 2
i_sum = ary[0] + ary[1]
sum = i_sum
while sum <= N
  j = 0
  while sum <= N
    cnt += 1
    j += 1
    break if j > size - i
    # 再計算せず前の結果を利用
    sum = sum - ary[j - 1] + ary[i - 1 + j]
  end
  i += 1
  # 再計算せず前の結果を利用
  i_sum += ary[i - 1]
  sum = i_sum
end
p cnt

2 件の回答 2

3

効率的に処理するなら、ループの回数を減らすことと、ループ内での処理を減らすことが効果的です。

今回の問題の場合、次の性質があることが分かります。

  • aryの要素は、1つずつなら全て要求を満たす(ので、数える必要はない)
  • aryの要素で、N/2以上の値のうち、最小値以外は、他の値との組み合わせはない

上記を考慮すると、次のような手順で効率的に求められると思います。

  1. カウント値を、argの要素数として初期化
  2. aryの後ろから前に辿りながら、合計がN以下になる組み合わせを列挙

自分はruby使いではないので、C#で、C#らしくないサンプルメソッドを示します。

int Count2(List<int> ary, int N) {
    var c = ary.Count; // 初期値(1つずつとった場合を総カウント)
    for (int iEnd = ary.Count - 1; iEnd > 0; iEnd--) { // iEnd==0は不要
        if (ary[iEnd - 1] >= N / 2) continue; // 探索ポイントの1つ手前がN/2以上なら、合計はNを越えるので探索不要
        int sum = ary[iEnd]; // 合計の初期値を与えることで計算を削減
        for (int iBegin = iEnd - 1; iBegin >= 0; iBegin--) {
            if (s + ary[iBegin] > N) break;
            s += ary[iBegin];
            c++;
        }
    }
    return c;
}

私が気づいていない節約可能なポイントもあると思いますが、こういう考え方で処理効率は高められると思います。

2
  • s はどこで決めたのでしょうか?
    – TOM
    Commented 2015年7月20日 6:20
  • 1
    すみません、本当のソースから変数名を書き換える際に忘れてました。sはsumに直したものとして考えてくださいませ。 なお、実際にはsumやiBeginの初期値を、iEndループの前回の結果から求めることで、ループ回数をさらに減らせると思います。 (前回のiEndを"iEnd1"として、i1~iEnd1の合計がsum1だったとすると、今回のiBegin初期値はi1、今回のsum初期値はsum1-ary[iEnd1]にします)
    – tofuma
    Commented 2015年7月21日 13:15
1

先頭を固定する方が素直な気がする。

N = 10

ary = (1..N).to_a # 最大値がN以下の(ソートされた)配列の例
size = ary.size

cnt = 0
# 先頭をary[i]に固定する
(0..size - 1).each{|i|
  j = i
  sum = ary[j]
  while sum <= N
    cnt += 1
    j += 1
    break if j > size - 1
    sum += ary[j]
  end
}
p cnt

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。