Python Integer Partitioning with given k partitions

by

I’ve written a generator solution

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

This generates all the partitions of n with length k with each one being in order of least to greatest.

Just a quick note: Via cProfile, it appears that using the generator method is much faster than using falsetru’s direct method, using the test function lambda x,y: list(partitionfunc(x,y)). On a test run of n=50,k-5, my code ran in .019 seconds vs the 2.612 seconds of the direct method.

More Related Contents:

  1. Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]
  2. Cost of len() function
  3. What’s a good rate limiting algorithm?
  4. Pick N distinct items at random from sequence of unknown length, in only one iteration
  5. Find all combinations of a list of numbers with a given sum
  6. Why is Bubble Sort implementation looping forever?
  7. Edit Distance in Python
  8. Longest increasing subsequence
  9. Speed of calculating powers (in python)
  10. heapq with custom compare predicate
  11. Finding index of nearest point in numpy arrays of x and y coordinates
  12. General bars and stars
  13. Gauss-Legendre Algorithm in python
  14. How to invert a permutation array in numpy
  15. Subset sum Problem
  16. Non biased return a list of n random positive numbers (>=0) so that their sum == total_sum
  17. “For” loop first iteration
  18. Adjacency List and Adjacency Matrix in Python
  19. Binary search algorithm in python
  20. Sliding window maximum in O(n) time
  21. How to hash a string into 8 digits?
  22. What algorithm does Python’s built-in sort() method use?
  23. NumPy grouping using itertools.groupby performance
  24. A set union find algorithm
  25. Finding the most frequent character in a string
  26. Sieve of Eratosthenes – Primes between X and N
  27. What is the Big O Complexity of Reversing the Order of Columns in Pandas DataFrame?
  28. Python – Removing overlapping lists
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment