5

我正在尝试编写一个 erlang Mastermind 求解器作为练习（我是一个完整的新手，但我认为这对于函数式语言来说是一个有趣的练习）

我希望它尽可能通用，所以我觉得我需要一个笛卡尔幂函数。就像是：

cart_pow([a,b],2) -> [[a,a],[a,b],[b,a],[b,b]]
cart_pow([a,b],3) -> [[a,a,a],[a,a,b],[a,b,a],[a,b,b],[b,a,a],[b,a,b],[b,b,a],[b,b,b]]

我想不出一个纯粹的功能（递归，映射，折叠......）解决方案。有什么线索吗？如果它是懒惰的奖励。

4

3 回答 3

3

@Ed'ka 提供的解决方案简洁而漂亮，但尽管如此，它的复杂性是O(N).

我建议您考虑通过平方方法求幂，它提供O(log(N))了幂计算的复杂性。使用这种技术，笛卡尔幂可以这样实现：

%% Entry point
cart(List, N) ->
        Tmp = [[X] || X <- List],
        cart(Tmp, Tmp, N).

cart(_InitialList, CurrList, 1) ->
        CurrList;
cart(_InitialList, CurrList, N) when N rem 2 == 0 ->
        Tmp = mul(CurrList, CurrList),
        cart(Tmp, Tmp, N div 2);
cart(InitialList, CurrList, N) ->
        Tmp = cart(InitialList, CurrList, N - 1),
        mul(InitialList, Tmp).

mul(L1, L2) ->
        [X++Y || X <- L1, Y <- L2].

PS shell 的使用示例（我已将函数打包cart到 mudule 中my_module）：

1> c(my_module).
{ok,my_module}
2> 
2> my_module:cart([0,1], 2).
[[0,0],[0,1],[1,0],[1,1]]
3> 
3> my_module:cart([0,1], 3).
[[0,0,0],
 [0,0,1],
 [0,1,0],
 [0,1,1],
 [1,0,0],
 [1,0,1],
 [1,1,0],
 [1,1,1]]
于 2012-11-06T00:31:20.160 回答
2

从 Haskell 实现：

cart_pow(Xs, N) -> 
    sequence(lists:duplicate(N, Xs)).

sequence([]) ->
    [[]];
sequence([Xs|Xss]) ->
    [[X|Xs1] || X <- Xs, Xs1 <- sequence(Xss)].

不过，不确定如何使 Erlang 的列表变得懒惰。

更新： 这个版本可以通过简单地使其尾递归来提高性能（尽管我相信这三个之间没有渐近差异）

cart_pow(Xs, N) -> 
    sequence(lists:duplicate(N, Xs)).

sequence(Xss) ->
    sequence(Xss, [[]]).

sequence([], Acc) ->
    Acc;
sequence([Xs|Xss], Acc) ->
    sequence(Xss, [[X|Xs1] || X <- Xs, Xs1 <- Acc]).

与@stemm 的版本相比：

1> timer:tc(fun() -> length(tmp1:cart([0,1], 20)) end).
{383939,1048576}
2> timer:tc(fun() -> length(tmp1:cart_pow([0,1], 20)) end).
{163932,1048576}

PS：甚至更好：

sequence(Xss) ->
    lists:foldl(fun(Xs, A) -> [[X|Xs1] || X <- Xs, Xs1 <- A] end, [[]], Xss).
于 2012-11-05T23:53:32.707 回答
1

您可能会发现这个 Stack Overflow 问题很有帮助，它涉及在函数式语言中生成列表的笛卡尔幂。该问题针对 F#，但评论中也有一个 Haskell 示例：F#: how to find Cartesian power

于 2012-11-05T22:59:09.137 回答