计算n元笛卡儿积 [英] Calculate n-ary Cartesian Product
问题描述
permute :: [a] - > [a] - > [[a]]
permute xs ys = [[x,y] | x< -xs,y< - ys]
例子> permute [1,2] [3,4] == [[1,3],[1,4],[2,3],[2,4]]
如何扩展排列,以便不使用两个列表,而是使用列表的列表(长度为n)并返回列表的列表(长度为n)
permute :: [[a]] - > [[a]]
示例> permute [[1,2],[3,4],[5,6]]
== [[1,3,5],[1,3,6],[1,4,5] ,[1,4,6]] --etc
Hoogle上找不到任何相关内容..唯一匹配签名的函数是 transpose
,它不会产生所需的输出。
编辑:我认为这个2列表版本实质上是笛卡尔产品,但我无法换行我的头脑是执行 n-ary Cartesian产品。任何指针?
Prelude>序列[[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[ 1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
Given two lists, I can produce a list of all permutations the Cartesian Product of these two lists:
permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]
Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]
How do I extend permute so that instead of taking two lists, it takes a list (length n) of lists and returns a list of lists (length n)
permute :: [[a]] -> [[a]]
Example> permute [ [1,2], [3,4], [5,6] ]
== [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc
I couldn't find anything relevant on Hoogle.. the only function matching the signature was transpose
, which doesn't produce the desired output.
Edit: I think the 2-list version of this is essentially the Cartesian Product, but I can't wrap my head around implementing the n-ary Cartesian Product. Any pointers?
Prelude> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
这篇关于计算n元笛卡儿积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!