9

長さのリストを与えることができ、それらの長さまでのデカルト座標のすべての組み合わせを返すメソッドを作成したいと思います。例で説明するのは簡単です：

cart [2,5]
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ]

cart [2,2,2]
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ]

リストがどれくらいの長さになるかわからないため、単純なリストの理解は機能しません。私は多くの問題で Haskell のシンプルさが気に入っていますが、Haskell では動脈瘤ができてしまうのに対し、これは手続き的に (C か何かで) 5 分で書ける問題です!

この特定の問題の解決策は、私を大いに助けてくれます。また、このようなことに取り組むときの思考プロセスについてもお聞きしたいと思います.

4

3 に答える 3

13

うーん..

cart = sequence . map (enumFromTo 0 . subtract 1)

[[a]] -> [[a]]私たちが期待することを行う関数が既にライブラリに存在していると期待するのは合理的です。したがって、に慣れていない場合sequenceは、それを見つけるのは簡単なことです。

編集： newacctが指摘したように：

cart = mapM (enumFromTo 0 . subtract 1)

これは、前のソリューションをHLintに渡すことによっても見つけることができます。

于 2010-04-11T09:32:27.610 に答える
12

これは再帰的に解決できます。まず、無のデカルト積は {∅} です。

cart [] = [[]]

(または、空の製品が無効な場合は、1 要素フォームのみを定義します。

cart [x] = [[i] | i <- [0 .. x-1]]

)

次に、 のデカルト積は次のx:xsように記述できます。

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs]

一般に、リストの長さNを必要とする関数fを作成する場合、 f(N)をより小さなリスト (たとえばf(N - 1)のみ)に依存させる方法を考えてから、基本ケースf( 0)またはf(1)など。これにより、問題は簡単に解決できる再帰に変換されます。

于 2010-04-11T07:46:18.417 に答える
7

あなたの手続き的な解決策には再帰が含まれるに違いありません。Haskell ソリューションには再帰も含まれます。

では、再帰。まず再帰的なケース。

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart]
  where rcart = cart cs

ここで言いたいのは、可能な初期座標と、残りの長さからのデカルト座標の可能な組み合わせごとに、座標を残りの座標と組み合わせるという明らかなことを行うということです。

次にベースケース。

cart [] = [[]]

と思うかもしれませんcart [] = []。私は最初にしました。しかし、再帰ケースが基本ケースから何を必要とするかを考えてみてください。

于 2010-04-11T07:50:16.960 に答える