如何创建 haskell 排列

发布于 2024-11-11 11:16:53 字数 491 浏览 3 评论 0原文

我想要做的是创建一个函数，给定一定的长度创建 True/False

ex 的所有可能的组合/排列。 getPerm 2 应返回 [True,True,True,False,False,True,False,False]

getTrue 0 = []
getTrue size = (True:(getTrue (size-1)))++(True:(getFalse (size-1)))
getFalse 0 = []
getFalse size =(False:(getTrue (size-1)))++(False:(getFalse (size-1)))
getPerm 0 = []
getPerm size= (getTrue size)++(getFalse size)

我无法正确理解......我是函数式编程新手，所以请只使用基本的东西而不是奇怪的东西..尝试使代码尽可能简单，因为我对 haskell 还不太了解

原文

What i want to do is create a function that given a certain length creates all possible combinations/permutations of True/False

ex. getPerm 2 shall return [True,True,True,False,False,True,False,False]

getTrue 0 = []
getTrue size = (True:(getTrue (size-1)))++(True:(getFalse (size-1)))
getFalse 0 = []
getFalse size =(False:(getTrue (size-1)))++(False:(getFalse (size-1)))
getPerm 0 = []
getPerm size= (getTrue size)++(getFalse size)

I can't get it right..im new to functional programming so please only use basic stuff and not weird things..try to make code as simple as possible cuz i don't know a lot about haskell yet

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

赤濁 2024-11-18 11:16:53

getPerm n = concat $ replicateM n [True, False]

虽然它可能被称为“奇怪的事情”，但它并不太难。 [True, False] 表示列表 monad 中的不确定性选择。 replicateM 生成这些选择的 n 次重复的不确定列表。由于您希望将它们全部放在一个列表中，因此我们将它们连接起来以获得最终结果。

getPerm n = concat $ replicateM n [True, False]

While it might qualify as a "weird thing", it isn't too hard. [True, False] represents nondeterministic choice in the list monad. replicateM makes a nondeterministic list of n repetitions of these choices. Since you wanted them all in one list we concatenate to get the final result.

回复收藏 0 原文

黑寡妇 2024-11-18 11:16:53

您可以使用sequence获得结果：

getPerm = concat . sequence . flip replicate [True,False]

如果您希望所有排列都有不同的列表，只需删除concat即可。

我只是想到了一个更基本的定义。 迭代 :: (a -> a) ->一个-> [a] 一次又一次地应用函数并返回中间值：

getPerm = concat . (iterate permute [[]] !!)

permute xs = map (True:) xs ++ map (False:) xs

所以基本上，permute 生成下一个排列，而 getPerm 只是选择所需的排列。

You get your result by using sequence:

getPerm = concat . sequence . flip replicate [True,False]

If you want to have different lists for all permutations, just drop the concat.

I just thought of a more basic definition. iterate :: (a -> a) -> a -> [a] applies a function again and again and returns the intermediate values:

getPerm = concat . (iterate permute [[]] !!)

permute xs = map (True:) xs ++ map (False:) xs

So basically, permute generates the next permutation, while getPerm just picks the permutation needed.

回复收藏 0 原文

稚然 2024-11-18 11:16:53

这是另一个观点。

getPerm n 将创建 2^n 种排列。生成这些值的另一种方法是简单地从 0 计数到 2^n-1 并将位模式编码为 True 和 False。

我更改了 getPerms 函数的类型以返回列表列表，以便更轻松地分解内容。

import Data.Bits

getPerms :: Int -> [[Bool]]
getPerms n = map (encode n) [0..2^n-1]

encode :: Int -> Int -> [Bool]
encode bitSize value = map (testBit value) [0..bitSize-1]

*Main> getPerms 2
[[False,False],[True,False],[False,True],[True,True]]

Here's another perspective.

getPerm n is going to create 2^n permutations. Another way of generating these values is simply to count from 0 to 2^n-1 and encode the bit pattern as True and False.

I've changed the type of your getPerms function to return a list of lists so that it is easier to break things apart.

import Data.Bits

getPerms :: Int -> [[Bool]]
getPerms n = map (encode n) [0..2^n-1]

encode :: Int -> Int -> [Bool]
encode bitSize value = map (testBit value) [0..bitSize-1]

*Main> getPerms 2
[[False,False],[True,False],[False,True],[True,True]]

回复收藏 0 原文

~没有更多了~