順列・組み合わせ（業務レベル）

[アルゴリズム]

とりあえず、数学知識なしで動く順列・組み合わせについて載せている

• Bashで計算しようとしたのだが、結論から言うと遅すぎて使えない
  • Octaveで計算すると早かったのでそっちを推奨する

• ここにも書いた
  • Javaで簡単な組み合わせの総数 nCr を求めてみる

• 業務システムに使いたい場合
  • 業務システム程度であれば、このロジックでもそんなに重くはならないと思う。早くするには動的計画法(DP)を使う必要があるだろう
  • もし、ロジックを年配の人のレビューに通さなければいけない場合、説明は諦めたほうがいいかもしれない（理解できないから）
  • レビューを行って相手が理解したようであれば、あなたはすごくいい会社に勤めていると言える
  • 動的計画法(DP) を使った組み合わせの求め方は → 動的計画法 - 組み合わせ

Java

  組み合わせ (nCr)

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);
        }
    }
}

Ruby

  組み合わせ (nCr)

• Rubyには Array クラスに、#combination メソッドが用意されているので、実は自作する必要はない

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)

Bash

  順列 (nPr)

• Generate combinations of elements with echo
  • 参考になったが、これは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)

• ここのやつをコピペして使おう！
  • Arbitrary permutation and combination script

Octave

• Octave Online
  • まずは 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,:);