Erlang列表理解,排列

Question

我正在修补一本书中的排列示例.以下代码作为意图.

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

当我替换表达式时,它变为:

[ [1 | perms([2])], 
   [2 | perms([1])] ]

[ [1 | [[2 | perms([])]]], 
   [2 | [[1 | perms([])]]] ]

[ [1 | [ [2 | [[]] ] ]], 
  [2 | [ [1 | [[]] ] ]] ]

这正确评估[[1,2],[2,1]].

但是当我从列表中将基本案例更改为空列表时包含一个空列表:

perms([]) -> [];

它返回一个空列表.当我替换时,我得到了这个.

   [ [1 | [[2 | [] ]]], 
     [2 | [[1 | [] ]]] ] 

我尝试了两种表达方式,但是它们产生了相同且正确的结果.

[[1 | lists:flatten([[2 | lists:flatten([[]]) ]])], [2 | lists:flatten([[1 | lists:flatten([[]]) ]])]]
[[1 | lists:flatten([[2 | lists:flatten([]) ]])], [2 | lists:flatten([[1 | lists:flatten([]) ]])]].

所以我无法弄清楚两个表达式之间的区别.

Answer 1

此函数实现递归算法:

• 非空列表的排列是什么？对于列表中的每个元素,将列表的排列减去该元素,并将元素添加到每个这样的排列中.
• 空列表的排列是什么？只有一个:空列表本身,所以我们返回一个包含一个元素的列表,即空列表:[[]]

通过改变基础案例[]而不是返回[[]],你会说:

• 空列表的排列是什么？零排列.

然后在递归的情况下,你进入"采取......的排列"的步骤 - 但是没有排列,所以没有任何东西你可以预先添加元素.