2017-04-21

AOJ - ITP1_7_B (組み合わせ) を解いてみた

偉そうに書いてるが、これは序の口の問題である。。。

AOJ - ITP1_7_B
- 解法１ algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow
- 解法２ Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks

AOJ - ITP1_7_B

How many ways? | Aizu Online Judge
自分の回答

解法１ algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow

algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow

愚直な手順（ナイーブな解法とか煽られるやつ）

アルゴリズム

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:
この問題は全ての和の組み合わせを再帰的に解き、目標の数に一致したもの以外をフィルタリングすることで解くことができます。

処理フロー

引数に対象の数列N、目標X、部分配列Pをとる関数subset_sumを作成する

subset_sumに初期値N、X、空の部分配列を入れて開始
この時点での合計値 S = 配列Xの合計値で計算する
S=Xかどうか検査
1. S==X であれば、その部分配列Pを記録して4へ進む
2. S>=X ならば、プログラム終了
3. S<Xであれば4へ進む
数列Nの長さiを取得してループを開始、i = 0 〜 iまで以下を繰り返す
1. n = 数列Nのi番目の要素とおく
2. 配列R = Nのi+1番目以降の全ての要素とおく
3. 配列TR = 配列P の末尾に n を連結したものとおく
4. 関数subset_sumに引数としてR, X, TR を渡して実行

結果

メモリ制限に引っかかる…これではダメです…でも一応nCrの組み合わせの出し方は書いておく → Javaで簡単な組み合わせの総数 nCr を求めてみる - なんとな～くしあわせ？の日記

解法２ Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks

Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks

２つのアルゴリズムを使う

配列Aと数値xが与えられた時、その和がxになる配列A内の組み合わせ（ペア）をチェックする
- Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks
数値xが２より大きくなった場合
- Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution) - GeeksforGeeks

アルゴリズムA

Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
時間計算量：これは我々がどのようなソートアルゴリズムを使っているかによる。マージソートやヒープソートをつかっている場合最悪でも (-)(nlogn) となる。クイックソートをつかっている場合は、最悪でも O(n^2) になる。
Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.
空間計算量：これも、我々がどのようなソートアルゴリズムを使っているかによる。例えば空間計算量はマージソートならばO(n)、ヒープソートならばO(1)になる。

処理フロー

引数に対象の数列A、配列サイズar_size、その和sumをとる関数hasArrayTwoCandidatesを作成する

配列Aを昇順でソートする
ソートされた配列の中の要素から候補を見つけるために、２つのインデックス用の変数を初期化する
1. １つ目の変数を、最左端の値で初期化する： L = 0
2. ２つ目の変数を、最右端の値で初期化する： R = ar_size - 1
L < R の間これを繰り返す ( while L < R )
1. もし A[L] + A[R] == sum ならば、１を返す
2. もし A[L] + A[R] < sum ならば、Lをインクリメント、L++
3. それ以外は Rをデクリメント、R--
配列全てから候補が見つからなければ、０を返す

アルゴリズムB

This method works in O(n) time if range of numbers is known.
この手法は数値の範囲が既知のものであればO(n)で動作する

処理フロー

和は与えられた和で、配列Aは我々が見つけたいペアとなる（？）

２分木の連想配列を初期化する M[] = {0, 0, 0...}
配列A[]の中にある、各々のA[i]に対して以下を実行
1. もし M[x - A[i]] がセットされていれば A[i], x - A[i] を出力
2. M[A[i]] をセットする

アルゴリズムC

処理の流れとしては、Cを走らせてから先ほどのアルゴリズムAかBを内部で使用する。

We have discussed a O(n^3) algorithm in the previous post on this topic. The problem can be solved in O(n^2Logn) time with the help of auxiliary space.
先に我々は、AとBのアルゴリズムでこれがO(n^3)で動作することを議論した。この問題は空間計算量の助けによりO(n^2 log n)で解ける

処理フロー

対象の数列をAとする

補助用の配列auxを作成する、そして全ての求めるべき和の可能性のあるペアをそこに格納する。auxのサイズは n が配列Aのサイズとすると、 n*(n-1)/2になる
補助用の配列aux[]をソートする

今やXに等しいなんらかの数値の組み合わせの和を配列auxから見つける問題は簡単化された。その２つの要素を能率的に見つけるにはアルゴリズムAが使えるだろう。

ここには以下のような特筆すべきポイントがある

配列aux は配列Aから抽出したペアを表している。配列auxから２つの要素を選ぶ一方で、その２つの要素が一般に配列Aの中にあるかどうかをチェックする必要がある
例えば、A[1]とA[2]の和が最初の要素だとして、A[2]とA[4]の和が次の要素だとすると、これは配列Aの中から抽出した４要素を持った配列ということにはならない

結果

アルゴリズムAとCを使用してやることで普通に解けた。

解法１
- ターゲットの配列が1〜100まであったとき、そこから全ての組み合わせを求めると161700になってしまう、そこから更に計算して合計値が100になるのを探すのは効率が悪すぎる
解法２
- 求めるべき要素３つのうち１つを決め撃ちして、残り二つを配列から挟み撃ちの形で求めているので早い

2017-04-21

Bash/Octaveで順列・組み合わせ

プログラミング数学 Octave bash

Bashで計算しようとしたのだが、結論から言うと遅すぎて使えない。

Octaveで計算すると早かったのでそっちを推奨する。

Bash

順列 (nPr)

bash - Generate combinations of elements with echo - Stack Overflow
- 参考になったが、これはCombinationではなくPermutationだ

#!/bin/bash

n=$1
r=$2

elem=$(echo `seq 1 $n` | tr ' ' ',')
set="{"${elem}"}"
group=$r

for ((i=0; i<$group; i++));
do
  repetition=$set$repetition
done

bash -c "echo "$repetition""

組み合わせ (nCr)

ここのやつをコピペして使おう！
- www.unix.com

Octave

Octave Online: Free Interface compatible with MATLAB
- まずは 1～100までの縦ベクトルを設定
- nCr (n=100, r=3)の組み合わせを取得、結果は行列になるのでビジュアルでわかりやすい
- １行ごとに和を求めてみる
- 和が100になるものの数を見る

> A = [1:100]';
> C = nchoosek(A,3);
> SUM = sum(C,2)
> sum(SUM == 100)
ans = 784

- 計算結果が見たいので、COMPUTEに行列をとる
- Selecting only a specific number of rows fulfilling a condition
- ちょっとよくわからないけど、これで４列目が100になっているものだけとれる

> COMPUTE = [C SUM];
> idx = ( COMPUTE(:,4)==100 );
> SUMMARIZE = A(idx,:);

結論、行列計算は最高

2017-04-20

Javaで簡単な組み合わせの総数 nCr を求めてみる

Java プログラミング

Aizu Online Judgeをやっていて、求められんかな？と思ったので。
速さとかは遅いと思う。

Java
Ruby
- 実働してるやつ
- ソースコード

Java

実働してるやつ

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

参考

stackoverflow.com

ソースコード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class prog {

    public static void main(String[] args) {

        // nCr : n=[1,2,3,4,5],r=3 で試してみる
        ArrayList<Integer> n1 = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        //getCombination(n1,3);

        // nCr : n=[1,2,3,4,5,6,7],r=4 で試してみる
        ArrayList<Integer> n2 = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7));
        getCombination(n2,4);
    }

    private static Set<ArrayList<Integer>> getCombination(ArrayList<Integer> n, Integer r) {
        Set<ArrayList<Integer>> ans = new HashSet<ArrayList<Integer>>();
        combination(n, r, ans);
        for (ArrayList<Integer> e : ans) {
            System.out.println(e.toString());
        }
        return ans;
    }

    private static void combination(ArrayList<Integer> n, Integer r, Set<ArrayList<Integer>> ans) {
        if (n.size() == r) {
            ans.add(n);
            return;
        }
        for (int i = 0; i < n.size(); i++) {
            ArrayList<Integer> N = new ArrayList<Integer>();
            N.addAll(n);
            N.remove(i);
            combination(N,r,ans);
        }
    }
}

所感

再帰関数は苦手で、自分でも若干どうして動いてるのかわからない部分がある。手続き型の設計書にしろと言われると多分無理（やめたほうがいい）。しかしポイントは以下で、与えられたサイズの配列からremoveで削除して組み合わせを作っているのだが、削除するインデックスがiで徐々にインクリメントされるのでn回試行するといろいろな組み合わせができる。

        for (int i = 0; i < n.size(); i++) {
            ArrayList<Integer> N = new ArrayList<Integer>();
            N.addAll(n);
            N.remove(i);
            combination(N,r,ans);
        }

あと、答えの型は

Set<ArrayList<Integer>>

にしておくと、勝手に配列の重複削除されるのです。nCrじゃなくてn-r+1Crを求めたい場合は、SetじゃなくてただのListにすればよいのでは。

Ruby

実働してるやつ

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

ソースコード

require 'set'

def combi(n, r, ans)
  if n.size == r
    ans.add(n)
    return
  end
  for i in 0...n.size
    arr = n.dup
    arr.delete_at(i)
    combi(arr, r, ans)
  end
end

def get_combination(n, r)
  ans = Set.new
  combi(n, r, ans)
  ans.map do |e|
    puts e.to_s
  end
  ans
end

n = [1,2,3,4,5]
get_combination(n, 3)

答え合わせはこのへんで
組合せ - 高精度計算サイト