Javaで簡単な組み合わせの総数 nCr を求めてみる
Aizu Online Judgeをやっていて、求められんかな?と思ったので。
速さとかは遅いと思う。
Java
実働してるやつ
ソースコード
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
実働してるやつ
ソースコード
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)
答え合わせはこのへんで
組合せ - 高精度計算サイト
Monger + mLab + ClojureでMongoDBに触る
MongoDBはいわゆるNoSQLで、きっちり行と列を定めなければいけないRDBと違い、JSONをそのままぶっこめる。
今趣味で触っているプログラムに使おうと思い、Mongerをクライアントライブラリとして使用してみた。
準備編
Monger
ClojureのMongoDBクライアント側ライブラリ。使いはじめは以下のページから:
Monger, a Clojure MongoDB client: Connecting to MongoDB | MongoDB library for Clojure
project.cljに以下を追加するだけ
[com.novemberain/monger "3.1.0"]
mLab
MongoDBをクラウドで提供しているPaaS、今見たらTOYOTAも使ってるようだ。無料枠がある。
www.mlab.com
HerokuのAdd-onからmLabを使う
Herokuの側でAdd-onを追加したら、Herokuの環境変数MONGODB_URIに全ての認証情報が入っている。
うーん、これを使用してやればもっと簡単にできたな。
mLabのダッシュボードに入ると、以下のような情報がもらえる
Database: heroku_xxxxxxxx
To connect using the mongo shell:
mongo ds12345.mlab.com:12345/heroku_xxxxxxxx -u-p
To connect using a driver via the standard MongoDB URI (what's this?):
mongodb://: @ds12345.mlab.com:12345/heroku_xxxxxxxx
mLabでMongoDBのユーザーを作成する
自動作成する接続情報とは別にユーザーを作ることも出来る。
mLabの管理ポータルにログインする
- アカウントのページからデプロイのページへ(動きが正しければ、ユーザーを追加するためのデータベースに遷移するはず)
- 「ユーザー」タブをクリック
- 「データベースユーザーを追加」をクリック、新しいユーザーを追加する
- 追加したら以下のコマンドでリモートのMongoDBにログインできることを確認する
mongo ds12345.mlab.com:12345/heroku_xxxxxxxx -u <dbuser> -p<dbpassword>
コード片
これでやっと接続できる、わたしはとりあえず環境変数にいろいろ情報を与えて使ってみた。
- mg/connect だと、ホスト名とポートをハッシュマップで渡すようだ
- mg/connect-with-credentials だと、サーバ名は文字列にしないとだめなようだ
- mg/connect-via-uri だと、環境変数MONGODB_URIが使えるのだと思う
- let [db (or (System/getenv "DB_NAME") "")] とやると、環境変数から文字列が取れなかった時に空文字を入れられる
- Rubyにおけるnilガードみたいなやつですね
- とりあえずこれでJavaでいうところのConnectionがとれる
(ns sample (:gen-class :main false) (:require [clojure.string :as str] [monger.core :as mg] [monger.credentials :as mcred])) (defn mongodb [] (let [db (or (System/getenv "DB_NAME") "") user (or (System/getenv "DB_USER") "") pass (or (System/getenv "DB_PASS") "") host (or (System/getenv "DB_HOST") "127.0.0.1") port (Integer/parseInt (or (System/getenv "DB_PORT") "27017"))] (if (or (str/blank? user) (str/blank? pass)) ;; ユーザーやパスワードが設定されてないので開発環境 (mg/connect {:host host :port port}) ;; 本番環境 (mg/connect-with-credentials (str host ":" port) (mcred/create user db pass)) )))
結局接続するだけで今日は終わってしまった。レコードを作りたかったのだが。
leiningenで作るuberjarがmavenでできたらいいと思ったら出来なかった話
Leiningenでuberjarを作る
Clojureの日本語ガイドにあるように -> Part7: どのようにして Heroku へデプロイするか
Leiningenから lein uberjar
と打てばいわゆるFAT Jarができる。これは依存ライブラリを全て含んでいるのでJavaさえあれば実行できる。
Mavenからそれはできないか
似たようなものはできた。以下、設定したproject.clj
- 肝心な部分は
maven-shade-plugin
ManifestResourceTransformer
は Maven側でManifest.mfを書き換えて、実行するメインクラスを定めてくれるfinalName
- これを
${project.artifactId}-${project.version}-standalone
で設定すると、leiningenがデフォルトで出力するuberjarの名前になるハズ
- これを
実行は lein pom
してから mvn clojure:compile package
(defproject uber "0.1.0-SNAPSHOT" :description "FIXME: write description" :url "http://example.com/FIXME" :license {:name "Eclipse Public License" :url "http://www.eclipse.org/legal/epl-v10.html"} :uberjar-name "uber-clj.jar" :min-lein-version "2.5.3" :dependencies [[org.clojure/clojure "1.8.0"]] :pom-plugins [[com.theoryinpractise/clojure-maven-plugin "1.3.8" {:configuration ([:mainClass "uber.core"] [:sourceDirectories [:sourceDirectory "src/main/clj"]])}] [org.apache.maven.plugins/maven-shade-plugin "2.4.3" [:executions [:execution ([:phase "package"] [:goals [:goal "shade"]] [:configuration [:transformers [:transformer {:implementation "org.apache.maven.plugins.shade.resource.ApacheLicenseResourceTransformer"}] [:transformer {:implementation "org.apache.maven.plugins.shade.resource.ApacheNoticeResourceTransformer"}] [:transformer {:implementation "org.apache.maven.plugins.shade.resource.ManifestResourceTransformer"} [:mainClass "uber.core"]] ] ;[:finalName "${project.artifactId}-${project.version}-standalone"] [:finalName "uber-clj"] [:filters [:filter [:includes [:include "**/*.js"] [:include "**/*.class"] [:include "**/*.xml"]]]]])]]]] :source-paths ["src/main/clj"] :test-paths ["src/test/clj"] :resource-paths ["resources"] :profiles {:dev {:env {:dev true }} :uberjar {:aot :all :main uber.core}})
動かない理由
ただし、この方法で作ったjarは動かない。それにはどうやらClojureのAOTコンパイルが関係しているらしい。
ClojureのAOTコンパイルは、タイムスタンプによってAOTコンパイル済みか判定する。maven-shade-pluginはこれをおかしくさせてしまうようだ。 むーん、maven-shade-pluginにプルリクする?
追記
簡単なスクリプト程度だと、Mavenから動かしても動くバイナリができるようだ。ringなどのライブラリを混ぜると動かない感じになる。