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

看起来这是你的算法：

  1. 生成所有组合 (2^n)
  2. 对每组组合求和 (n)
  3. 在列表中搜索每个总和 (n)

看起来是这样的n*2^n。我认为这在计算方面是尽可能快的，因为您必须尝试列表中每个数字的所有组合的顺序。也许有人可以纠正我。

但是，您的空间效率似乎是2^n，因为它存储了所有组合，这是不必要的。

这是我想出的，它只会累积结果：

  1. 对于每个项目，在列表的其余部分中搜索与其相加的组合。
  2. 为了找到组合，从目标数字中减去列表的第一个数字，然后在列表的其余部分中搜索加起来差的组合。
-module(subsets).

-export([find_subsets/1]).


find_subsets(NumList) ->
  ReverseSorted = lists:reverse(lists:sort(NumList)),
  find_each_subset(ReverseSorted, []).

find_each_subset([], Subsets) ->
  Subsets;
find_each_subset([First | ReverseSorted], Subsets) ->
  [ { First, recurse_find_subsets(First, ReverseSorted, [])} | find_each_subset(ReverseSorted, Subsets)].

recurse_find_subsets(_Target, [], Sets) ->
  Sets;
recurse_find_subsets(Target, [Target | _Numbers], []) ->
  [[Target]];
recurse_find_subsets(Target, [First | Numbers], Sets) when Target - First > 0 ->
  Subsets = recurse_find_subsets(Target - First, Numbers, []),
  NewSets = lists:map(fun(Subset) -> [ First | Subset] end, Subsets),
  recurse_find_subsets(Target, Numbers, lists:append(NewSets, Sets));
recurse_find_subsets(Target, [_First | Numbers], Sets) ->
  recurse_find_subsets(Target, Numbers, Sets).

输出：

5> subsets:find_subsets([6,4,3,2,1]).
[{6,[[3,2,1],[4,2]]},{4,[[3,1]]},{3,[[2,1]]},{2,[]},{1,[]}]
于 2013-07-19T23:51:11.423 回答
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 回答