ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

[rust][離散最適化] パス列挙アルゴリズム

組込Deep Learningで、量子化された状態での学習というのは離散最適化問題なのでは?と思い立ち組合せ最適化 第2版を読み始めました。最初のアルゴリズムとして、パス列挙アルゴリズム(path enumeration algorithm)が載っていたので、これまた勉強を始めたRustで書いてみました。

やりたいことは、nが与えられたときその順列を列挙したい。n = 2だったら(2,1)と(1,2)、n=3なら(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)の6つ。ちょうとn!の組み合わせが欲しい出力です。本の一番最初にでてきたアルゴリズムなので、これを最初の一歩として、この後に再帰バージョンなどがでてくるのでは無いかと思ってます。

本のアルゴリズムをそのまま実装してみた結果がこうなりました。明らかにエラー処理を握りつぶしにいってますが、初めてのRustプログラムなので勘弁してください。アルゴリズム的にmin()が失敗することはありえないのでpanicで落ちても良いですね。

use std::collections::HashSet;

type Pi = Vec<u32>;

fn calc_k(pi:&Pi, i:u32, n:u32) -> u32 {

    // pi(i) + 1 .. n
    let g0: HashSet<u32> = (pi[i as usize - 1] + 1.. n + 2).collect();
    // pi(1) .. pi(i-1)
    let g1: HashSet<u32> = pi[0 .. (i - 1) as usize].to_vec().into_iter().collect();    

    let diff = &g0 - &g1;
    match diff.into_iter().min() {
        Some(k) => k,
        _ => 0
    }   
}

fn enumlation(n: u32) -> Vec<Pi> {
    let mut pi : Pi = (1..n+1).collect();
    let mut i = n - 1;  
    let mut result :  Vec<Vec<u32>> = Vec::new();
    let mut k = calc_k(&pi, i , n);

    result.push(pi.clone());

    // k == n + 1, i == 1
    while k != n + 1 || i != 1  {
        if k <= n {
            pi[i as usize - 1] = k;
            if i == n {
                result.push(pi.clone());
            }
            if i < n  {
                pi[i as usize] = 0;
                i = i + 1;
            }
        }
        if k == n + 1 {
            i = i - 1;
        }
        k = calc_k(&pi, i , n);
    }    
    result   
}

#[test]
fn test_k() {
    assert_eq!(calc_k(&vec![1,2,3,4,5,6], 5, 6), 6);
    assert_eq!(calc_k(&vec![1,2,3,4,6,5], 5, 6), 7);
    assert_eq!(calc_k(&vec![1,2,3,4,6,5], 4, 6), 5);
}

fn main() {
    let ret = enumlation(4);
    println!("len = {}", ret.len());
    println!("{:?}", ret);
}

はてなダイアリーではrustの色分けができないのかな。ぐぬぬ

n = 4で動かしてみるとちゃんと動いてそう。

len = 24
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

rustで標準で無いの?

unstableだけど、この辺が使えそう。
https://doc.rust-lang.org/1.1.0/std/slice/struct.Permutations.html

Qiitaに別の実装を見つけました。
https://qiita.com/aflc/items/d6fa617910092377e022

アルゴリズムをさっと動かして試してみたいって時には、Listに入れておけば配列としても集合としても扱えるし順列も簡単にとりだせるGauche便利。一方実務でやる場合は、Rustの制約のおかげでテストの工数がぐっと減らせそうで、かつ最初にアルゴリズム整理しないといけないので設計に時間がかかるが最初から完成度が高いコードができそうな気がしました。(小学生並)