[アルゴリズム]
とりあえず、数学知識なしで動く順列・組み合わせについて載せている
- Bashで計算しようとしたのだが、結論から言うと遅すぎて使えない
- Octaveで計算すると早かったのでそっちを推奨する
- ここにも書いた
- 業務システムに使いたい場合
- 業務システム程度であれば、このロジックでもそんなに重くはならないと思う。早くするには動的計画法(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)
- ここのやつをコピペして使おう!
Octave
- Octave Online
- まずは 1~100までの縦ベクトルを設定
- nCr (n=100, r=3)の組み合わせを取得、結果は行列になるのでビジュアルでわかりやすい
- 1行ごとに和を求めてみる
- 和が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
- ちょっとよくわからないけど、これで4列目が100になっているものだけとれる
> COMPUTE = [C SUM]; > idx = ( COMPUTE(:,4)==100 ); > SUMMARIZE = A(idx,:);