计算 n 元笛卡尔积 [英] Calculate n-ary Cartesian Product

问题描述

给定两个列表，我可以生成所有排列的列表这两个列表的笛卡尔积:

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] ]

如何扩展 permute 以便它不使用两个列表，而是使用列表的列表(长度 n)并返回列表的列表(长度 n)

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

我在 Hoogle 上找不到任何相关内容.唯一匹配签名的函数是 transpose，它不会产生所需的输出.

I couldn't find anything relevant on Hoogle.. the only function matching the signature was transpose, which doesn't produce the desired output.

我认为这个 2-list 版本本质上是 笛卡尔积，但是我无法专注于实施 n-ary 笛卡尔积.有什么指点吗?

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屋！