寻找组合

Question

我想编写一个函数来计算7元组中数字1到7的所有组合，但是每个数字在每个元组中只能出现一次。

到目前为止，我已经找到了这种方法，但是它还会返回每个元组中多次出现相同编号的组合。我不太确定如何删除具有相同编号的多次出现的元组。

  a = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7], 
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7]]

目标结果示例（所有有效组合都应在此处）：

  [(1,2,3,4,5,6,7),(2,1,3,4,5,6,7),(2,3,1,4,5,6,7),...]

Answer 1

您可以使用列表差异(\\)的Data.List。

perms = [ (a,b,c,d,e,f,g) | a <- [1..7]
                          , b <- [1..7] \\ [a]
                          , c <- [1..7] \\ [a,b]
                          , d <- [1..7] \\ [a,b,c]
                          , e <- [1..7] \\ [a,b,c,d]
                          , f <- [1..7] \\ [a,b,c,d,e]
                          , g <- [1..7] \\ [a,b,c,d,e,f] ]

这种方式b将被选择为与a，c会与a和不同b，依此类推。

Answer 2

我们可以根据kuoytfouy的答案优化代码，如下所示：

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = [1..7] \\ [a]
                         , b <- dom6,   let dom5 = dom6 \\ [b]
                         , c <- dom5,   let dom4 = dom5 \\ [c]
                         , d <- dom4,   let dom3 = dom4 \\ [d] 
                         , e <- dom3,   let dom2 = dom3 \\ [e] 
                         , f <- dom2,   let dom1 = dom2 \\ [f] 
                         , g <- dom1,   let dom0 = dom1 \\ [g]  ]

并通过减少冗余计算来进一步改进它，

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = delete a [1..7]
                         , b <- dom6,   let dom5 = delete b dom6
                         , c <- dom5,   let dom4 = delete c dom5
                         , d <- dom4,   let dom3 = delete d dom4 
                         , e <- dom3,   let dom2 = delete e dom3 
                         , f <- dom2,   let [g]  = delete f dom2 ]

将元素的选择与从当前域中删除的元素组合在一起，可以为我们提供一个同时执行两项工作的功能，通常称为picks。过去曾在SO答案中使用过它，并且可以在那里找到。

也可以看看：

• picks一位猪工
• choose 在“独特选择”单子中
• 我的一个普通Lisp答案，它带有一个有效的代码，该代码实际上通过外科手术改变列表结构来缩小域列表，在递归构建的嵌套循环中将元素逐个删除；并在回程中治愈它。
  就是说，基于choose-（或等效picks-）的Haskell代码被严重怀疑效率极低（inits对于初学者，在完全被迫时为二次方）。
  每次都重新计算缩小的域，就像在此答案中一样，我们在每个时间点仅得到七个（六个，无论如何）域列表，完成后每个域都是完全垃圾可回收的- 但是，每次delete调用都会搜索其从头开始重新争论（picks发明了效率低下的问题来解决...），这再次表明总体计算是二次的，低效率的。值得深思！

Answer 3

怎么样呢？

import Data.List
list = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7],
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7], [1,2,3,4,5,6,7]\\[a,b,c,d,e,f,g]==[]]

Answer 4

我们可以在此处创建一个“帮助函数”，对于给定的列表，它会xs生成一个元组列表，其中第一个元素是我们选择的元素，第二个元素是剩余元素的列表，例如：

import Data.List(inits, tails)

pick :: [a] -> [(a, [a])]
pick ls = [(b, as ++ bs) | (as, (b:bs)) <- zip (inits ls) (tails ls)]

例如：

Prelude Data.List> pick [1..5]
[(1,[2,3,4,5]),(2,[1,3,4,5]),(3,[1,2,4,5]),(4,[1,2,3,5]),(5,[1,2,3,4])]

因此，每个项目都会从列表中选择一个元素，并返回一个列表，其中已删除该元素的列表。我们可以使用它来将该列表传递给下一个生成器。

然后，我们可以在一个do类似的代码块中使用它：

perms :: (Num a, Enum a) => [(a, a, a, a, a, a, a)]
perms = do
    (a, as) <- pick [1..7]
    (b, bs) <- pick as
    (c, cs) <- pick bs
    (d, ds) <- pick cs
    (e, es) <- pick ds
    (f, [g]) <- pick es
    return (a, b, c, d, e, f, g)

产生：

Prelude Data.List> perms
[(1,2,3,4,5,6,7),(1,2,3,4,5,7,6),(1,2,3,4,6,5,7),(1,2,3,4,6,7,5),(1,2,3,4,7,5,6),(1,2,3,4,7,6,5),(1,2,3,5,4,6,7),(1,2,3,5,4,7,6), ...