Efficient list rotation

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Efficient list rotation

Joel Reymont-2
Folks,

Is there a more efficient version of this code? I understand that it's
better to append to the head of the list and reverse afterwards but
appending to the tail works with the logic of the task.

I'm trying to rotate the list so that a particular item is at the tail of
the list, that is if I rotate the list once more it will be at the head.

As a bit of background info, I need this for my poker logic as when a
player makes a bet I rotate the list and place them at the tail. I might
delete them right after or I might not.

-module(bar).
-compile([export_all]).

rotate(_Target, []) ->
    [];

rotate(Target, [H|T]) ->
    rotate(Target, [H|T], none).

rotate(Target, [H|T], none) when Target =:= H ->
    rotate(Target, T, H);

rotate(Target, [H|T], none) ->
    rotate(Target, T ++ [H], none);

rotate(_Target, [], X) ->
    [X];

rotate(_Target, [H|T], X) ->
    [H|T] ++ [X].

    Thanks, Joel

--
http://wagerlabs.com/tech




Reply | Threaded
Open this post in threaded view
|

Efficient list rotation

Luke Gorrie-3
Hi Joel,

The problem is to move the first element of the list to the end?
Here's a simple way:

  move_first_to_last([H|T]) -> T++[H].

The list would be representing a queue. There is also a queue data
structure in OTP ('queue' module) which is quite a cute, I remember
stepping through the algorithm with billiard balls when I was learning
Erlang :-). For your purposes a plain ol' list sounds fine.

Or do you really need to move the Nth element to the tail instead?




Reply | Threaded
Open this post in threaded view
|

Efficient list rotation

Raimo Niskanen-3
In reply to this post by Joel Reymont-2
Have a look at the module 'queue'. It implements a FIFO queue,
which can be used as a rotatable list.

joelr1 (Joel Reymont) writes:

> Folks,
>
> Is there a more efficient version of this code? I understand that it's
> better to append to the head of the list and reverse afterwards but
> appending to the tail works with the logic of the task.
>
> I'm trying to rotate the list so that a particular item is at the tail of
> the list, that is if I rotate the list once more it will be at the head.
>
> As a bit of background info, I need this for my poker logic as when a
> player makes a bet I rotate the list and place them at the tail. I might
> delete them right after or I might not.
>
> -module(bar).
> -compile([export_all]).
>
> rotate(_Target, []) ->
>     [];
>
> rotate(Target, [H|T]) ->
>     rotate(Target, [H|T], none).
>
> rotate(Target, [H|T], none) when Target =:= H ->
>     rotate(Target, T, H);
>
> rotate(Target, [H|T], none) ->
>     rotate(Target, T ++ [H], none);
>
> rotate(_Target, [], X) ->
>     [X];
>
> rotate(_Target, [H|T], X) ->
>     [H|T] ++ [X].
>
>     Thanks, Joel
>
> --
> http://wagerlabs.com/tech
>
>

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB


Reply | Threaded
Open this post in threaded view
|

Efficient list rotation

Joel Reymont-2
In reply to this post by Luke Gorrie-3
Hi Luke!

>The problem is to move the first element of the list to the end?
>Here's a simple way:
>
>  move_first_to_last([H|T]) -> T++[H].

I don't know in advance the position of the element that will be moving
to the end :-(. And I really need to "rotate" the list as opposed to
moving it to the end, yes, in a queue-like fashion :).

    Thanks, Joel

--
http://wagerlabs.com/tech




Reply | Threaded
Open this post in threaded view
|

Efficient list rotation

Vladimir Sekissov
In reply to this post by Joel Reymont-2
Good day,

joelr1> -module(bar).
joelr1> -compile([export_all]).
joelr1>
joelr1> rotate(_Target, []) ->
joelr1>     [];
joelr1>
joelr1> rotate(Target, [H|T]) ->
joelr1>     rotate(Target, [H|T], none).
joelr1>
joelr1> rotate(Target, [H|T], none) when Target =:= H ->
joelr1>     rotate(Target, T, H);
joelr1>
joelr1> rotate(Target, [H|T], none) ->
joelr1>     rotate(Target, T ++ [H], none);
joelr1>
joelr1> rotate(_Target, [], X) ->
joelr1>     [X];
joelr1>
joelr1> rotate(_Target, [H|T], X) ->
joelr1>     [H|T] ++ [X].

rotate(Target, L) ->
    {Before, FromToEnd} =
          lists:splitwith(fun (E) -> E =/= Target end, L),
    case FromToEnd of
       [Target|T] ->
         T ++ lists:reverse([T|Before]);
       _ ->
         lists:reverse(L)
    end.

Best Regards,
Vladimir Sekissov