1

整数を分割できる方法がいくつあるかを数えようとしています。これまでのところ、私は次の関数を思いついた： 

def partition(num: Int): Int = {
    if(num == 1) return 1
    if(num <= 0) return 0
    return partition(num-1) + partition(num-(num-1))
}
partition(6) //6 instead of 7

例えば：5 -> 4 + 1, 3 + 2, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1

num終わりだと思うので、 1の場合は1を返しますpartition(1)。

多分あなたはそれに論理エラーを見つけることができますか？

4

5 に答える 5

4

私はこれがうまくいくと思います：

def partition(n: Int): Int = {
  def inner(n: Int, max: Int): Int =
    if (n == 0) 1
    else if (n < 0) 0
    else ((1 to max) map (x => inner(n - x, x))).sum

  if (n == 0) 0
  else inner(n, n-1)
}

整数は、、、 ...、にn分割できます。ただし、結果を単純に計算して合計すると、パーティション化のいくつかの方法が2回カウントされます（例：および）。(n-1) + (any way of partitioning 1)(n-2) + (any way of partitioning 2)1 + (any way of partitioning (n-1))partition(m)m = 1 to n-1n1 + (n-1)(n-1) + 1

この問題は、パーティションi{j} < nを合計が。になる正の整数のシーケンスと見なし、順序付けられnたシーケンスのみを考慮することで解決できます。このメソッドには、 。を含むシーケンスのみを考慮することを保証するパラメーターがあります。したがって、たとえば、を考慮しますが、は考慮しません。innermaxi{j} >= i{j+1}2 + 11 + 2

n == 0空のシーケンスを事実上数えたくないので、上記のコードでは厄介なエッジケースです。

于 2012-09-28T15:44:39.870 に答える
2 
def partition(n: Int): Int = {
    def partDecr(n: Int, decr: Int): Int = {
        if (n == 0) 1
        else if (n < 0 || decr == 0) 0
        else partDecr(n - decr, decr) + partDecr(n, decr - 1)
    }
    partDecr(n, n)
}
  • 内部関数は、次の可能なデクリメントを指定する追加のパラメーターを取ります。
  • 最初に、有効な終点にいるかどうかを確認します (1 つの解決策が見つかりました)。
  • 次に、先に進むことができるかどうかをチェックします (正の残りをパーティションに、正のデクリメントを次の試行に)。
  • 次に、2 つの方法で再帰します。
    • 最初は現在のデクリメントを「取り」、それによって n を減らします。
    • 2 番目は現在のデクリメントを「スキップ」し、次に低いデクリメントで試行します。

これは末尾再帰ではなく、かなりのスタック スペースを使用する可能性がありますが、非常に遅いため、あまり問題になりません。

于 2012-09-28T23:16:03.540 に答える
1

別の引数が必要だと思います（パーティションを構成できる整数、それを呼び出しますmadeOf）。そうすれば、問題を2つの厳密に小さいサブセットに分割できます。のカウントpartition(num, madeOf=(n, n-1, ..., 1))はの合計です

  • partition(num, madeOf=(n-1, ..., 1))（nを含まないすべてのパーティション）
  • partition(num-n, madeOf(n, n-1, ..., 1))（少なくとも1つのnがあるすべてのパーティション）

madeOf次に、 1つのintからのみ構築できるため、より最適にすることができます。

def part(num: Int, madeOf: Int): Int =
  if (num == 0) 1 // we found a partition!
  else if (num < 0) 0 // no partition...
  else if (madeOf == 0) 0 // no more ways to make partition
  else part(num, madeOf - 1) +  // all the partitions that don't contain n
    part(num - madeOf, madeOf)  // all the partition that contain n

part(5, 4) // 6
于 2012-09-28T15:24:28.077 に答える
1

必要なものを計算するための「それほど単純な」アルゴリズムはないと思います。OPで提示されたアルゴリズムは、いくつかの理由で機能しません（これについては説明しません）。

ただし、'Partition' に関するウィキペディアのエントリを参照してください。このエントリには、再帰式も含まれています。

この正確な式は、計算上より複雑であり、OP で提示されたアルゴリズムよりも複雑であることに注意してください。

于 2012-09-28T13:45:46.263 に答える
0

次の内部関数を使用できます。パーティション化する番号よりも小さい番号のリストを作成するだけです。たとえば、4 を分割する場合、intNumber は (1,2,3,4) にする必要があります。

  def partition(number: Int, intNumbers: List[Int]): Int = {    
if (number <= 0 || intNumbers.isEmpty) 
  0
else if ((number-intNumbers.head)==0) 
  1+partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)
else 
  partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)
于 2012-09-28T14:10:49.247 に答える