スポンサーサイト

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

F#雑記 combinationもどき

これまででつくったビット演算がらみの関数を利用して組み合わせを求める関数を作ってみました。
次のような動きをします。
 
>  getComb [|'a'.. 'd'|] (fun c -> c = 2);;
val it : seq<char list> =
  seq [['a'; 'b']; ['a'; 'c']; ['a'; 'd']; ['b'; 'c']; ...]
 
>  getComb [|'a'.. 'd'|] (fun c -> 0 <=c && c <= 4);;
val it : seq<char list> =
  seq[['a'; 'b'; 'c'; 'd']; ['a'; 'b'; 'c']; ['a'; 'b'; 'd']; ['a'; 'b']; ...]
 
> getComb [|'a'.. 'd'|] (fun c -> c % 2 = 0);;
val it : seq<char list> =
  seq [['a'; 'b'; 'c'; 'd']; ['a'; 'b']; ['a'; 'c']; ['a'; 'd']; ...]
 
getCombは配列から何個か取り出す方法をシークエンスにして返す関数です。
配列の要素数をm個とすると0からmまでのうち、2番目の関数を適用してtrueになるものだけが返ります。
(ただ配列の大きさは32までは無理で、24,5あたりでout of memoryエラーが出始めます)
 
方法は前回と同じで、ビットのマスクを作りこれに対応する配列の要素をリストとして作り出しています。
 
ではコードです。
 
> let bitCountUint32 (n : uint32) =
    n
    |> (fun x -> x - ((x>>>1) &&& 0b01010101010101010101010101010101u))
    |> (fun x -> (x &&& 0b00110011001100110011001100110011u) + ((x &&& 0b11001100110011001100110011001100u) >>> 2))
    |> (fun x -> (x &&& 0b00001111000011110000111100001111u) + ((x &&& 0b11110000111100001111000011110000u) >>> 4))
    |> (fun x -> (x &&& 0b00000000111111110000000011111111u) + ((x &&& 0b11111111000000001111111100000000u) >>> 8))
    |> (fun x -> (x &&& 0b00000000000000001111111111111111u) + (x >>> 16))
 
let inline isLowestBitOnUint32 (n: uint32)= 
    (n &&& 1u)  = 1u  
 
let pow2MaxMinus1 (m: int32) = 
    let rec subPow curM res = 
        if curM = m then res 
        else subPow (curM+1) (res <<< 1 ||| 1u) 
    subPow 1 1u 
 
/////////ここまでは前回までに定義したもの
/////////ここから先は今回定義したもの
 
let getUnmaskedVals (arr:array<'a>) (n:uint32)  =
    let rec getUVsub m index res =
        if index = Array.length arr then
            res
        else
           if isLowestBitOnUint32 m then
                getUVsub (m >>> 1) (index + 1) (arr.[index]::res)
           else
                getUVsub (m >>> 1) (index + 1) res          
    getUVsub n 0 []
   
 
let getComb (arr:array<'a>) f =
    let dim = Array.length arr
    let revArr = Array.rev arr
    if dim > 25 then failwith "配列の次数は25までです"
    seq[(int64)(pow2MaxMinus1 dim) .. -1L .. 0L]
    |> Seq.map(fun k  -> (uint32)k) 
    |> Seq.filter (fun k -> f ((int)(bitCountUint32 k)) = true)
    |> Seq.map (fun k -> getUnmaskedVals revArr k);;
 
val bitCountUint32 : uint32 -> uint32
val inline isLowestBitOnUint32 : uint32 -> bool
val pow2MaxMinus1 : int32 -> uint32
val getUnmaskedVals : 'a array -> uint32 -> 'a list
val getComb : 'a array -> (int -> bool) -> seq<'a list>
 
 
(使用例)
 
> Seq.take 10 (getComb [|1.. 20|] (fun c -> c = 2));;
val it : seq<int list> = seq [[1; 2]; [1; 3]; [1; 4]; [1; 5]; ...]
 
> Seq.take 10 (getComb [|1.. 20|] (fun c -> c = 14))
|> Seq.iter(fun x -> printfn "%A" x);;
 
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 15]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 16]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 17]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 18]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 19]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 20]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 15]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 16]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 17]
val it : unit = ()
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

No title

>配列の大きさは32までは無理で、24,5あたりでout of memoryエラー
実行速度はともかくとして、
> seq[(int64)(pow2MaxMinus1 dim) .. -1L .. 0L]

seq {(int64)(pow2MaxMinus1 dim) .. -1L .. 0L}
にすれば、実行可能だと思います。
(いつもseq [ ] で書いているのが気にはなってたんですが、こういう部分で違いが・・・)

No title

こんなところでシークエンスが最後まで評価されてしまってますね。
もっと注意しなければ。
最速のcombination作成法とはどんなもんなんでしょうかね。

組み合わせ作成手順

>最速のcombination作成法とはどんなもんなんでしょうかね
http://blog.livedoor.jp/p-1956050/archives/51735148.html
と大して変わらない手順になるんじゃないでしょうか。
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

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