Longest increasing subsequence: Difference between revisions

=={{header|Elixir}}==

{{trans|Erlang}}

===Naive version===

very slow

<lang elixir>defmodule Longest_increasing_subsequence do

# Naive implementation

def lis(l) do

(for ss <- combos(l), ss == Enum.sort(ss), do: ss)

|> Enum.max_by(fn ss -> length(ss) end)

end

defp combos(l) do

Enum.reduce(1..length(l), [[]], fn k, acc -> acc ++ (combos(k, l)) end)

end

defp combos(1, l), do: (for x <- l, do: [x])

defp combos(k, l) when k == length(l), do: [l]

defp combos(k, [h|t]) do

(for subcombos <- combos(k-1, t), do: [h | subcombos]) ++ combos(k, t)

end

end

IO.inspect Longest_increasing_subsequence.lis([3,2,6,4,5,1])

IO.inspect Longest_increasing_subsequence.lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])</lang>

{{out}}

<pre>

[3, 4, 5]

[0, 4, 6, 9, 13, 15]

</pre>

===Patience sort version===

<lang elixir>defmodule Longest_increasing_subsequence do

# Patience sort implementation

def patience_lis(l), do: patience_lis(l, [])

defp patience_lis([h | t], []), do: patience_lis(t, [[{h,[]}]])

defp patience_lis([h | t], stacks), do: patience_lis(t, place_in_stack(h, stacks, []))

defp patience_lis([], []), do: []

defp patience_lis([], stacks), do: get_previous(stacks) |> recover_lis |> Enum.reverse

defp place_in_stack(e, [stack = [{h,_} | _] | tstacks], prevstacks) when h > e do

prevstacks ++ [[{e, get_previous(prevstacks)} | stack] | tstacks]

end

defp place_in_stack(e, [stack | tstacks], prevstacks) do

place_in_stack(e, tstacks, prevstacks ++ [stack])

end

defp place_in_stack(e, [], prevstacks) do

prevstacks ++ [[{e, get_previous(prevstacks)}]]

end

defp get_previous(stack = [_|_]), do: hd(List.last(stack))

defp get_previous([]), do: []

defp recover_lis({e, prev}), do: [e | recover_lis(prev)]

defp recover_lis([]), do: []

end

IO.inspect Longest_increasing_subsequence.patience_lis([3,2,6,4,5,1])

IO.inspect Longest_increasing_subsequence.patience_lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])</lang>

{{out}}

<pre>

[2, 4, 5]

[0, 2, 6, 9, 11, 15]

</pre>