スポンサーサイト

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

F#雑記 Triangle15

Gushwellさんの記事BlUEPIXYさんの記事をみて、わらわも仲間に入れていた(「いた」というのは香川県東讃の方言で、「ください」という意味)ということでやってみました。
 
方針としては、一番下の一つの数を何か選びます。次に、下から2行目に移ります。下から2行目の最初の数を残った数から一つ選びます。次に右下の数を足した数と引いた数の2数を考えます。それぞれの場合で、その数が使われていないなら下から3行目に移ります。下から3行目の最初の数を残った数から一つ選びます。次に下の行の数列の最初の項を足した数と引いた数の2数を考えます。それぞれの場合でその数が使われていないなら、次の数(下から3行目の数列の2項目)に移ります。.....
このようにして調べていきます。
 
まず次のような関数を定義します。(行単位で数列を作る関数です。)
最初の引数madeSeqは、着目している何行目かの数列の何番目かまで操作を進めた時のこれまででの移動でできた数列の最初の何項かです。(並びは逆になります。)
2番目の引数remDifsは、上の操作で着目している行の下の行の数列のうち、これまでの移動で使われていない数列の残りの部分です。(一つの移動毎に下の行は足されるもの、引かれるものとして消費されます。)
3番目の引数remNumsは、そこまでで使われていない数の集合です。
 
> let rec makeSeq (madeSeq:list<int>) (remDifs : list<int>) (remNums :Set<int>) =
    [ if remDifs = [] then yield (List.rev madeSeq)
      else
        let lastNum = List.head madeSeq
        let cand1 =  lastNum + (List.head remDifs)
        if  Set.contains cand1 remNums then
            yield! makeSeq (cand1 :: madeSeq) (List.tail remDifs) (remNums - Set.ofList([cand1]))
        let cand2 =  lastNum - (List.head remDifs)
        if  Set.contains cand2 remNums then
            yield! makeSeq (cand2 :: madeSeq) (List.tail remDifs) (remNums - Set.ofList([cand2]))
    ] ;;
 
val makeSeq : int list -> int list -> Set<int> -> int list list
 
使用例
> makeSeq [7] [4;9] (Set.ofList [1;2;3;5;6;8;10;11;12;13;14;15]);;
val it : int list list = [[7; 11; 2]; [7; 3; 12]]
 
次に行単位の処理です。次のように定義します。
第一引数のpartはそこまででできた行単位の数列の数列([[7; 11; 2]; [4; 9]; [5]]というような形です。)
第二引数のremNumsは、そこまでの処理で残っている数の集合です。
 
> let rec search (part:list<list<int>>) (remNums :Set<int>) =
    if remNums.Count = 0 then
      printfn "%A" part
    else
      for nxtLF  in remNums do //mxtLFは行の最初の項
        for candSeq in (makeSeq [nxtLF] (List.head part) (remNums - Set.ofList([nxtLF]))) do
          search (candSeq :: part) (remNums - Set.ofList candSeq) ;;
 
val search : int list list -> Set<int> -> unit
 
3行で一番下の行が1のもので実験してみます。
 
> search [[1]] (Set.ofList([2;3;4;5;6]));;
[[5; 2; 6]; [3; 4]; [1]]
[[6; 2; 5]; [4; 3]; [1]]
val it : unit = ()
 
ではn行で考えるために次の関数を定義します。
 
> let solve n =
    let allNumsList = [for i in 1 .. (n*(n+1))/2 -> i]  
    let allNumsSet  = Set.ofList allNumsList
    for i in allNumsList do
        search [[i]] (allNumsSet - Set.ofList([i]));;
 
val solve : int -> unit
 
使ってみます。
 
n = 2
> solve 2;;
[[2; 3]; [1]]
[[3; 2]; [1]]
[[1; 3]; [2]]
[[3; 1]; [2]]
val it : unit = ()
 
n = 3
> solve 3;;
[[5; 2; 6]; [3; 4]; [1]]
[[6; 2; 5]; [4; 3]; [1]]
[[4; 1; 6]; [3; 5]; [2]]
[[6; 1; 4]; [5; 3]; [2]]
[[5; 6; 2]; [1; 4]; [3]]
[[4; 6; 1]; [2; 5]; [3]]
[[2; 6; 5]; [4; 1]; [3]]
[[1; 6; 4]; [5; 2]; [3]]
val it : unit = ()
 
n = 4
> solve 4;;
[[8; 1; 10; 6]; [7; 9; 4]; [2; 5]; [3]]
[[6; 1; 10; 8]; [5; 9; 2]; [4; 7]; [3]]
[[6; 10; 1; 8]; [4; 9; 7]; [5; 2]; [3]]
[[8; 10; 1; 6]; [2; 9; 5]; [7; 4]; [3]]
[[9; 3; 10; 8]; [6; 7; 2]; [1; 5]; [4]]
[[8; 3; 10; 9]; [5; 7; 1]; [2; 6]; [4]]
[[8; 10; 3; 9]; [2; 7; 6]; [5; 1]; [4]]
[[9; 10; 3; 8]; [1; 7; 5]; [6; 2]; [4]]
val it : unit = ()
 
n = 5
> solve 5;;
[[6; 14; 15; 3; 13]; [8; 1; 12; 10]; [7; 11; 2]; [4; 9]; [5]]
[[13; 3; 15; 14; 6]; [10; 12; 1; 8]; [2; 11; 7]; [9; 4]; [5]]
val it : unit = ()
 
ここから時間を計ってみます。
 
> #time;;
--> 現在タイミングはオンです
 
n = 6
> solve 6;;
リアル: 00:00:02.526、CPU: 00:00:02.515、GC gen0: 129, gen1: 2, gen2: 1
val it : unit = ()
解なしでした
 
n = 7
> solve 7;;
リアル: 00:00:36.877、CPU: 00:00:36.796、GC gen0: 1898, gen1: 4, gen2: 0
val it : unit = ()
解なしでした。
これで37秒ですから、ここぐらいが限界です。
 
全コードは次の通りです。
 
let rec makeSeq (madeSeq:list<int>) (remDifs : list<int>) (remNums :Set<int>) =
    [ if remDifs = [] then yield (List.rev madeSeq)
      else
        let lastNum = List.head madeSeq
        for op in [(+);(-)] do   //ここ少し修正した
          let cand = op lastNum  (List.head remDifs)
          if  Set.contains cand remNums then
            yield! makeSeq (cand :: madeSeq) (List.tail remDifs) (remNums - Set.ofList([cand])) 
    ]
 
let rec search (part:list<list<int>>) (remNums :Set<int>) =
    if remNums.Count = 0 then
      printfn "%A" part
    else
      for nxtLF  in remNums do //mxtLFは行の最初の項
        for candSeq in (makeSeq [nxtLF] (List.head part) (remNums - Set.ofList([nxtLF]))) do
          search (candSeq :: part) (remNums - Set.ofList candSeq)    
 
let solve n =
    let allNumsList = [for i in 1 .. (n*(n+1))/2 -> i]  
    let allNumsSet  = Set.ofList allNumsList
    for i in allNumsList do
        search [[i]] (allNumsSet - Set.ofList([i]))
 
 
うちのPCは自分で電源ユニットを交換した結果、異音がおさまりました。(BLUEPIXYさんアドバイスありがとうございました。)
スポンサーサイト

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

コメントの投稿

非公開コメント

No title

おおっ素晴らしいですね。v-127
私も、下からボトムアップの方がバックトラックが少ないんじゃないかとか
一応は考えたんですが、
順列を使う方が、(順列の流用もできるし)最初の数が決まれば後は楽(考えないで良い)なので、
順列を使ってやりました。
実際ウチの環境でこちらのソースを試してみたら、こちらの方が速かったです。v-218
それで、こちらのようなやり方の場合、(最近はマルチコアだし)パラレルで実行をさせるとよりいいかもしれませんね。
ウチのソースを、新しい方のPCで試してみたら、反って遅くなってしまいました。
(GCが増える)F#のバージョンのせいもあるんかな・

パラレル化

今、試しにウチでここのソースの
for i in allNumsList do
search [[i]] (allNumsSet - Set.ofList([i]))
の部分をパラレル化
Parallel.ForEach(allNumsList, fun i -> … )
を試してみたんですが、
solve 7 で、
リアル:00:00:31.444 CPU:00:00:31.075
が、
リアル:00:00:16.472 CPU:00:00:56.690
になり、ほぼ半分の実行時間(CPUの使用時間は逆に上がっている?(良くなっている、つまり2つ分動いた))
というような結果になりました。

No title

私もパラレル版を作って実験してみました。ちなみにCPUはクワッドコアです。
たしかに倍くらいのスピードになりますね。

let solveParallel n =
let allNumsArray = [|for i in 1 .. (n*(n+1))/2 -> i|]
let allNumsSet = Set.ofArray allNumsArray
Array.Parallel.iter (fun i -> search [[i]] (allNumsSet - Set.ofList([i]))) allNumsArray

n = 2
single リアル: 00:00:00.009、CPU: 00:00:00.015、GC gen0: 0, gen1: 0, gen2: 0
parrallel リアル: 00:00:00.006、CPU: 00:00:00.031、GC gen0: 0, gen1: 0, gen2: 0

n = 3
single リアル: 00:00:00.031、CPU: 00:00:00.031、GC gen0: 0, gen1: 0, gen2: 0
parrllel リアル: 00:00:00.022、CPU: 00:00:00.015、GC gen0: 1, gen1: 0, gen2: 0

n = 4
single リアル: 00:00:00.054、CPU: 00:00:00.062、GC gen0: 1, gen1: 0, gen2: 0
parrallel リアル: 00:00:00.029、CPU: 00:00:00.093、GC gen0: 1, gen1: 0, gen2: 0

n = 5
single リアル: 00:00:00.404、CPU: 00:00:00.406、GC gen0: 12, gen1: 1, gen2: 0
parrallel リアル: 00:00:00.142、CPU: 00:00:00.390、GC gen0: 13, gen1: 0, gen2: 0

n = 6
single リアル: 00:00:06.288、CPU: 00:00:06.312、GC gen0: 212, gen1: 2, gen2: 1
parrallel リアル: 00:00:02.307、CPU: 00:00:06.390、GC gen0: 212, gen1: 1, gen2: 0

n = 7 (PCが何か他ごとをやっているのか上の記事を書いた時に比べてえらく遅い)
single リアル: 00:01:32.403、CPU: 00:01:32.250、GC gen0: 3128, gen1: 10, gen2: 1
parrallel リアル: 00:00:41.884、CPU: 00:01:33.828、GC gen0: 3141, gen1: 5, gen2: 1
プロフィール

T GYOUTEN

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

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

この人とブロともになる

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