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

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]]