なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

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の管理ポータルにログインする

  1. アカウントのページからデプロイのページへ(動きが正しければ、ユーザーを追加するためのデータベースに遷移するはず)
  2. 「ユーザー」タブをクリック
  3. 「データベースユーザーを追加」をクリック、新しいユーザーを追加する
  4. 追加したら以下のコマンドでリモートの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
    • こいつが依存ライブラリとコンパイル済みのClojureからできたクラスファイルをjarに入れてくれる
  • ManifestResourceTransformerMaven側で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などのライブラリを混ぜると動かない感じになる。