具有k个部分的排序和不排序的整数划分 [英] Rank and unrank integer partition with k parts

问题描述

对于正整数n和k，让k-分区n是不同的加起来为n的不同正整数的排序列表，并以给定的k分区的"排名"为其在所有这些列表的排序列表中的位置，按词典顺序从0开始。

例如，有两个2-5分区(n ；= ；5，k ；= ；2)：[1，4]和[2，3]。由于[1，4]在词典顺序中排在[2，3]之前，因此[1，4]的排名为0，[2，3]的排名为1。

因此，我希望能够做两件事：

• 给定n、k和n的k分区，我要找出nk分区的排名。
• 给定n、k和一个排名，我希望找到具有该排名的n的k分区。

我是否可以在不计算n的所有k分区的情况下执行此操作？

此问题与其他问题不同，因为我们在这里讨论的是整数分区，而不仅仅是组合。

推荐答案

这里有一个基于两个想法的使用Python语言的解决方案。首先，动态编程，无需生成分区即可计算分区数。其次，如果第一个值是i，那么我们可以将其视为一个i * k框，其中n-i*k分成了k-1块。

partition_cache = {}
def distinct_partition_count (n, k):
    if n < k:
        return 0
    elif n < 1:
        return 0
    elif k < 1:
        return 0
    elif k == 1:
        return 1
    elif (n, k) not in partition_cache:
        answer = 0
        for i in range(1, n/k + 1):
            answer = answer + distinct_partition_count(n - i*k, k-1)
        partition_cache[(n, k)] = answer
    return partition_cache[(n, k)]

def rank_distinct_partition (values):
    values2 = sorted(values)
    n = sum(values)
    k = len(values)
    answer = 0
    highwater = 0
    for v in values:
        rise = v - highwater
        for i in range(1, rise):
            answer = answer + distinct_partition_count(n - k*i, k-1)
        highwater = v
        ## BUG HERE: was n = n - rise
        n = n - rise * k
        k = k - 1
    return answer

def find_ranked_distinct_partition (n, k, rank):
    if k == 1 and rank == 0:
        return [n]
    elif distinct_partition_count(n, k) <= rank:
        return None
    elif rank < 0:
        return None
    else:
        i = 1
        while distinct_partition_count(n - i*k, k-1) <= rank:
            rank = rank - distinct_partition_count(n - i*k, k-1);
            i = i + 1
        answer = find_ranked_distinct_partition(n - i*k, k-1, rank)
        return [i] + [j + i for j in answer]

print(rank_distinct_partition([2, 3])
print(find_ranked_distinct_partition(5, 2, 1))

这篇关于具有k个部分的排序和不排序的整数划分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！