0

我需要以perms这种嵌套方式调用此函数：

e = [1,3,7,10, 25,50]
f = perms (perms (perms (perms (perms (perms [[]] e) e) e) e) e) e
g = [[]] ++ f -- final set of permutations 

perms :: (Eq a, Ord a) => [[a]] -> [a] -> [[a]] 
-- set [a] is a set of existing permutations and set [b] are the elements to add to [a] in all possible permutations
perms xss      [] = xss  -- no unique elements to create new permutations from
perms [xs]     ys = [xs ++ [y] | y <- ys \\ xs ]                         -- last list of xs in list xss 
perms (xs:xss) ys = [xs] ++ [ xs ++ [y] | y <- ys\\xs ] ++ perms xss ys

简而言之，我想知道是否有一个函数，比如一个花哨的使用，map with (.)或者something它可以以比以下更简洁的语法为我执行其中六个嵌套调用：

f = perms (perms (perms (perms (perms (perms [[]] e) e) e) e) e) e

我相信我可以Int在函数中添加另一个参数，perms以便通过 P(n, r) for r <- [1..6] 进行计数，但这对我来说并不感兴趣。我想知道如何在没有文字嵌套的情况下递归调用自身的同一个函数的 6 个嵌套？

但也许它归结为我的函数中递归设计的错误选择，并且需要废弃整个方法以获得更好的东西？

背景：

这是我试图解决 Graham Hutton Haskell 简介讲座中提出的倒计时游戏解决方案查找器的一部分。（我敢肯定他的解决方案更优雅）

使用 Data.List 库permutations函数不起作用，因为除了 (n=720) 6 元素排列之外，我还需要 (720) 5 元素排列、(360) 4 元素排列、(120 ) 3 元素排列 ...，(6) 1 元素排列和空集解。因为在这个游戏中，您可以随意使用随机选择的 6 个数字中的任意数量或数量。

我查看了 hackage.org 上的源代码permutations，这有点超出我的理解。所以我想我最好自己试试这个。

这是 Hutton 的解决方案，用于查找我刚刚选择查看的数字排列选择。

-- Combinatorial functions

subs :: [a] -> [[a]]
subs []     = [[]]
subs (x:xs) = yss ++ map (x:) yss
              where yss = subs xs

interleave :: a -> [a] -> [[a]]
interleave x []     = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)

perms :: [a] -> [[a]]
perms []     = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))

choices :: [a] -> [[a]]
choices = concat . map perms . subs
4

4 回答 4

4

我会使用iterate，如

iterate (flip perms e) [[]] !! 6
于 2021-05-17T13:55:01.293 回答
2

这里有一个方法：

> foldr ($) [[]] (replicate 1 $ flip perms e)
[[1],[3],[7],[10],[25],[50]]

> foldr ($) [[]] (replicate 2 $ flip perms e)
[[1],[1,3],[1,7],[1,10],[1,25],[1,50],[3],[3,1],[3,7],[3,10],[3,25],[3,50],
 [7],[7,1],[7,3],[7,10],[7,25],[7,50],[10],[10,1],[10,3],[10,7],[10,25],
 [10,50],[25],[25,1],[25,3],[25,7],[25,10],[25,50],[50,1],[50,3],[50,7],
 [50,10],[50,25]]

> foldr ($) [[]] (replicate 6 $ flip perms e)
...............

它是如何产生的？你有例如

f3 =                 perms   ( perms   ( perms  [[]]  e )  e )  e
   =                 perms' e ( perms' e ( perms' e  [[]] ))
   =                 perms' e $ perms' e $ perms' e $ [[]]
   = foldr ($) [[]] (perms' e : perms' e : perms' e : [])
   = foldr ($) [[]] (replicate 3 (perms' e))
   = foldr ($) [[]] (replicate 3 $ flip perms e)

perms' e xs = perms xs e
            = flip perms e xs
perms' e    = flip perms e
perms'      = flip perms

然后我们把它抽象3出来。

所以它或多或少只是语法。（嗯，不是真的，但足够接近）。

当然我们也可以把它perm'本身当做操作符，

f3 =                    perms   ( perms   ( perms  [[]]  e )  e )  e
   =                    perms' e ( perms' e ( perms' e  [[]] ))
   =                    e `perms'` e `perms'` e `perms'` [[]]
   = foldr perms' [[]] (e    :     e    :     e    :     [])
   = foldr (flip perms) [[]] (replicate 3 e)
   = foldl perms [[]] (replicate 3 e)

这甚至更短。

顺便说一句，最后一个foldl片段是一个罕见的例子，可以使用foldl和 not foldl'。它用于首先构建嵌套计算结构（嵌套perms调用），然后通过 Haskell 的惰性求值运行。

当我使用它($)本身时，我专注于代码的结构，它没有出现在最后一个片段中，只暗示了.

于 2021-05-17T13:00:16.047 回答
2

我想你正在寻找foldl，不是吗？

foldl perms [[]] [e,e,e,e,e,e] == perms (perms (perms (perms (perms (perms [[]] e)e)e)e)e)e

或者如果e是固定的，你也可以replicate使用

foldl perms [[]] (replicate 6 e) == perms (perms (perms (perms (perms (perms [[]] e)e)e)e)e)e

所以在你的情况下，它会像这样工作：

Prelude> take 10 $ foldl perms [[]] (replicate 6 e)
[[1],[1,3],[1,7],[1,10],[1,25],[1,50],[1,3],[1,3,7],[1,3,10],[1,3,25]]
于 2021-05-17T12:59:55.803 回答
1

使用 Data.List 库排列函数不起作用，因为除了 (n=720) 6 元素排列之外，我还需要 (720) 5 元素排列、(360) 4 元素排列、 ( 120) 3 元素排列……，(6) 1 元素排列和空集解。因为在这个游戏中，您可以随意使用随机选择的 6 个数字中的任意数量或数量。

我宁愿使用permutations然后改进它的结果，也不愿自己重新实现整个事情，尤其是因为它的permutations实现效率比我想象的要高。在这种情况下，对于一般列表很容易做到，而无需明确使用它的长度。当然，这并不能解决您的直接问题（“如何将一个函数与自身组合 N 次”），但我认为它是您真正目标的更好解决方案（“查找集合子集的排列”）。

import Control.Monad (filterM, (<=<))
import Data.List (permutations, tails)

subsets :: [a] -> [[a]]
subsets = filterM (const [False, True])

permutationsOfSubsets :: [a] -> [[a]]
permutationsOfSubsets = permutations <=< subsets

首先，我们找到输入列表的所有子集（预先设置我们将实际使用的数字），然后对于每个子集，我们尝试其所有排序。

*Main> permutationsOfSubsets [1,2,3]
[[],[3],[2],[2,3],[3,2],[1],[1,3],[3,1],[1,2],[2,1],[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
*Main> length . permutationsOfSubsets $ [1..6]
1957

观察它是否完全符合您对小列表的要求。对于完整的 6 个数字，它提供了 1957 种可能性。那是对的吗？

*Main> factorial n = product [1..n]
*Main> n `nPr` r = factorial n `div` factorial (n - r)
*Main> sum . map (6 `nPr`) $ [0..6]
1957

是的，有 1957 种方法可以从 6 个总体中选择 0 个或更多元素的有序集合。

于 2021-05-17T21:21:49.030 回答