Rust で bit 全探索

bit 全探索とは

bit 全探索は，全探索の一つで組み合わせを列挙するような用途に使用できます．

例えば { A, B, C, D } の文字列の部分集合を全探索するようなケースを考えます．

これは，二進数で，0000 ~ 1111 までの数値を考え，各桁のbit を { A, B, C, D } と対応付けるとすべてのパターンを探索できるといった考え方です．

すなわち，{ A, B, C, D } からなるすべての部分集合を求めるには，0 ~ 31 (0 <= i < (1«4)) まで数え上げれば良いことになります．

0000 => {} 0001 => { A } 0010 => { B } 0011 => { A, B } 0100 => { C } 0101 => { A, C } ... .. . 1111 => { A, B, C, D }

Rustでbit全探索の実装

以下に実装例を載せます．

fn main() {

    let list = vec!["A", "B", "C", "D"];
    let n = list.len() as i32;

    for bit in 0..(1 << n) {
        let sub_list = (0..n)
            .filter(|x| (bit & (1 << x)) != 0)
            .map(|x| list[x as usize]);

        // 表示
        sub_list.for_each(|x| {
            print!("{} ", x);
        });
        println!("");
    }
}

まず，以下の部分で 0 ~ 31 までのループを実装しています．

fn main() {

    // 0 ~ 1<<4 までのループ
    for bit in 0..(1 << n) {
    }
}

次に以下の箇所で，bit 列のどのbit が 1 にっているか (0 じゃないか) を確認しています． filter と map を使って以下のようにスッキリかけます．

   let sub_list = (0..n)
       .filter(|x| (bit & (1 << x)) != 0)
       .map(|x| list[x as usize]);

これを実行すると以下のような結果が得られ，全探索出来てそうなことがわかります．

A B A B C A C B C A B C D A D B D A B D C D A C D B C D A B C D

まとめ

今回は，Rust でbit全探索の実装方法をまとめました．考え方はシンプルですが，しらないと思いつかない or 自力で頑張って実装してしましそうなのでこういうパターンを覚えて速く問題が解けるように精進していきます．

参考

こんにちは、 @kz_morita です。今回は、自転車本と言われている「実践Rust入門言語仕様から開発手法まで」を読んだのでその感想を書いていこうと思います。実践Rust入門言語仕様から開発手法まで目次目次は以下のような感じです。第1章 Rustの特徴第2章はじめてのRustプログラム第3章クイックツアー第4章プリミティブ型第5章ユーザー定義型第6章基本構文第7章所有権システム第8章トレイトとポリモーフィズム第9章パーサを作る第10章パッケージを作る第11章 Webアプリケーション・データベース接続第12章 FFI 最初に、環境の構築と簡単なプログラムを紹介して、次に基本的な文法などから、所有権・トレイト・ライフタイムなどのRust のコアな部分までの解説があります。最後に、パーサ、Webアプリケーション、FFIという実践的な内容に触れるといった順番で書かれていました。感想などこの書籍では、最初にRustの起源から始まり、実用的なアプリケーションの例まで一通り記されていました。最初に Rust を触ったときに何か Swift に似ていると感じたのですが、Rust 開発者の Hoare 氏が Apple でSwift を開発しているということをこの書籍で知って、なるほどなぁと思ったのが印象的でした。そして書籍全体の中でもなんといっても一番面白かったのは、7章と8章です。 Rustの醍醐味である、所有権システムの仕組みはやはり魅力的に感じました。コンパイラが、メモリ安全性を担保するという思想はとても魅力的だし、それを実現する仕組みも本当にすごいなと感じました。はじめはむずかしいなと感じたのですが、前職で C++ を書いてたおかげでなんとか理解できた気がしてます。（ムーブセマンティクスとかあったので）所有権に関しては、以下の記事でもまとめてありますので、よかったら見てみてください。 Rustの所有権についてライフタイムについても、以下の記事でまとめました。 Rustのライフタイムについてそして、その次の parser を作る以降の章では、実際にコードの作り方や Rust の作法みたいなところを学ぶことができたのがとても良かったです。書いていて驚いたのは、cargo を始めとするエコシステムが整っているのは非常によいなぁということと、コンパイルエラーのメッセージがとても丁寧でわかりやすいということでした。エコシステムに関しては、インストールはコマンド一発ですし、Rust自体のバージョンアップも rustup で一発でできたり、cargo で便利な crate が簡単に使えるところはさすがだなぁと思いました。

こんにちは、 @kz_morita です。今回は、アルゴリズムの評価軸である計算量、そしてよく使われるオーダー記法についてまとめていきます。アルゴリズムとは？アルゴリズムというワードはよく聞くことが多いと思いますが、以下のように定義されていることが多いようです。アルゴリズムとは、ある問題を解くのに計算機などで機械的に解ける有限個の命令からなるプログラムであり、問題のいずれの入力に対しても、有限時間で正しい解を出して停止するものである要は、問題を解くために、普通のプログラムのように任意の数の命令でかけて、無限ループしたり間違った答えを出さないものという感じの定義になります。よく例に出されるのが、任意の要素を持つリストをソートするといったアルゴリズムがあると思います。上記の定義に照らし合わせると、どんなリストを与えられても、有限個の命令で、(理論上) 有限時間で期待したソート順を返すのが、ソーティングアルゴリズムということが言えそうです。以下のようなソーティングアルゴリズムを一度は聞いたことがあるのではないでしょうか？バブルソートマージソートクイックソート etc… アルゴリズムの評価としての計算量上記でアルゴリズムとはどんなものかを述べましたが、実際にプログラムを書くときには数種類のアルゴリズムからひとつを選んで実装するということになると思います。(ソーティングなどは、ライブラリの物を使うとは思いますが) そのときに、アルゴリズムの評価軸として用いられるのが計算量です。アルゴリズムが任意の入力に対して正しい答えをだすという前提の上で、アルゴリズムを比較したいとなったときには、アルゴリズムの計算時間が少ない方が優れたアルゴリズムであると言えます。もちろん、実際の計算時間は実行されるハードウェアの影響などを受けるので、抽象化して単純化した指標が計算量となります。アルゴリズムの計算量は一般的に、入力データ数に比例することが多いです。そのためデータ数 $n$ を用い、計算量は $n$ の関数として表現することができます。ここでは以下のように表します。 $$ 計算量 = T(n) $$ 具体例として、入力データ数と同じ回数だけの計算回数がかかるアルゴリズムがあるとします。 $n = 100$ の時に計算回数が 100 回といった具合です。その時の計算量は $$ T(n) = n $$ とあらわすことができそうです。入力データ数の 2 乗に比例するのであれば、 $$ T(n) = n^2 $$ のように表すことができます。他にも以下のように様々なケースが考えらるでしょう。 $$ T(n) = 5n^3 + 2n + 100 $$

Rust で bit 全探索

bit 全探索とは

Rustでbit全探索の実装

まとめ

参考

関連記事