[erlang-questions] How to understanding recursive inside comprehension lists?

[Jesper Louis Andersen]

On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <
okaprinarjaya@REDACTED> wrote:

> Hi,
>
> Now I read Joe's book titled Programming Erlang 2nd Edition. I practice
> some functions such as for/3, quicksort/1, pythag/1, and perms/1, and
> perms/1 is the function that hard to understand.
>
> I understand comprehension lists, I fully understand for/3, I fully
> understand quicksort/1, pythag/1. But it's really hard for me to understand
> perms/1. Please teach me how to read and understand this perms/1 function.
>
> perms([]) -> [[]];
> perms(List) -> [ [H|T] || H <- List, T <- perms(List--[H]) ].
>
>
Note you have two generators in the comprehension. So for each generated H,
it generates all the possible T's. Also note that the T's depend on the H.
It is akin to having a for-loop within a for-loop:

for H := range(List) {
  for T := perms(List -- [H]) {
     Res := append(Res, [H|T])
  }
}

Now, to understand why this works, the argument is based on an induction
principle:

Observe that to generate a permutation, you first select something which
goes first, H, and then you need to generate a permutation out of the
remaining elements, List -- [H]. Suppose we fix H to some value in the
list. Then surely, we can generate all the permutations where H goes first,
by generating perms(List - [H]) and then attaching H to all the results:

perms(List) ->
  H = pick_among(List),
  [ [H|T] || T <- perms(List -- [H]) ].

But now note that to generate all permutations, any element could have been
picked by pick_among/1. So we need to loop over all elements in the list
one at a time, and consider what happens if that element goes first. This
is what the original code is doing.

Alternative wordings by Sverker and Fred :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20190823/cb6ba347/attachment.htm>