파이썬에서 합계가 10 이하인 모든 조합을 효과적으로 얻는 방법

Question

일부 고정 된 리소스 (예 : n=10)를 일부 지역 (예 : t=5)에 할당하려고한다고 가정 해 보겠습니다. 나는 합계가 n 또는 그 이하인 모든 조합을 얻는 방법을 효율적으로 알아 내려고 노력 중이다.

예. 이 좋고, 0,0,5,5,0 등이 있고, 3,3,3,3,3,3은 분명히 틀립니다.

나는 여기까지 가지고 :

import itertools 
t = 5 
n = 10 
r = [range(n+1)] * t 
for x in itertools.product(*r): 
    if sum(x) <= n:   
     print x 

이 무력 접근 방식은 비록 매우 느린; 더 좋은 방법이 있어야합니까?

타이밍 (1000 반복) :

Default (itertools.product)   --- time: 40.90 s 
falsetru recursion     --- time: 3.63 s 
Aaron Williams Algorithm (impl, Tony) --- time: 0.37 s 

Answer 1

가능한 접근 방법은 다음과 같습니다. 확실히주의해서 사용해야합니다 (거의 테스트하지는 않았지만 n = 10 및 t = 5의 결과는 합리적입니다).

접근법은 아니요 재귀를 포함합니다. Knuth의 네 번째 볼륨에서 m 개의 요소 (예제에서는 5 개)가있는 숫자 n (사용자의 경우 10 개)의 파티션을 생성하는 알고리즘이 제공됩니다. 필요한 경우 각 파티션을 0으로 확장하고 모든 고유 한 순열은 Aaron Williams의 알고리즘을 사용하여 생성 된 것이며 elsewhere이라고합니다. 두 알고리즘 모두는 파이썬으로 변환되어야했고, 그로 인해 오류가 쌓일 확률이 높아졌습니다. 윌리엄스 알고리즘은 링크드리스트 클래스를 작성하는 것을 피하기 위해 2D 배열로 위조해야하는 링크드리스트를 원했습니다.

오후에 있습니다.

코드 (주 당신의 n가 내 maxn하고 t 내 p입니다) :

import itertools 

def visit(a, m): 
    """ Utility function to add partition to the list""" 
    x.append(a[1:m+1]) 

def parts(a, n, m): 
    """ Knuth Algorithm H, Combinatorial Algorithms, Pre-Fascicle 3B 
     Finds all partitions of n having exactly m elements. 
     An upper bound on running time is (3 x number of 
     partitions found) + m. Not recursive!  
    """ 
    while (1): 
     visit(a, m) 
     while a[2] < a[1]-1: 
      a[1] -= 1 
      a[2] += 1 
      visit(a, m) 
     j=3 
     s = a[1]+a[2]-1 
     while a[j] >= a[1]-1: 
      s += a[j] 
      j += 1 
     if j > m: 
      break 
     x = a[j] + 1 
     a[j] = x 
     j -= 1 
     while j>1: 
      a[j] = x 
      s -= x 
      j -= 1 
      a[1] = s 

def distinct_perms(partition): 
    """ Aaron Williams Algorithm 1, "Loopless Generation of Multiset 
     Permutations by Prefix Shifts". Finds all distinct permutations 
     of a list with repeated items. I don't follow the paper all that 
     well, but it _possibly_ has a running time which is proportional 
     to the number of permutations (with 3 shift operations for each 
     permutation on average). Not recursive! 
    """ 

    perms = [] 
    val = 0 
    nxt = 1 
    l1 = [[partition[i],i+1] for i in range(len(partition))] 
    l1[-1][nxt] = None 
    #print(l1) 
    head = 0 
    i = len(l1)-2 
    afteri = i+1 
    tmp = [] 
    tmp += [l1[head][val]] 
    c = head 
    while l1[c][nxt] != None: 
     tmp += [l1[l1[c][nxt]][val]] 
     c = l1[c][nxt] 
    perms.extend([tmp]) 
    while (l1[afteri][nxt] != None) or (l1[afteri][val] < l1[head][val]): 
     if (l1[afteri][nxt] != None) and (l1[i][val]>=l1[l1[afteri][nxt]][val]): 
      beforek = afteri 
     else: 
      beforek = i 
     k = l1[beforek][nxt] 
     l1[beforek][nxt] = l1[k][nxt] 
     l1[k][nxt] = head 
     if l1[k][val] < l1[head][val]: 
      i = k 
     afteri = l1[i][nxt] 
     head = k 
     tmp = [] 
     tmp += [l1[head][val]] 
     c = head 
     while l1[c][nxt] != None: 
      tmp += [l1[l1[c][nxt]][val]] 
      c = l1[c][nxt] 
     perms.extend([tmp]) 

    return perms 

maxn = 10 # max integer to find partitions of 
p = 5 # max number of items in each partition 

# Find all partitions of length p or less adding up 
# to maxn or less 

# Special cases (Knuth's algorithm requires n and m >= 2) 
x = [[i] for i in range(maxn+1)] 
# Main cases: runs parts fn (maxn^2+maxn)/2 times 
for i in range(2, maxn+1): 
    for j in range(2, min(p+1, i+1)): 
     m = j 
     n = i 
     a = [0, n-m+1] + [1] * (m-1) + [-1] + [0] * (n-m-1) 
     parts(a, n, m) 
y = [] 
# For each partition, add zeros if necessary and then find 
# distinct permutations. Runs distinct_perms function once 
# for each partition. 
for part in x: 
    if len(part) < p: 
     y += distinct_perms(part + [0] * (p - len(part))) 
    else: 
     y += distinct_perms(part) 
print(y) 
print(len(y)) 

Answer 2

당신은 동적 프로그래밍을 사용하여 알고리즘을 최적화 할 수 있습니다. 기본적으로

, 당신은 배열 t (수가 아니라 당신의 요소를 가지고 가정, a[i][j] 내가이 (가) j-th 요소 요소까지 (그리고 jth 요소를 사용하여 j의 합을받을 수 "를 의미 배열 a을 가지고 당신은)) 언급했다.

다음

당신이, 당신은 솔루션 :

를 역 추적 할 수이 정보를 사용하여, 다음

a[0][t[0]] = True 
for i in range(1, len(t)): 
    a[i][t[i]] = True 
    for j in range(t[i]+1, n+1): 
     for k in range(0, i): 
      if a[k][j-t[i]]: 
       a[i][j] = True 

을하고있는 배열을 채울 수 있습니다

def backtrack(j = len(t)-1, goal = n): 
    print j, goal 
    all_solutions = [] 
    if j == -1: 
     return [] 
    if goal == t[j]: 
     all_solutions.append([j]) 
    for i in range(j-1, -1, -1): 
     if a[i][goal-t[j]]: 
      r = backtrack(i, goal - t[j]) 
      for l in r: 
       print l 
       l.append(j) 
       all_solutions.append(l) 
    all_solutions.extend(backtrack(j-1, goal)) 
    return all_solutions 


backtrack() # is the answer 

Answer 3

은 당신이 itertools 모든 순열을 생성 할 수 있습니다

def f(r, n, t, acc=[]): 
    if t == 0: 
     if n >= 0: 
      yield acc 
     return 
    for x in r: 
     if x > n: # <---- do not recurse if sum is larger than `n` 
      break 
     for lst in f(r, n-x, t-1, acc + [x]): 
      yield lst 

t = 5 
n = 10 
for xs in f(range(n+1), n, 5): 
    print xs 

Answer 4

합 < = (10)을하는 것이 가능하지 않는 한 요소와 재귀하지 않는 자신의 재귀 함수를 확인하고 numpy과 결과를 분석 .

>>> import numpy as np 
>>> from itertools import product 

>>> t = 5 
>>> n = 10 
>>> r = range(n+1) 

# Create the product numpy array 
>>> prod = np.fromiter(product(r, repeat=t), np.dtype('u1,' * t)) 
>>> prod = prod.view('u1').reshape(-1, t) 

# Extract only permutations that satisfy a condition 
>>> prod[prod.sum(axis=1) < n] 

Timeit :

>>> %%timeit 
    prod = np.fromiter(product(r, repeat=t), np.dtype('u1,' * t)) 
    prod = prod.view('u1').reshape(-1, t) 
    prod[prod.sum(axis=1) < n] 

10 loops, best of 3: 41.6 ms per loop 

는 당신은 populating combinations directly in numpy하여 제품의 계산 속도를 높일 수 있습니다.