2

次のコードでは、制限された整数パーティション (各番号は各パーティションで 1 回のみ発生する可能性があります) を各パーティションのk番号でカウントし1ますm。このコードは大量のキャッシュ値を生成するため、すぐにメモリ不足になります。

例：

sum := 15, k := 4, m:= 10期待される結果は6

次の制限付き整数パーティションがあります。

1,2,3,9、、、、、、1,2,4,8_ 1,2,5,7_ 1,3,4,7_ 1,3,5,7_2,3,4,6

public class Key{
  private final int sum;
  private final short k1;
  private final short start;
  private final short end;

  public Key(int sum, short k1, short start, short end){
    this.sum = sum;
    this.k1 = k1;
    this.start = start;
    this.end = end;
  }
  // + hashcode and equals
}

public BigInteger calcRestrictedIntegerPartitions(int sum,short k,short m){
  return calcRestrictedIntegerPartitionsHelper(sum,(short)0,k,(short)1,m,new HashMap<>());
}

private BigInteger calcRestrictedIntegerPartitionsHelper(int sum, short k1, short k, short start, short end, Map<Key,BigInteger> cache){
  if(sum < 0){
    return BigInteger.ZERO;
  }
  if(k1 == k){
    if(sum ==0){
      return BigInteger.ONE;
    }
    return BigInteger.ZERO;
  }
  if(end*(k-k1) < sum){
    return BigInteger.ZERO;
  }

  final Key key = new Key(sum,(short)(k-k1),start,end);

  BigInteger fetched = cache.get(key);

  if(fetched == null){
    BigInteger tmp = BigInteger.ZERO;

    for(short i=start; i <= end;i++){
      tmp = tmp.add(calcRestrictedIntegerPartitionsHelper(sum-i,(short)(k1+1),k,(short)(i+1),end,cache));
    }

    cache.put(key, tmp);
    return tmp;
  }

  return fetched;
}

キャッシュを回避/削減する公式はありますか? または、制限された整数部分をどのように数えることができますk and mか?

4

3 に答える 3

3

キーには 4 つの部分が含まれているため、ハッシュ スペースはこれらの部分の最大値の積の値に達する可能性があります。バックワード ループとゼロ値を自然な制限として使用して、キーを 3 つの部分に減らすことができます。

Python の例では、組み込み機能lru_cacheをハッシュテーブル サイズ = で使用していますN*K*M

@functools.lru_cache(250000)
def diff_partition(N, K, M):
    '''Counts integer partitions of N with K distint parts <= M'''
    if K == 0:
        if N == 0:
            return 1
        return 0
    res = 0
    for i in range(min(N, M), -1, -1):
        res += diff_partition(N - i, K - 1, i - 1)
    return res

def diffparts(Sum, K, M):   #diminish problem size allowing zero part
    return diff_partition(Sum - K, K, M-1)

print(diffparts(500, 25, 200))

>>>147151784574
于 2020-10-12T10:45:31.957 に答える