排名和取消排名具有最大值的受限整数分区

Question

我想对具有最大值

m

的受限整数分区进行排名/取消排名。 在此链接中https://stackoverflow.com/a/64316625/6301603描述了一种对具有最大值的受限整数分区进行计数的方法。但是如何使用给定的

count()

函数对特定的受限整数分区进行排名/取消排名？

示例：

n = 15

总和

k = 4

不同整数的数量

m = 10

最大可能的整数

鉴于这些属性，并且

rank = 1

unranking 应该返回

1,2,4,8

。

Rank

2,3,4,6

应返回属性

rank = 5

具有给定属性的所有有效受限整数分区的字母顺序：

1,2,3,9

->

0

1,2,4,8

->

1

1,2,5,7

->

2

1,3,4,7

->

3

1,3,5,7

->

4

2,3,4,6

->

5

如何以给定的计数函数为基础对具有最大值的受限整数分区进行un/ranking？

计数功能：

@Test
public void test() {
    count(600, (short) 25, (short) 200, new Has hMap());
}

public BigInteger count(int sum, short k, short m Map<Triple<Integer,Short, Short>, Big Integer>) {
    // If the biggest allowed number in a partition is less than the number of parts, then
    // they cannot all be distinct, therefore we have zero results.
    if (m < k) {
        return BigInteger.ZERO;
    }
    
    // If the sum of minimum element-values for k is less than the expected sum, then
    // we also have no results.
    final int v = ((k * ((int) k + 1)) / 2);
    if (sum < v) {
        return BigInteger.ZERO;
    }
    
    // We normalize the problem by lifting the distinction restriction.
    final int sumNorm = sum - v;
    final short mNorm = (short) (m - k);
    
    BigInteger result = countHelper(sumNorm, k, mNorm, cache);
    
    return result;
}

public BigInteger countHelper(int sum, short k, short m, Map<Triple<Integer,Short, Short>,Big Integer> cache) {
    
    // We can improve cache use by standing the k*m-rectangle upright (k being the 'bottom').
    if (k > m) {
        final short c = k;
        k = m;
        m = c;
    }
    
    // If the result is trivial, we just calculate it. This is true for k < 3
    if (k < 3) {
        if (k == 0) {
            return sum == 0 ? BigInteger.ONE : BigInteger.ZERO;
            
        } else if (k == 1) {
            return sum <= m ? BigInteger.ONE : BigInteger.ZERO;
            
        } else {
            final int upper = Math.min(sum, m);
            final int lower = sum - upper;
            
            if (upper < lower) {
                return BigInteger.ZERO;
            }
            
            final int difference = upper - lower;
            final int numSubParts = difference / 2 + 1;
            return BigInteger.valueOf(numSubParts);
        }
    }
    
    // If k * m / 2 < sum, we can 'invert' the sub problem to reduce the number of keys further.
    sum = Math.min(sum, k * m - sum);
    
    // If the sum is less than m and maybe even k, we can reduce the box. This improves the cache size even further.
    if (sum < m) {
        m = (short) sum;
        
        if (sum < k) {
            k = (short) sum;

            if (k < 3) {
                return countHelper(sum, k, m, cache);
            }
        }
    }
    
    // If the result is non-trivial, we check the cache or delegate.
    final Triple<Short, Short, Integer> key = Triple.of(k, m, sum);
    final BigInteger cachedResult = cache.get(key);
    if (cachedResult != null) {
        return cachedResult;
    }
    
    BigInteger current = BigInteger.ZERO;
    
    // i = m is reached in case the result is an ascending stair e.g. [1, 2, 3, 4]
    for (int i = 0; i <= m; ++i) {
        final int currentSum = sum - (i * k);
        if (currentSum < 0) {
            break;
        }
        
        short currentK = (short) (k - 1);
        short currentM = (short) (m - i);
        
        current = current.add(countHelper(currentSum, currentK, currentM, cache));
    }
    
    // We cache this new result and return it.
    cache.put(key, current);
    return current;
}

Answer 1

我刚刚意识到我可以使用此答案中的排名/取消排名功能：

https://stackoverflow.com/a/56782034/6301603