生成列表的所有排列，包括不同大小和重复元素

Question

我想创建函数genAllSize ::[a] -> [[a]]，它接收一个列表l并生成按大小排序的所有列表，可以使用列表l的元素构建;即

> genAllSize [2,4,8] 
[[],[2],[4],[8],[2,2],[4,2],[8,2],[2,4],[4,4],[8,4],[2,8],[4,8],[8,8],[2,2,2],[4,2,2],[8,2,2], ...

你会怎么做？我想出了一个使用Data.List排列的解决方案，但我不想使用它。

Answer 1

• 给定输入列表xs，以非确定性方式选择该前缀
• 对于前缀中的每个元素，以非确定性方式将其替换为xs的任何元素

结果：

> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[[],[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]

Answer 2

其他答案似乎有点复杂。我这样做：

> [0..] >>= flip replicateM "abc"
["","a","b","c","aa","ab","ac","ba","bb","bc","ca","cb","cc","aaa","aab",...

Answer 3

嗯，我想你需要一个懒惰的无限循环子序列表。一种天真的方式可能就像

Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[[],[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]

Answer 4

一个简单而高效的选择：

genAllSize [] = [[]]
genAllSize [a] = iterate (a:) []
genAllSize xs =
  [] : [x:q|q<-genAllSize xs,x<-xs]

（感谢Will Ness的一个小但非常好的简化。）

该解决方案利用了以下事实：有效的解决方案列表为空或者参数列表的元素集中在较短的有效解决方案列表上。与Daniel Wagner的解决方案不同，这个解决方案并不依赖于计算。我的测试表明它在典型条件下表现非常好。

为什么我们需要一个单元素列表的特殊情况？一般情况下执行情况非常糟糕，因为它一遍又一遍地映射在同一个列表中，没有对数减速。

但是，对genAllSizes的调用与同样的论点有什么关系呢？保存结果以增加共享不是更好吗？

genAllSize [] = [[]]
genAllSize xs = p
  where
    p = [] : [x:q|q<-p,x<-xs]

实际上，在具有无限恒定时间内存的理论机器上，这是最佳的：在每个缺点的最坏情况下O（1）时间走列表。在实践中，如果能够实现和保留大量条目，那将是一个好主意。否则，就会出现问题：大多数列表条目将无限期保留，从而大大增加了内存驻留时间以及垃圾收集器需要完成的工作量。上面的非粗体共享版本仍然提供每个缺点的摊销O（1）时间，但它需要非常少的内存（对数而不是线性）。

Examples

genAllSize "ab" =
 ["","a","b","aa","ba"
 ,"ab","bb","aaa","baa"
 ,"aba","bba","aab","bab"
 ,"abb","bbb","aaaa",...]

genAllSize "abc" =
  ["","a","b","c","aa","ba"
  ,"ca","ab","bb","cb","ac"
  ,"bc","cc","aaa","baa"
  ,"caa","aba","bba","cba"
  ,"aca",...]

An explicit option

您还可以使用两个累加器：

genAllSize [] = [[]]
genAllSize [a] = iterate (a:) []
genAllSize (x:xs) = go ([], []) where
  go (curr, remain) = curr : go (step curr remain)
  step [] [] = ([x], [xs])
  step (_:ls) ((r:rs):rss) =
    (r:ls, rs:rss)
  step (_:ls) ([] : rs) =
    (x : ls', xs : rs')
    where
      !(ls', rs') = step ls rs

此版本会跟踪当前“单词”以及每个位置中剩余的可用“字母”。一般来说，性能似乎相当，但在内存驻留方面要好一些。这也很难理解！

Answer 5

这会在每个长度内以不同的顺序生成元素，但它符合问题文本的定义。更改顺序很简单 - 您必须将<*>替换为您自己制作的稍微不同的运算符。

import Control.Applicative
import Control.Monad

rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure

extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin

genAllSize [] = []
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
  where extensions = singletonBranchExtensions xs
        initialBranches = pure empty