int를 더 낮은 전체 정수로 나눕니다

Question

저는 randint(30,60)을 사용하는 30-60의 범위에서 임의의 int를가집니다. 40이라고 가정 해 봅시다.이 숫자를 정확히 7 개의 무작위 정수로 나누고 싶습니다. 예를 들어 [5,5,5,5,5,5,10]이 유효한 결과입니다. 그러나 이것처럼 많은 해결책이 있습니다. [6,6,6,6,6,6,4] 또는 [4,2,9,13,8,1,3] ... 많은 솔루션이 있지만 빠른 방법을 찾고 있습니다. 모든 단일 솔루션을 얻으려고하지 않고 오히려 단시간에 많은 제품을 반복 할 수있는 빠른 방법을 찾고 있습니다. 이를 달성하는 한 가지 방법은 무작위로 숫자를 고르는 것입니다 (1에서 15까지의 범위에서 말하십시오). 그리고 목록에 저장 한 다음 합계가 정확히 40이 될 때까지 while 루프를 수행합니다. 시도했는데 효율적이지 않습니다. 모든. [5,5,5,5,5,5,10]과 같은 시작 값을 선택하고 "1st digit -2"과 3rd +2과 같은 정확한 방법으로 숫자를 변경하면 [3,5,7,5,5,5,10]이 훨씬 더 빠른 해결책이 될 것이라고 생각합니다. 누구든지 그 방법을 알고 있거나 좋은 제안이 있습니까? 감사. 나는 파이썬 3을 선호한다.

Answer 1

경우에만 임의을 받고 걱정 모두 조합 이상의 철저한 반복보다는 합계가되는 숫자 세트를 사용하면 다음과 같은 정보를 얻을 수 있습니다.

def get_parts(total, num_parts=7, max_part=15): 
    running_total = 0 
    for i in range(num_parts - 1): 
     remaining_total = total - running_total 
     upper_limit = min(max_part, remaining_total - num_parts + 1 + i) 
     # need to make sure there will be enough left 
     lower_limit = max(1, remaining_total - max_part*(num_parts - i - 1)) 
     part = randint(lower_limit, upper_limit) 
     running_total += part 
     yield part 
    yield total - running_total 

>>> list(get_parts(40)) 
[2, 7, 10, 11, 1, 4, 5] 

>>> list(get_parts(40)) 
[7, 13, 11, 6, 1, 1, 1] 

>>> list(get_parts(50, 4)) 
[6, 14, 15, 15] 

물론 위의 각 목록의 항목은 실제로 임의가 아니며 목록의 앞부분에서 더 큰 숫자와 더 작은 숫자를 선호합니다. pseudorandomness 요소를 더 원하면 random.shuffle()을 통해 이러한 목록을 제공 할 수 있습니다.

Answer 2

첫 번째 6 개 값의 합계 (40 개를 초과하지 않는 경우)에 대해 간단한 반복을 수행하고 7 번째 값을 계산할 수있다. 합을 미리 계산하여 (timeit를 사용하여 테스트에 따라)

for a in range(41): 
    for b in range(41-a): 
     for c in range(41-(a+b)): 
      for d in range(41-(a+b+c)): 
       for e in range(41-(a+b+c+d)): 
        for f in range(41-(a+b+c+d+e)): 
         g = 40 - (a+b+c+d+e+f) 
         # Do what you need to do here 

당신은 거의 반으로 루프에 의해 필요한 시간을 줄일 수는 :

for a in range(41): 
    for b in range(41-a): 
     ab = a + b 
     for c in range(41-ab): 
      abc = ab + c 
      for d in range(41-abc): 
       abcd = abc + d 
       for e in range(41-abcd): 
        abcde = abcd + e 
        for f in range(41-abcde): 
         g = 40 - (abcde + f) 
         # Do what you need to do here 

Answer 3

숫자의 합이 n 인 합을 partition이라고하며 n이라고합니다. 주문이 문제가되면 구성이라고합니다.

여기서는 무작위로 작곡하는 것이 합리적으로 빠른 방법입니다.

import random 

def random_partition(n, size): 
    seq = [] 
    while size > 1: 
     x = random.randint(1, 1 + n - size) 
     seq.append(x) 
     n -= x 
     size -= 1 
    seq.append(n) 
    return seq 

n = 40 
for _ in range(20): 
    print(random_partition(n, 7)) 

전형적인 출력 다른 size - 1 숫자는 적어도 1. 다음

는 모든 파티션을 생성하는 매우 효율적인 방법이기 때문에

[26, 2, 8, 1, 1, 1, 1] 
[30, 2, 1, 3, 1, 1, 2] 
[26, 5, 3, 1, 2, 2, 1] 
[2, 25, 9, 1, 1, 1, 1] 
[28, 2, 2, 2, 1, 2, 3] 
[23, 1, 9, 3, 2, 1, 1] 
[3, 26, 1, 7, 1, 1, 1] 
[25, 1, 7, 1, 2, 1, 3] 
[10, 8, 11, 5, 3, 1, 2] 
[19, 16, 1, 1, 1, 1, 1] 
[12, 23, 1, 1, 1, 1, 1] 
[1, 14, 15, 7, 1, 1, 1] 
[29, 5, 1, 1, 2, 1, 1] 
[25, 1, 3, 3, 1, 2, 5] 
[10, 12, 10, 4, 1, 2, 1] 
[13, 4, 6, 14, 1, 1, 1] 
[31, 3, 1, 1, 1, 1, 2] 
[16, 11, 9, 1, 1, 1, 1] 
[3, 26, 5, 3, 1, 1, 1] 
[31, 2, 1, 2, 2, 1, 1] 

우리는 상한으로 1 + n - size를 사용 주어진 정수. 이것들은 순서가 정해져 있습니다. 이 파티션에서 임의의 컴포지션을 생성하려면 random.shuffle을 사용할 수 있습니다.

먼저 크기가 16 인 모든 파티션을 인쇄 한 다음 크기가 27 (= 2738) 인 파티션의 수를 계산합니다.

이 코드는 Jerome Kelleher에 의해 알고리즘에서 파생되었습니다.

def partitionR(num, size): 
    a = [0, num] + [0] * (num - 1) 
    size -= 1 
    k = 1 
    while k > 0: 
     x = a[k - 1] + 1 
     y = a[k] - 1 
     k -= 1 
     while x <= y and k < size: 
      a[k] = x 
      y -= x 
      k += 1 
     a[k] = x + y 
     if k == size: 
      yield a[:k + 1] 

for u in partitionR(16, 5): 
    print(u) 

print('- ' * 32) 
print(sum(1 for _ in partitionR(40, 7))) 

출력

[1, 1, 1, 1, 12] 
[1, 1, 1, 2, 11] 
[1, 1, 1, 3, 10] 
[1, 1, 1, 4, 9] 
[1, 1, 1, 5, 8] 
[1, 1, 1, 6, 7] 
[1, 1, 2, 2, 10] 
[1, 1, 2, 3, 9] 
[1, 1, 2, 4, 8] 
[1, 1, 2, 5, 7] 
[1, 1, 2, 6, 6] 
[1, 1, 3, 3, 8] 
[1, 1, 3, 4, 7] 
[1, 1, 3, 5, 6] 
[1, 1, 4, 4, 6] 
[1, 1, 4, 5, 5] 
[1, 2, 2, 2, 9] 
[1, 2, 2, 3, 8] 
[1, 2, 2, 4, 7] 
[1, 2, 2, 5, 6] 
[1, 2, 3, 3, 7] 
[1, 2, 3, 4, 6] 
[1, 2, 3, 5, 5] 
[1, 2, 4, 4, 5] 
[1, 3, 3, 3, 6] 
[1, 3, 3, 4, 5] 
[1, 3, 4, 4, 4] 
[2, 2, 2, 2, 8] 
[2, 2, 2, 3, 7] 
[2, 2, 2, 4, 6] 
[2, 2, 2, 5, 5] 
[2, 2, 3, 3, 6] 
[2, 2, 3, 4, 5] 
[2, 2, 4, 4, 4] 
[2, 3, 3, 3, 5] 
[2, 3, 3, 4, 4] 
[3, 3, 3, 3, 4] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
2738 

Answer 4

Python Integer Partitioning with given k partitions

def partitionfunc(n,k,l=1): 
    '''n is the integer to partition, k is the length of partitions, l is the min partition element size''' 
    if k < 1: 
     raise StopIteration 
    if k == 1: 
     if n >= l: 
      yield (n,) 
     raise StopIteration 
    for i in range(l,n//k+1): 
     for result in partitionfunc(n-i,k-1,i): 
      yield (i,)+result 
list(partitionfunc(40,7))