math - 在Erlang中查找子集，请帮我优化解决方案

Question

全面披露。这是一个面试/预筛选问题，我在面试中未能解决。为了我自己的利益，我决定在 Erlang 中实现它。

问题陈述如下:

You must find number of subsets of an array where the largest number is the sum of the remaining numbers. For example, for an input of:1, 2, 3, 4, 6

the subsets would be

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. 是否有比所有解决方案更清洁的解决方案(这是相当蛮力的)。

谢谢!

Answer 1

这是一个看起来更优雅的版本。

在这个版本中，我只假设正数，希望能加快速度。另外，我有点累了，所以它可能有一些小错别字，但大部分都是正确的:)

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).    

我不确定这可以加快多少，因为我怀疑背包问题可以简化为这个问题。