タグ: アルゴリズム

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

前回と前々回のエントリーの問題を総当りで

前々回前回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。

実行開始から7時間半経過したけど未だに終わる気配がない。馬鹿正直に40人の参加希望者と10個の実験枠を組み合わせたら組み合わせは10^40通り。今回のコードでは、参加可能枠の配列を使って解空間を狭めたけれど、それでもやはり9 * 8 * 9 * 6 * 6 * 5 * 4 * 6 * 7 * 9 * 6 * 8 * 9 * 6 * 7 * 5 * 9 * 4 * 4 * 5 * 3 * 8 * 6 * 8 * 6 * 8 * 7 * 3 * 7 * 9 * 5 * 9 * 5 * 6 * 8 * 7 * 8 * 8 * 7 * 5 = 1.4271125147448316e+32通りの解がある。もっと解空間を狭めるアルゴリズムを考えるか、確率的なアルゴリズムを考えるしかないようだ。

ちなみに、7時間半走らせたところ、最適解は最大実験枠が4個で最大参加者数が12人になっている。明らかにまだまだ。

続きを読む

前回のエントリの問題を詳述

前回のエントリで、僕では解けない問題を書いてみたんだが、書き方が曖昧であまり伝っていないみたいなので、少し正確に書いてみることにした。ついでにサンプルデータも用意したから、サンプルデータでイメージしてもらえると助かる。

続きを読む

この問題はどう解けばいいんだ?

最近作ってるシステムで、どうしてもどう解いていいのかがわからなくて行き詰っていた問題があったのでpostしてみる。

作っているのは心理学実験の参加者募集システムで、問題は参加希望者を最適に実験枠に割り振るためのアルゴリズム。

問題の状況を簡単にまとめると図1のような感じ。

続きを読む

[メモ][Java][JavaScript] ユークリッドの互除法

よく使うので、ユークリッドの互除法で二つの整数の最大公約数を求める関数をメモ。

/** Java */
int gcd(int x, int y) {
    int g = Math.max(Math.abs(x), Math.abs(y));
    int l = Math.min(Math.abs(x), Math.abs(y));
    while (l != 0) l = g % (g = l);
    return g;
}
/** JavaScript */
function gcd(x, y) {
    var g = Math.max(Math.abs(x), Math.abs(y));
    var l = Math.min(Math.abs(x), Math.abs(y));
    while (l != 0) l = g % (g = l);
    return g;
}

再帰は使わない。再帰を使っていなければ、関数化しないでインラインで使うこともできて便利。大小関係がはっきりしている正整数が二つある場合、ユークリッドの互除法は本質的にはwhile (l != 0) l = g % (g = l);だけで表現できるんだね。

まずJavaで書いて、それをほぼそのままJavaScriptに移植したから、JavaScript側のコードは引数のチェックをしていない。必要な場合は整数かどうかのチェックをしておいたほうがいいと思う。

続きを読む

JavaScriptでマージソート

以前、JavaScriptでクイックソートを書いてみたことがあったが、今度はマージソートを書いてみた。

var sort = function self(list) {
    if (list.length < 2) return list;
    var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
    while (left.length && right.length)
        list.push(left[0] <= right[0] ? left.shift() : right.shift());
    return list.concat(left, right);
};

比較関数を使う場合は↓

var sort = function(list, comparer) {
    if (!comparer) comparer = function(x, y) { return x - yy - x; };
    return (function self(list) {
        if (list.length < 2) return list;
        var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
        while (left.length && right.length)
            list.push(comparer(left[0], right[0]) <>= 0 ? left.shift() : right.shift());
        return list.concat(left, right);
    })(list);
};

意外とシンプルなんだなー

[追記 (2011-06-29)]

安定ソートになっていなかったので一部ソースを修正。Thanks, id:escape_artist!

[追記 (2011-07-03)]

比較関数の定義がECMAScriptのsort関数と逆になっていたので一部修正。

JavaScriptでクイックソート

Haskellでのクイックソートを参考に、JavaScriptで単純なクイックソートを行う関数を書いた。

第一引数にはソートする配列を渡して、第二引数には比較関数を渡す。比較関数はArray.prototype.sortに渡す関数と同じ。

var sort = function(list, comparer) {
    if (!comparer) comparer = function(x, y) { return y - x; };
    return (function s(l) {
        var len = l.length;
        if (len < 2) return l;
        var x = l[0], y = l[1], lt = [], gt = [];
        for (var i = 1; i < len; y = l[++i]) (comparer(x, y) < 0 ? lt : gt).push(y);
        return s(lt).concat([x], s(gt));
    })(list);
};

ソートがこんな簡単に書けるものだと思わなかった。最近、アルゴリズム系の話に興味津々。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。