[PYTHON] 파이썬 정수 주어진 k 파티션으로 파티션하기

파이썬 정수 주어진 k 파티션으로 파티션하기

파이썬에 대한 정수 파티션 코드를 찾거나 개발하려고합니다.

FYI, Integer Partitioning은 주어진 정수 n을 n보다 작은 정수의 합으로 표시합니다. 예를 들어, 정수 5는 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

나는 이것을위한 많은 해결책을 발견했다. http://homepages.ed.ac.uk/jkellehe/partitions.php 및 http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

그러나 실제로 원하는 것은 파티션 수를 제한하는 것입니다.

말하자면, 파티션 k = 2, 프로그램은 5 = 4 + 1 = 3 + 2를 보여 주면되고,

k = 3, 5 = 3 + 1 + 1 = 2 + 2 + 1이면

해결법

1. ==============================

   1.생성기 솔루션을 작성했습니다.

   생성기 솔루션을 작성했습니다.

   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+1):
           for result in partitionfunc(n-i,k-1,i):
               yield (i,)+result
   

   이렇게하면 길이가 k 인 n의 모든 파티션이 생성되고 각 파티션은 가장 큰 것부터 순서대로 생성됩니다.

   간단히 말하면 다음과 같습니다 : cProfile을 통해, generator 함수를 사용하면 falsetru의 직접 함수를 사용하는 것보다 훨씬 빠르며, 테스트 함수 lambda x, y : list (partitionfunc (x, y))를 사용하는 것보다 빠릅니다. n = 50, k-5의 테스트 실행에서 제 코드는 .019 초에서 직접 메소드의 2.612 초 사이에 실행되었습니다.

2. ==============================

   2.

   def part(n, k):
       def _part(n, k, pre):
           if n <= 0:
               return []
           if k == 1:
               if n <= pre:
                   return [[n]]
               return []
           ret = []
           for i in range(min(pre, n), 0, -1):
               ret += [[i] + sub for sub in _part(n-i, k-1, i)]
           return ret
       return _part(n, k, n)
   

   예:

   >>> part(5, 1)
   [[5]]
   >>> part(5, 2)
   [[4, 1], [3, 2]]
   >>> part(5, 3)
   [[3, 1, 1], [2, 2, 1]]
   >>> part(5, 4)
   [[2, 1, 1, 1]]
   >>> part(5, 5)
   [[1, 1, 1, 1, 1]]
   >>> part(6, 3)
   [[4, 1, 1], [3, 2, 1], [2, 2, 2]]
   

   최신 정보

   메모 사용하기 :

   def part(n, k):
       def memoize(f):
           cache = [[[None] * n for j in xrange(k)] for i in xrange(n)]
           def wrapper(n, k, pre):
               if cache[n-1][k-1][pre-1] is None:
                   cache[n-1][k-1][pre-1] = f(n, k, pre)
               return cache[n-1][k-1][pre-1]
           return wrapper
   
       @memoize
       def _part(n, k, pre):
           if n <= 0:
               return []
           if k == 1:
               if n <= pre:
                   return [(n,)]
               return []
           ret = []
           for i in xrange(min(pre, n), 0, -1):
               ret += [(i,) + sub for sub in _part(n-i, k-1, i)]
           return ret
       return _part(n, k, n)
   

3. ==============================

   3.먼저 모든 분들께 감사드립니다. 여기에 다음 세부 사항으로 정수 파티션을 생성하기위한 알고리즘이 필요합니다.

   먼저 모든 분들께 감사드립니다. 여기에 다음 세부 사항으로 정수 파티션을 생성하기위한 알고리즘이 필요합니다.

   숫자의 파티션을 정확히 k 개의 파트로 생성하지만 MINIMUM 및 MAXIMUM 제약 조건도 있습니다.

   따라서 이러한 새로운 요구 사항을 충족시키기 위해 "Snakes and Coffee"코드를 수정했습니다.

   def partition_min_max(n,k,l, m):
   '''n is the integer to partition, k is the length of partitions, 
   l is the min partition element size, m is the max partition element size '''
   if k < 1:
       raise StopIteration
   if k == 1:
       if n <= m and n>=l :
           yield (n,)
       raise StopIteration
   for i in range(l,m+1):
       for result in partition_min_max(n-i,k-1,i,m):                
           yield result+(i,)
   
   
   >>> x = list(partition_min_max(20 ,3, 3, 10 ))
   >>> print(x)
   >>> [(10, 7, 3), (9, 8, 3), (10, 6, 4), (9, 7, 4), (8, 8, 4), (10, 5, 5), (9, 6, 5), (8, 7, 5), (8, 6, 6), (7, 7, 6)]
   

from https://stackoverflow.com/questions/18503096/python-integer-partitioning-with-given-k-partitions by cc-by-sa and MIT license