Ранговое и unrank целочисленное разбиение с k частями

Question

Для целых положительных чисел n и k , пусть " k -раздел n " будет отсортированным списком k различных положительных целых чисел, которые складываются в n , и позволяют "рангу" данного k -раздела n быть его позицией вотсортированный список всех этих списков в лексикографическом порядке, начиная с 0.

Например, есть два 2-разбиения по 5 ( n = 5, k = 2): [1,4] и [2,3].Поскольку [1,4] предшествует [2,3] в лексикографическом порядке, ранг [1,4] равен 0, а ранг [2,3] равен 1.

Итак, я хочууметь делать две вещи:

• Дано n , k и k -разделение n , я хочу найти ранг этого k -раздела n .
• Учитывая n , k и ранг, я хочу найти k -раздел n с таким рангом.

Могу ли я сделать это без необходимости вычислять все k -разделы n , которые предшествуют интересующему?

Этот вопрос отличается от других, потому что мы здесь говорим о целочисленных разбиениях, а не просто комбинациях.

Answer 1

Вот решение на 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
        n = n - rise
        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))