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

電力の計算が複雑になる2 乗法によるべき乗を考慮することをお勧めします。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シェルからの使用例（関数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 のリストを遅延させる方法がわかりません。

更新: このバージョンは、末尾再帰にするだけでパフォーマンスの点で改善できます (3 つすべての間に漸近的な違いはないと思いますが)。

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

このスタックオーバーフローの質問は、関数型言語でリストのデカルト力を生成することを扱っていると役立つ場合があります。質問は F# を対象としていますが、コメントにも Haskell の例があります: F#: デカルトの力を見つける方法

于 2012-11-05T22:59:09.137 に答える