Functional Programming in Erlang: 2.27

morelists.erl

-module(morelists).

-export([concat/1, concat_test/0, insertion_sort/1,
	 join/2, join_test/0, member/2, member_test/0,
	 merge_sort/1, perms/1, perms_test/0, quicksort/1,
	 sort_tests/0, test/0]).

join([], Y) -> Y;
join([X | Xs], Y) -> [X | join(Xs, Y)].

join_test() -> "hello" = join("hel", "lo"), ok.

concat([]) -> [];
concat([X | Xs]) -> join(X, concat(Xs)).

concat_test() ->
    "goodbye" = concat(["goo", "d", "", "by", "e"]), ok.

member(_, []) -> false;
member(X, [Y | _]) when X == Y -> true;
member(X, [_ | Ys]) -> member(X, Ys).

member_test() ->
    true = member(2, [2, 0, 0, 1]),
    false = member(20, [2, 0, 0, 1]),
    ok.

merge_sort([]) -> [];
merge_sort([X]) -> [X];
merge_sort(Xs) ->
    {L, R} = split(Xs, [], [], left),
    merge(merge_sort(L), merge_sort(R)).

split([], L, R, _) -> {L, R};
split([X | Xs], L, R, left) ->
    split(Xs, [X | L], R, right);
split([X | Xs], L, R, right) ->
    split(Xs, L, [X | R], left).

merge(L, []) -> L;
merge([], R) -> R;
merge([L | Ls], [R | Rs]) when L < R ->
    [L | merge(Ls, [R | Rs])];
merge(L, [R | Rs]) -> [R | merge(L, Rs)].

quicksort([]) -> [];
quicksort([X | Xs]) ->
    {LT, GTE} = split_by_pivot(X, Xs, [], []),
    join(quicksort(LT), [X | quicksort(GTE)]).

split_by_pivot(_, [], LT, GTE) -> {LT, GTE};
split_by_pivot(P, [X | Xs], LT, GTE) when X < P ->
    split_by_pivot(P, Xs, [X | LT], GTE);
split_by_pivot(P, [X | Xs], LT, GTE) ->
    split_by_pivot(P, Xs, LT, [X | GTE]).

insertion_sort([]) -> [];
insertion_sort([X | Xs]) ->
    insert_in_place(X, insertion_sort(Xs)).

insert_in_place(N, []) -> [N];
insert_in_place(N, [X | Xs]) when N < X -> [N, X | Xs];
insert_in_place(N, [X | Xs]) ->
    [X | insert_in_place(N, Xs)].

sort_tests() ->
    [0, 1, 2, 3, 4, 4, 5, 7] = insertion_sort([4, 2, 5, 7,
					       3, 1, 0, 4]),
    [0, 1, 2, 3, 4, 4, 5, 7] = merge_sort([4, 2, 5, 7, 3, 1,
					   0, 4]),
    [0, 1, 2, 3, 4, 4, 5, 7] = quicksort([4, 2, 5, 7, 3, 1,
					  0, 4]),
    ok.

perms([]) -> [[]];
perms(L) -> element(1, gen_perms(length(L), L)).

% Heap's algorthim: https://en.wikipedia.org/wiki/Heap%27s_algorithm
gen_perms(1, A) -> {[A], A};
gen_perms(K, A) ->
    {L1, A2} = gen_perms(K - 1, A),
    {L2, A3} = gen_perms(K, A2, 0),
    {L1 ++ L2, A3}.

gen_perms(K, A, I) ->
    A2 = case K rem 2 of
	   0 -> swap(A, I, K - 1);
	   1 -> swap(A, 0, K - 1)
	 end,
    case I + 1 < K - 1 of
      true ->
	  {L1, A3} = gen_perms(K - 1, A2),
	  {L2, A4} = gen_perms(K, A3, I + 1),
	  {L1 ++ L2, A4};
      false -> gen_perms(K - 1, A2)
    end.

% helper function for Heap's algorithm: swap elements I & J of a list
swap([X | Xs], 0, J) ->
    {L, [R | Rs]} = lists:split(J - 1, Xs),
    [R | L] ++ [X | Rs];
swap([X | Xs], I, J) -> [X | swap(Xs, I - 1, J - 1)].

swap_test() ->
    [4, 2, 3, 1] = swap([1, 2, 3, 4], 0, 3), ok.

perms_test() ->
    [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1],
     [3, 2, 1]] =
	perms([1, 2, 3]),
    ok.

test() -> swap_test(), perms_test(), ok.

Great job!

Hey, I am also trying to implement Heap's algorithm, are you sure your implementation is okay?

I see you have repeated some permutations at your test, like [1,2,3] and [2,1,3]

Thanks for the bug report @viniciusd ! What an embarrassing test 😊.
I wasn't preserving the mutations to A in the recursive call to generate.
I've revised the code, please take a look and let me know what you think.

Wow that was fast, I will go over it Tomorrow, I am done for today.

My implementation is at https://gist.github.com/viniciusd/25372491ec2aa8368292fbf6e2788d7c#file-permutations-erl
But it is generating duplicates, I have no idea why. Probably spent all my energy today and need some recharging 😅

I tried adapting the algorithm to Erlang's 1-based lists