3

完全開示。これは、面接中に解決できなかった面接/事前選別の質問でした. 私は自分の利益のためにそれをErlangで実装することにしました。

問題文は次のとおりです。

最大数が残りの数の合計である配列のサブセットの数を見つける必要があります。たとえば、次の入力の場合: 1、2、3、4、6

サブセットは

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

これが私の解決策です：

% credit: http://stackoverflow.com/questions/1459152/erlang-listsindex-of-function
index_of(Item, List) -> index_of(Item, List, 1).
index_of(_, [], _)  -> not_found;
index_of(Item, [Item|_], Index) -> Index;
index_of(Item, [_|Tl], Index) -> index_of(Item, Tl, Index+1).

% find sums
findSums(L) ->
    Permutations=generateAllCombos(L),
    lists:filter(fun(LL) -> case index_of(lists:sum(LL), L) of
                    not_found -> false;
                    _ -> true
                end
        end, Permutations).


% generate all combinations of size 2..legnth(L)-1
generateAllCombos(L) ->
    NewL=L--[lists:last(L)],
    Sizes=lists:seq(2,length(NewL)),
    lists:flatmap(fun(X) -> simplePermute(NewL,X) end, Sizes).

% generate a list of permutations of size R from list L
simplePermute(_,R) when R == 0 ->
    [[]];

simplePermute(L,R) ->
    [[X|T] || X <- L, T<-simplePermute(lists:nthtail(index_of(X,L),L),R-1)].

実行例を次に示します。

例：

18> maxsubsetsum_app:findSums([1,2,3,4,6]).
[[1,2],[1,3],[2,4],[1,2,3]]

質問

  1. 親愛なる Erlangers (Erlangists?) の皆さん、これは正規の Erlang に見えますか?
  2. 私がしたことを言うより良い方法はありますか？
  3. すべてのソリューションにクリーナーがありますか (これは非常に力ずくです)。

ありがとうございました！

4

2 に答える 2

2

これは、よりエレガントな外観のバージョンです。

このバージョンでは、速度が向上することを期待して、正の数のみを想定しています。また、私は少し疲れているので、小さなタイプミスがあるかもしれませんが、ほとんど正しいです:)

get_tails([]) -> [];
get_tails([_]) -> [];
get_tails([X:XS]) -> [[X:XS],get_tails(XS)].

get_sums([]) -> [];
get_sums([_]) -> [];
get_sums([X:XS]) -> [get_sums_worker(X,XS):get_sums(XS)]

get_sums_worker(S,_) when S < 0 -> [];
get_sums_worker(S,_) when S == 0 -> [[]];
get_sums_worker(S,[X:XS]) when S > 0 ->
    get_sums_worker(S, XS) ++ [[X:L] || L <- get_sums_worker(S - X, XS)].

sums(A0) ->
    A = lists:reverse(lists:sort(A0)),
    B = get_tails(A),
    lists:flatmap(fun get_sums/1, B).

ナップザックの問題はこの質問に還元されるのではないかと思うので、これをどれだけ高速化できるかはわかりません。

于 2013-07-19T23:41:03.883 に答える