F #에서 n 시퀀스의 직교 곱을 어떻게 계산합니까?

Question

나는 수수께끼를 선물로 받았다. 그것은 나란히 배열 된 4 개의 큐브로 구성됩니다. 각 입방체의 얼굴은 네 가지 색상 중 하나입니다.

퍼즐을 해결하려면 큐브의 방향이 정해져 있어야 네 개의 큐브의 꼭대기가 모두 다르고 앞면이 모두 다르고 뒤가 모두 다르며 바닥이 모두 달라야합니다. 왼쪽과 오른쪽은 중요하지 않습니다.

내 의사 코드 솔루션이었다

1. 각 큐브의 표현을 만듭니다.
2. 각 큐브의 가능한 방향을 확인하십시오 (각각 24 개씩 있습니다).
3. 각 큐브 방향 의 가능한 모든 조합을 가져옵니다.
4. 솔루션을 만족하는 방향 조합 을 찾습니다.

나는 F 번호에 그 의사 코드의 구현을 사용하여 퍼즐을 해결,하지만 3 단계를 그런 식으로 satisifed 있지 않다 :

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 } 

제품 기능이

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 정확히 내가 원하는 서명 작동합니다.

그러나, 제품을 사용하는 것은 성가신 광고 서열 {수율 Seq.empty}를 포함하고,이 unintuitively 얻어

: 값 (서열 < '는 >)

의

1. 시퀀스를 시퀀스 시퀀스 을 값 (서열 SEQ < < '는 > >)

번째 인수는 보이지 않는다 (C)의 직립.

그 이상한 인터페이스는 productn에 의해 멋지게 숨겨져 있지만, 여전히 저촉하고 있습니다.

일반적으로 n 개의 시퀀스로 구성된 데카르트 곱을 더 멋지고 직관적으로 계산할 수 있습니까? 이 작업을 수행하는 내장 함수가 있습니까?

Answer 1

재귀를 사용하십시오 : 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]]}과 {2는 장바구니 [3; 4; 5]; [6; 7]]의 각 목록에 추가됩니다. 이는 match 문에서 두 번째 절입니다.

Answer 2

다음은 목록 버전에서 첫 번째 시도입니다. 나는 그것이 약간 정리 될 수 있었다라고 생각한다.

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