Генерация пользовательских перестановок с Erlang - PullRequest
Новая
       27

Генерация пользовательских перестановок с Erlang

1 голос
/ 13 декабря 2011

Примечание: это вопрос сиквела к моим предыдущим перестановкам вопрос .

Я хотел бы сгенерировать все перестановки списка в Erlang, ноЯ хотел бы отфильтровать некоторые перестановки, прежде чем они будут добавлены в стек или сохранены где-либо.

Я отфильтрую перестановки на основе некоторых пользовательских специальных правил (назовем их «Фильтр»).

Другими словами, я хотел бы создать список перестановок большого списка (50-300 элементов), но я хотел бы выбросить большинство сгенерированных перестановок прямо во время процесса (я знаю, чтополное число перестановок равно N!).

steenslag дал мне хорошее решение в Ruby: 

res = [1,2,3,4].permutation(3).reject do |perm|
  perm.first.even? #Filter: if this line is true, the perm will be rejected
end

Как я могунаписать что-то похожее на Erlang?

(у меня уже есть функции Filter, написанные на Erlang, поэтому я хотел бы сделать некоторое повторное использование кода).

Кстати, может ли желаемое решение Erlang быть«внутренне параллельный»?

Ответы [ 2 ]

2 голосов
/ 15 декабря 2011

Вы можете фильтровать перестановки, как только они построены.

В качестве примера, эта run () возвращает все перестановки [1,2,3,4], которые начинаются с четного числа.Функция 'check' (которая фильтрует результат) 1) проверяет, является ли его полная перестановка (длина результата == длина списка источников), а затем 2) проверяет условие фильтрации (в моем случае - первая цифра четная). 

run() ->
    perm([1,2,3,4],4).

perm([],_) ->
    [[]];
perm(L,N) -> [[H|T] || H <- L, T <- perm(L--[H],N), check( [H|T] ,N) ].

check(L,N) when length(L) < N -> true;
check([H|_],_) -> trunc(H/2) == H/2. .
1 голос
/ 13 декабря 2011

Я сделал возможную реализацию для проблемы: 

-module(perm).

-export([pred_perms/2, pred/1]).

pred(L = [H | _T]) when H > 1 ->
    L;
pred(_L) ->
    [].

do_pred_perms([], _Pred) -> 
    [[]];
do_pred_perms(L, Pred)  -> 
    [Pred([H|T]) || H <- L, T <- do_pred_perms(L--[H], Pred)].

pred_perms(List, Pred) ->
    Res = do_pred_perms(List, Pred),
    lists:filter(fun(E) -> E =/= [] end, Res).

Он использует пустые списки в качестве заполнителей для списков, которые должны быть отброшены.Если это неприемлемо, вы можете изменить реализацию, чтобы не использовать сжатие списка.

Функция pred / 1 является просто примером функции для использования в качестве предиката.

Надеюсь, это поможет.

...