2

我有一个 x 元素列表，我希望从中获得所有可能的唯一 n 元组。

所以我基本上正在寻找一个实现

nub . map (take n) . permutations

这不会不必要地创建重复项。

对我来说，这看起来像是一个很有可能已经在某个地方定义的函数。

是这样吗？

4

4 回答 4

1

你的意思是这样的吗？

import Data.List (permutations)

choose n list = concatMap permutations $ choose' list [] where
  choose' []     r = if length r == n then [r] else []
  choose' (x:xs) r | length r == n = [r]
                   | otherwise     = choose' xs (x:r) 
                                  ++ choose' xs r

输出：

*Main> choose 2 [0..5]
[[1,0],[0,1],[2,0],[0,2],[3,0],[0,3],[4,0],[0,4],[5,0],[0,5],[2,1]
,[1,2],[3,1],[1,3],[4,1],[1,4],[5,1],[1,5],[3,2],[2,3],[4,2],[2,4]
,[5,2],[2,5],[4,3],[3,4],[5,3],[3,5],[5,4],[4,5]]
于 2013-08-08T14:07:01.100 回答
0

Hayoo is very helpful for finding functions. With this query, I found the permutation package, which seems it might do what you want, although I haven't examined the implementation in detail.

But it might be simpler to use one of the solutions discussed here on Stack Overflow. A search turned up some relevant posts. You might look at this discussion of the implementation of the permutations function in Data.List, and modify it to meet your needs.

于 2013-08-08T11:24:18.767 回答
0

您可以使用Math.Combinatorics.Multiset( cabal install multiset-comb)，即使输入列表中有重复项，也会避免输出列表中出现重复项：

import Math.Combinatorics.Multiset  (fromList, kSubsets, permutations)

permute :: Ord a => Int -> [a] -> [[a]]
permute n = concatMap permutations . kSubsets n . fromList

main = print $ permute 2 [1, 1, 2, 3]

产生：

[[2,3],[3,2],[1,3],[3,1],[1,2],[2,1],[1,1]]
于 2013-08-18T15:14:17.180 回答
0

由于您已经要求元组，因此这是一个利用 list 是应用函子这一事实的解决方案：

Prelude> let list = [0..4]
Prelude> import Control.Applicative
Prelude Control.Applicative> (,) <$> list <*> list
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),...
Prelude Control.Applicative> (,,) <$> list <*> list <*> list
[(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,0,4),(0,1,0),(0,1,1),...

但是，由于根据定义，不同元组的元组是不同的类型，因此不可能编写一个通用函数来根据某个n参数产生不同元组的结果。

尽管我必须注意，这可以通过引入类型类和表示您想要支持的元组的数量的类型级自然数的实例来使用一些高级类型级编程技术来解决，但我确信这将是一个矫枉过正. 此外，使用自然类型也是多余的，因为所有需要的信息都可以从结果类型中确定，所以你想要支持的所有元组的简单类型类和实例就足够了。

于 2013-08-08T13:32:11.173 回答