Преобразовать набор больших целых чисел в набор маленьких

Хотя исходный вопрос касается очень общего сценария, касающегося целочисленных кодировок, я бы предположил, что маловероятно, что существует подход, который работает в полной общности. Например, если P[i] более или менее случайны (с точки зрения теории информации), я был бы удивлен, если бы что-то работало.

Итак, вместо этого давайте обратим наше внимание на актуальную проблему OP создания разделов целого числа N, содержащих ровно K частей. При кодировании комбинаторных объектов как целых чисел нам надлежит сохранить как можно больше комбинаторной структуры. Для этого обратимся к классическому тексту Комбинаторные алгоритмы Найенхейса и Уилфа, в частности, главу 13. Фактически, в этой главе они демонстрируют структуру для перечисления и выборки из ряда комбинаторных семейств, включая разбиения N, где наибольшая часть равна K. Использование известная двойственность между разделами с K частями и разделами, где наибольшая часть равна K (возьмем транспонирование Диаграмма Феррерса), мы обнаруживаем, что нам нужно только внести изменения в процесс декодирования.

В любом случае, вот исходный код:

import sys
import random
import time

if len(sys.argv) < 4 :
    sys.stderr.write("Usage: {0} N K iter\n".format(sys.argv[0]))
    sys.stderr.write("\tN = number to be partitioned\n")
    sys.stderr.write("\tK = number of parts\n")
    sys.stderr.write("\titer = number of iterations (if iter=0, enumerate all partitions)\n")
    quit()

N = int(sys.argv[1])
K = int(sys.argv[2])
iters = int(sys.argv[3])

if (N < K) :
    sys.stderr.write("Error: N<K ({0}<{1})\n".format(N,K))
    quit()

# B[n][k] = number of partitions of n with largest part equal to k
B = [[0 for j in range(K+1)] for i in range(N+1)] 

def calc_B(n,k) :
    for j in xrange(1,k+1) :
        for m in xrange(j, n+1) :
            if j == 1 :
                B[m][j] = 1
            elif m - j > 0 :
                B[m][j] = B[m-1][j-1] + B[m-j][j]
            else :
                B[m][j] = B[m-1][j-1]

def generate(n,k,r=None) :
    path = []
    append = path.append

    # Invalid input
    if n < k or n == 0 or k == 0: 
        return []

    # Pick random number between 1 and B[n][k] if r is not specified
    if r == None :
        r = random.randrange(1,B[n][k]+1)

    # Construct path from r    
    while r > 0 :
        if n==1 and k== 1:
            append('N')
            r = 0   ### Finish loop
        elif r <= B[n-k][k] and B[n-k][k] > 0  : # East/West Move
            append('E')
            n = n-k
        else : #  Northeast/Southwest move
            append('N')
            r -= B[n-k][k]
            n = n-1
            k = k-1

    # Decode path into partition    
    partition = []
    l = 0
    d = 0    
    append = partition.append    
    for i in reversed(path) :
        if i == 'N' :
            if d > 0 : # apply East moves all at once
                for j in xrange(l) :
                    partition[j] += d
            d = 0  # reset East moves
            append(1) # apply North move
            l += 1            
        else :
            d += 1 # accumulate East moves    
    if d > 0 : # apply any remaining East moves
        for j in xrange(l) :
            partition[j] += d

    return partition


t = time.clock()
sys.stderr.write("Generating B table... ")    
calc_B(N, K)
sys.stderr.write("Done ({0} seconds)\n".format(time.clock()-t))

bmax = B[N][K]
Bits = 0
sys.stderr.write("B[{0}][{1}]: {2}\t".format(N,K,bmax))
while bmax > 1 :
    bmax //= 2
    Bits += 1
sys.stderr.write("Bits: {0}\n".format(Bits))

if iters == 0 : # enumerate all partitions
    for i in xrange(1,B[N][K]+1) :
        print i,"\t",generate(N,K,i)

else : # generate random partitions
    t=time.clock()
    for i in xrange(1,iters+1) :
        Q = generate(N,K)
        print Q
        if i%1000==0 :
            sys.stderr.write("{0} written ({1:.3f} seconds)\r".format(i,time.clock()-t))

    sys.stderr.write("{0} written ({1:.3f} seconds total) ({2:.3f} iterations per second)\n".format(i, time.clock()-t, float(i)/(time.clock()-t) if time.clock()-t else 0))

А вот несколько примеров производительности (на MacBook Pro 8.3, 2 ГГц i7, 4 ГБ, Mac OSX 10.6.3, Python 2.6.1):

mhum$ python part.py 20 5 10
Generating B table... Done (6.7e-05 seconds)
B[20][5]: 84    Bits: 6
[7, 6, 5, 1, 1]
[6, 6, 5, 2, 1]
[5, 5, 4, 3, 3]
[7, 4, 3, 3, 3]
[7, 5, 5, 2, 1]
[8, 6, 4, 1, 1]
[5, 4, 4, 4, 3]
[6, 5, 4, 3, 2]
[8, 6, 4, 1, 1]
[10, 4, 2, 2, 2]
10 written (0.000 seconds total) (37174.721 iterations per second)

mhum$ python part.py 20 5 1000000 > /dev/null
Generating B table... Done (5.9e-05 seconds)
B[20][5]: 84    Bits: 6
100000 written (2.013 seconds total) (49665.478 iterations per second)

mhum$ python part.py 200 25 100000 > /dev/null
Generating B table... Done (0.002296 seconds)
B[200][25]: 147151784574    Bits: 37
100000 written (8.342 seconds total) (11987.843 iterations per second)

mhum$ python part.py 3000 200 100000 > /dev/null
Generating B table... Done (0.313318 seconds)
B[3000][200]: 3297770929953648704695235165404132029244952980206369173   Bits: 181
100000 written (59.448 seconds total) (1682.135 iterations per second)

mhum$ python part.py 5000 2000 100000 > /dev/null
Generating B table... Done (4.829086 seconds)
B[5000][2000]: 496025142797537184410324290349759736884515893324969819660    Bits: 188
100000 written (255.328 seconds total) (391.653 iterations per second)

mhum$ python part-final2.py 20 3 0
Generating B table... Done (0.0 seconds)
B[20][3]: 33    Bits: 5
1   [7, 7, 6]
2   [8, 6, 6]
3   [8, 7, 5]
4   [9, 6, 5]
5   [10, 5, 5]
6   [8, 8, 4]
7   [9, 7, 4]
8   [10, 6, 4]
9   [11, 5, 4]
10  [12, 4, 4]
11  [9, 8, 3]
12  [10, 7, 3]
13  [11, 6, 3]
14  [12, 5, 3]
15  [13, 4, 3]
16  [14, 3, 3]
17  [9, 9, 2]
18  [10, 8, 2]
19  [11, 7, 2]
20  [12, 6, 2]
21  [13, 5, 2]
22  [14, 4, 2]
23  [15, 3, 2]
24  [16, 2, 2]
25  [10, 9, 1]
26  [11, 8, 1]
27  [12, 7, 1]
28  [13, 6, 1]
29  [14, 5, 1]
30  [15, 4, 1]
31  [16, 3, 1]
32  [17, 2, 1]
33  [18, 1, 1]

Я оставлю это OP, чтобы убедиться, что этот код действительно генерирует разделы в соответствии с желаемым (равномерным) распределением.

РЕДАКТИРОВАТЬ: добавлен пример функциональности перечисления.

Ниже приведен сценарий, который выполняет то, о чем я просил, в том, что касается перекодирования целых чисел, представляющих целочисленные разделы N с K частями. Чтобы этот подход был практичным для K > 4, необходим лучший метод перекодирования. Это определенно не лучший или предпочтительный подход. Тем не менее, он концептуально прост, и его легко аргументировать как фундаментально беспристрастный. Это также очень быстро для небольших K. Сценарий отлично работает в блокноте Sage и не вызывает функции Sage. Это НЕ скрипт для случайной выборки. Случайная выборка сама по себе не является проблемой.

Метод:

1.) Рассматривайте целочисленные разделы так, как будто их слагаемые объединены вместе и дополнены нулями в соответствии с размером наибольшего слагаемого в первом лексическом разделе, например. [17,1,1,1] -> 17010101 и [5,5,5,5] -> 05050505

2.) Рассматривайте полученные целые числа так, как если бы они вычитались из наибольшего целого числа (т. е. int, представляющего первый лексический раздел). например 17010101 - 5050505 = 11959596

3.) Рассматривайте каждое полученное уменьшенное целое число как разделенное на общий знаменатель, например. 11959596/99 = 120804

Итак, если бы мы хотели выбрать случайный раздел, мы бы:

1.) Выберите число от 0 до 120 804 (вместо числа от 5 050 505 до 17 010 101)

2.) Умножьте число на 99 и вычтите из 17010101

3.) Разделите полученное целое число в соответствии с тем, как мы обрабатывали каждое целое число как дополненное нулями.

За и против: Как указано в тексте вопроса, этот конкретный метод перекодирования не делает достаточно, чтобы значительно повысить вероятность случайного выбора целого числа, представляющего элемент P. Для небольшого количества частей , например K ‹ 5 и существенно большие суммы, т.е. При N > 100 функция, реализующая эту концепцию, может быть очень быстрой, поскольку такой подход позволяет избежать своевременной рекурсии (змея, пожирающая свой хвост), которая замедляет другие случайные функции распределения или делает другие функции непрактичными для работы с большими N.

При малом K вероятность рисования члена P может быть разумной, если учесть, насколько быстрым является оставшийся процесс. В сочетании с быстрым случайным розыгрышем, декодированием и оценкой эта функция может находить равномерные случайные разбиения для комбинаций N&K (например, N = 20000, K = 4), которые несовместимы с другими алгоритмами. Чтобы сделать этот подход эффективным, крайне необходим лучший способ перекодирования целых чисел.

import random
import sys

Во-первых, несколько полезных и простых функций

def first_partition(N,K):
    part = [N-K+1]
    ones = [1]*(K-1)
    part.extend(ones)
return part

def last_partition(N,K):
    most_even = [int(floor(float(N)/float(K)))]*K
    _remainder = int(N%K)
    j = 0

    while _remainder > 0:
        most_even[j] += 1
        _remainder -= 1
        j += 1
    return most_even

def first_part_nmax(N,K,Nmax):
    part = [Nmax]
    N -= Nmax
    K -= 1
    while N > 0:
        Nmax = min(Nmax,N-K+1)
        part.append(Nmax)
        N -= Nmax
        K -= 1

    return part


#print first_partition(20,4)
#print last_partition(20,4)
#print first_part_nmax(20,4,12)
#sys.exit()

def portion(alist, indices): 
    return [alist[i:j] for i, j in zip([0]+indices, indices+[None])]

def next_restricted_part(part,N,K): # *find next partition matching N&K w/out recursion

    if part == last_partition(N,K):return first_partition(N,K)
    for i in enumerate(reversed(part)):
        if i[1] - part[-1] > 1:
            if i[0] == (K-1):
                return first_part_nmax(N,K,(i[1]-1))

            else:
                parts = portion(part,[K-i[0]-1]) # split p
                h1 = parts[0]
                h2 = parts[1]
                next = first_part_nmax(sum(h2),len(h2),(h2[0]-1))
                return h1+next

""" *I don't know a math software that has this function and Nijenhuis and Wilf (1978) 
 don't give it (i.e. NEXPAR is not restricted by K). Apparently, folks often get the
 next restricted part using recursion, which is unnecessary """

def int_to_list(i): # convert an int to a list w/out padding with 0'
    return [int(x) for x in str(i)]

def int_to_list_fill(i,fill):# convert an int to a list and pad with 0's
    return [x for x in str(i).zfill(fill)]

def list_to_int(l):# convert a list to an integer
    return "".join(str(x) for x in l)

def part_to_int(part,fill):# convert an int to a partition of K parts
# and pad with the respective number of 0's

    p_list = []
    for p in part:
        if len(int_to_list(p)) != fill:
            l = int_to_list_fill(p,fill)
            p = list_to_int(l)
        p_list.append(p)
    _int = list_to_int(p_list)
    return _int       

def int_to_part(num,fill,K): # convert an int to a partition of K parts
    # and pad with the respective number of 0's
    # This function isn't called by the script, but I thought I'd include
    # it anyway because it would be used to recover the respective partition

    _list = int_to_list(num)
    if len(_list) != fill*K:
        ct = fill*K - len(_list) 
        while ct > 0:    
            _list.insert(0,0)
            ct -= 1    
    new_list1 = []
    new_list2 = []

    for i in _list:
        new_list1.append(i)
        if len(new_list1) == fill:
            new_list2.append(new_list1)
            new_list1 = []

    part = []
    for i in new_list2:
        j = int(list_to_int(i))
        part.append(j)

    return part

Наконец, мы получаем общее количество N и количество частей K. Далее будут напечатаны разделы, удовлетворяющие N&K, в лексическом порядке с соответствующими перекодированными целыми числами

N = 20
K = 4

print '#,  partition,  coded,    _diff,    smaller_diff'

first_part = first_partition(N,K) # first lexical partition for N&K
fill = len(int_to_list(max(first_part)))
# pad with zeros to 1.) ensure a strictly decreasing relationship w/in P,
# 2.) keep track of (encode/decode) partition summand values

first_num = part_to_int(first_part,fill)
last_part = last_partition(N,K)
last_num = part_to_int(last_part,fill)

print '1',first_part,first_num,'',0,'      ',0

part = list(first_part)
ct = 1
while ct < 10:
    part = next_restricted_part(part,N,K)
    _num = part_to_int(part,fill)

    _diff = int(first_num) - int(_num)
    smaller_diff = (_diff/99)
    ct+=1

    print ct, part, _num,'',_diff,' ',smaller_diff

ВЫВОД:

ct, раздел, закодированный, _diff, small_diff

1 [17, 1, 1, 1] 17010101 0 0

2 [16, 2, 1, 1] 16020101 990000 10000

3 [15, 3, 1, 1] 15030101 1980000 20000

4 [15, 2, 2, 1] 15020201 1989900 20100

5 [14, 4, 1, 1] 14040101 2970000 30000

6 [14, 3, 2, 1] 14030201 2979900 30100

7 [14, 2, 2, 2] 14020202 2989899 30201

8 [13, 5, 1, 1] 13050101 3960000 40000

9 [13, 4, 2, 1] 13040201 3969900 40100

10 [13, 3, 3, 1] 13030301 3979800 40200

Короче говоря, целые числа в последнем столбце могут быть намного меньше.

Почему стратегия случайной выборки, основанная на этой идее, принципиально беспристрастна:

Каждая целочисленная часть из N, состоящая из K частей, соответствует одному и только одному перекодированному целому числу. То есть мы не выбираем число наугад, декодируем его, а затем пытаемся переставить элементы, чтобы сформировать правильный раздел N&K. Следовательно, каждое целое число (независимо от того, соответствует ли оно разбиению N&K или нет) имеет одинаковую вероятность выпадения. Цель состоит в том, чтобы изначально уменьшить количество целых чисел, не соответствующих разбиению N на K частей, и, таким образом, ускорить процесс случайной выборки.