14

パズルをプレゼントしてもらいました。横に並べられた 4 つの立方体で構成されています。各立方体の面は、4 つの色のいずれかです。

パズルを解くには、4 つの立方体の上部がすべて異なり、前面がすべて異なり、背面がすべて異なり、底がすべて異なるように、立方体の向きを変える必要があります。左右は関係ありません。

私の疑似コードの解決策は次のとおりです。

  1. 各立方体の表現を作成します。
  2. 各立方体の可能な方向をすべて取得します (それぞれに 24 あります)。
  3. 各立方体の向きの可能な組み合わせをすべて取得します。
  4. 解を満たす方向の組み合わせを見つけます。

F# でその疑似コードの実装を使用してパズルを解決しましたが、手順 3 の方法には満足していません。

let problemSpace =
    seq { for c1 in cube1Orientations do
              for c2 in cube2Orientations do
                  for c3 in cube3Orientations do
                      for c4 in cube4Orientations do
                          yield [c1; c2; c3; c4] }

上記のコードは非常に具体的で、4 つの一連の向きのデカルト積のみを計算します。n シーケンスの向きを記述する方法を考え始めました。

私が思いついた (これ以降のすべてのコードは、F# インタラクティブで正常に実行されるはずです):

// Used to just print the contents of a list.
let print = 
    Seq.fold (fun s i -> s + i.ToString()) "" >> printfn "%s"

// Computes the product of two sequences - kind of; the 2nd argument is weird.
let product (seq1:'a seq) (seq2:'a seq seq) =
    seq { for item1 in seq1 do
              for item2 in seq2 do
                  yield item1 |> Seq.singleton |> Seq.append item2 }

product 関数は次のように使用できます...

seq { yield Seq.empty }
|> product [ 'a'; 'b'; 'c' ]
|> product [ 'd'; 'e'; 'f' ]
|> product [ 'h'; 'i'; 'j' ]
|> Seq.iter print

... につながる ...

let productn (s:seq<#seq<'a>>) =
    s |> Seq.fold (fun r s -> r |> product s) (seq { yield Seq.empty })

[ [ 'a'; 'b'; 'c' ]
  [ 'd'; 'e'; 'f' ]
  [ 'h'; 'i'; 'j' ] ]
|> productn
|> Seq.iter print

これはまさに私が望む使い方です。productn はまさに私が望む署名を持っており、機能します。

ただし、product の使用には厄介な行 seq { yield Seq.empty } が含まれており、直感に反して次のようになります。

  1. 値のシーケンス (seq<'a>)
  2. 値のシーケンスのシーケンス(seq<seq<'a>>)

2 番目の引数は正しくないようです。

その奇妙なインターフェイスはproductnによってうまく隠されていますが、それでも私を悩ませています。

n シーケンスのデカルト積を一般的に計算するための、より優れた、より直感的な方法はありますか? これを行う組み込み関数 (またはその組み合わせ) はありますか?

4

3 に答える 3

12

再帰を使用します。n 個のリストのデカルト積 {L1..LN} は、L1 の各要素をリスト {L2..LN} のデカルト積の各サブリストに追加したときに得られるリストのコレクションです。

let rec cart1 LL = 
    match LL with
    | [] -> Seq.singleton []
    | L::Ls -> seq {for x in L do for xs in cart1 Ls -> x::xs}

例：

> cart1 [[1;2];[3;4;5];[6;7]] |> Seq.toList;;
val it : int list list =
  [[1; 3; 6]; [1; 3; 7]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7]; [2; 3; 6];
   [2; 3; 7]; [2; 4; 6]; [2; 4; 7]; [2; 5; 6]; [2; 5; 7]]

[1;2] [3;4;5] と [6;7] のデカルト積は、カート [[3;4;5];[6;7]]} の各リストに追加された {1 の結合です。 {2 がカート内の各リストに追加されます [[3;4;5];[6;7]]}。これは、match ステートメントの 2 番目の句です。

于 2010-07-26T12:46:20.580 に答える
0

これは、リスト バージョンでの最初の試みです。少しはきれいにできると思います。

let rec cart nll = 
  let f0 n nll =
    match nll with
    | [] -> [[n]]
    | _ -> List.map (fun nl->n::nl) nll
  match nll with
  | [] -> []
  | h::t -> List.collect (fun n->f0 n (cart t)) h
于 2010-07-26T19:12:03.653 に答える