0

整数のリストのすべてのパーティションを見つけるにはどうすればよいですか? ほとんどの場合、SML で実装するので、再帰を使用するアルゴリズムが必要です。アルゴリズムだけが必要です。コーディング部分は自分で行います。誤ってサブセットを見つけるためのコードを書きましたが、これを行う時間があまりありません

SML はパスカルと似たようなものなので、フォーマットのコツをつかむことができます。例えば階乗で書くと、このような楽しい fuc x = if x<0 then 0 else if x=1 then 1 else x*(fac x-1)

前もって感謝します

4

4 に答える 4

1

セットの k パーティションがある場合、たとえばのk パーティションを生成できます。S {S1,...,Sn}{P1,...,Pk}kS ⋃ {Sn+1}

{P1,..., Pi-1, Pi ⋃ {n+1}, Pi+1,... Pk}i{1...k}で

プラス (k+1)-パーティションP ⋃ {k+1}

これらを から生成されたパーティションと呼びPます。の 2 つの異なるパーティションから生成されたパーティションのすべてのセット{1,...,n}が素であること、および のすべてのパーティションが の{1,...,n+1}何らかのパーティションから生成されることを示すのは簡単です{1,...,n}。

問題の再帰的な解決策を明らかにするには、これで十分だと思います。

検証のために、{1,...,n} のパーティション数のカウントはB(n)ベルB番号です (Sloane A000110 )

于 2012-12-13T19:14:46.160 に答える
1

分割問題は既知のNP 困難な問題であり (そのため、既知の多項式解はありません)、再帰で適切に記述された徹底的な検索を使用して解決できます。

疑似コード (ML のような疑似コードを実行しようとしました。役に立ち、明確になることを願っています):

partition([],A,B): #base clause
   if (sum(A) == sum(B)):
        print (A,B) # this is a partition
partition(list, A,B):
   e <- head(list)
   partition(tail(list),e :: A,B)
   partition(tail(list),A, e :: B)

( MLe :: Aの先頭に要素を追加していることを正しく覚えAていれば、間違っていた場合は自由に修正してください)

于 2012-12-12T23:40:21.307 に答える
1

これをチェックして、すべてのサブセットを見つけてください。基本的に、順列の反復ごとに、現在のサブセットの和集合からセット全体を差し引くことで、パーティションの他の部分を取得できます。

于 2012-12-12T23:55:14.797 に答える
1

amit への返信から判断すると、次のものを探しているようです。

fun partitions [] = []
  | partitions [x] = [[[x]]]
  | partitions (x::xs) =
    let
       val zsss = partitions xs
    in
       map (fn zss => [x]::zss) zsss @
       map (fn zs::zss => (x::zs)::zss) zsss
    end

編集：申し訳ありませんが、以前の例をpartition [1,2,3] = [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[1],[2],[3]]]、つまり、順序付けられたパーティションと読み違えました。

これがあなたの実際の質問に対する解決策です（私は思います）：

fun extensions x [] = []
  | extensions x (xs::xss) =
    ((x::xs)::xss) :: map (fn zss => xs::zss) (extensions x xss)

fun partitions [] = [[]]
  | partitions (x::xs) =
    List.concat (map (fn zss => ([x]::zss) :: extensions x zss) (partitions xs))
于 2012-12-13T21:49:41.307 に答える