Elegant Python Code for Integer Partitioning

Elegant Python code for Integer Partitioning

While this answer is fine, I'd recommend skovorodkin's answer.

>>> def partition(number):
...     answer = set()
...     answer.add((number, ))
...     for x in range(1, number):
...         for y in partition(number - x):
...             answer.add(tuple(sorted((x, ) + y)))
...     return answer
... 
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])

If you want all permutations(ie (1, 3) and (3, 1)) change answer.add(tuple(sorted((x, ) + y)) to answer.add((x, ) + y)

Python Integer Partitioning with given k partitions

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.

Recursion for Integer Partitioning using numbers only once in Python is slow

Reference on this sequence: http://oeis.org/A000009

You can think of the problem of partitioning n into distinct parts as a coin change problem with (single) coins of values 1 to n. (Or one less than this, since it seems you're disallowing the partition of n as the single number n).

You can count solutions by adapting a standard coin-change dynamic programming solution.

def Q(n):
    A = [1] + [0] * n
    for i in range(1, n+1):
        for j in range(n, i-1, -1):
            A[j] += A[j-i]
    return A[n] - 1

print(Q(500))

You can understand this program by noting that after k iterations of the outer loop, A[i] contains the number of ways of partitioning i with the distinct elements from 1..k. And that the number of ways of partitioning i with distinct elements from 1..k+1 is the number of ways of partitioning i with distinct elements from 1..k plus the number of ways of partitioning i-k-1 with elements from 1..k.

This runs in O(n^2) time, but it's fast for small cases (eg: partitions of 500 here, takes 0.033s on my machine).

Integer partition N into M parts in parallel

Here's a solution that works in limited cases, M hast to divide N, 2 has to divide M, and the maximium is limited, but this is the behaviour I wanted.

You start of with the equal partition then calculate a delta that sums to zero...

M = 4
N = 16
MINIMUM = 1
assert N % M == 0
assert M % 2 == 0
avg = N // M

equal_partition = torch.full((M,), avg)
half_delta = torch.randint(-(avg-MINIMUM), avg-MINIMUM, (M // 2,))
delta = torch.cat((half_delta, -half_delta), dim=-1)[torch.randperm(M)]
partition = equal_partition + delta
print(partition, partition.sum())

How do i optimize this code to run for larger values?

Generating all combinations is indeed not very efficient as most will not add up to n.

Instead, you could use a recursive function, which can be called after taking away one partition (i.e. one term of the sum), and will solve the problem for the remaining amount, given an extra indication that future partitions should be greater than the one just taken.

To further improve the efficiency, you can use memoization (dynamic programming) to avoid solving the same sub problem multiple times.

Here is the code for that:

def solution(n, least=1, memo={}):
    if n < least:
        return 0
    key = (n, least)
    if key in memo:  # Use memoization
        return memo[key]
    # Counting the case where n is not partitioned
    #    (But do not count it when it is the original number itself)
    count = int(least > 1)
    # Counting the cases where n is partitioned
    for i in range(least, (n + 1) // 2):
        count += solution(n - i, i + 1)
    memo[key] = count
    return count

Tested the code with these arguments. The comments list the sums that are counted:

print(solution(1)) # none
print(solution(2)) # none
print(solution(3)) # 1+2
print(solution(4)) # 1+3
print(solution(5)) # 1+4, 2+3
print(solution(6)) # 1+2+3, 1+5, 2+4
print(solution(7)) # 1+2+4, 1+6, 2+5, 3+4
print(solution(8)) # 1+2+5, 1+3+4, 1+7, 2+6, 3+5
print(solution(9)) # 1+2+6, 1+3+5, 2+3+4, 1+8, 2+7, 3+6, 4+5
print(solution(10)) # 1+2+3+4, 1+2+7, 1+3+6, 1+4+5, 2+3+5, 1+9, 2+8, 3+7, 4+6

Elegant Python code for Integer Partitioning

While this answer is fine, I'd recommend skovorodkin's answer.

>>> def partition(number):
...     answer = set()
...     answer.add((number, ))
...     for x in range(1, number):
...         for y in partition(number - x):
...             answer.add(tuple(sorted((x, ) + y)))
...     return answer
... 
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])

If you want all permutations(ie (1, 3) and (3, 1)) change answer.add(tuple(sorted((x, ) + y)) to answer.add((x, ) + y)

Find all unordered partitions of a list with a minimum number of elements

Here is one long-ish solution. No rejection is used in generating partitions, so in that sense this may be somewhat efficient. Still, there are lots of things to optimize.

Example:

list(get_partitions(range(3), 1))
# [[[0, 1, 2]], [[0], [1, 2]], [[1], [0, 2]], [[2], [0, 1]], [[0], [1], [2]]]

---

Here is an outline of how this works:

• First, it is useful to define a helper split function that takes a list lst and an integer n and return all ways to split the list into two groups, one of size n and another of size len(lst) - n.
• Second, we need to solve an easier version of the problem: how to split a list lst into n groups each of size k. Of course, this is only possible when len(lst) = n * k. This is implemented in get_partitions_same_size function. The idea is to always include the first element of lst in the first group and recurse.
• Third, we need to find all integer partitions of len(lst). I copied code from this thread.
• Fourth, for each integer partition p of len(lst), we need to find all ways to partition lst according to p.
  
  • For example, say len(lst) == 7 and p = 3 + 2 + 2. In this case, we can choose any three elements for the first group, any remaining two for the second group, and there is no choice to be made for the final third group.
  • This can introduce redundancy as we can get two partitions that only differ in the order of the last two groups.
  • To deal with this issue, we can represent a partition by counting the number of groups of each size. In this example, p corresponds to p_scheme = [(3, 1), (2, 2)]. The function get_partitions_helper takes in a list lst and a "partition scheme" p_scheme, and returns all corresponding partitions without double-counting. This is where get_partitions_same_size from step two is used.
• Finally, everything comes together in get_partitions: we loop over integer partitions of len(lst) and return all possible list partitions corresponding to each possible integer partition.

This is a fun problem and comments on bugs and optimizations are very welcome.

---

from itertools import combinations
from collections import Counter

# from this thread:
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning
def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

def split(lst, n):
  '''
  return all ways to split lst into two groups, 
  with n and len(lst) - n elements respectively
  '''
  assert len(lst) >= n
  # handle special case of len(lst) == 2 * n
  if len(lst) == 2 * n:
    for first, second in split(lst[1:], n-1):
      yield [lst[0], *first], second
  else:
    for comb in combinations(range(len(lst)), n):
      comb = set(comb)
      first = [x for i, x in enumerate(lst) if i in comb]
      second = [x for i, x in enumerate(lst) if i not in comb]
      yield first, second

def get_partitions_same_size(lst, n, k):
  # print(lst, n, k)
  'return all ways to partition lst into n parts each of size k up to order'
  if len(lst) != n * k:
    print(lst, n, k)
  assert len(lst) == n * k
  if n == 0 and len(lst) == 0:
    yield []
  # case when group size is one
  elif k == 1:
    yield [[x] for x in lst]
  # otherwise, without loss, the first element of lst goes into the first group
  else:
    for first, rest in split(lst[1:], k-1):
      for rec_call in get_partitions_same_size(rest, n-1, k):
        yield [[lst[0], *first], *rec_call]

def get_partitions_helper(lst, p_scheme):
  """
  return all ways to partition lst into groups according to a partition scheme p_scheme

  p_scheme describes an integer partition of len(lst)
  for example, if len(lst) == 5, then possible integer partitions are:
  [(5,), (1, 4), (1, 1, 3), (1, 1, 1, 2), (1, 1, 1, 1, 1), (1, 2, 2), (2, 3)]
  for each, we count the number of groups of a given size
  the corresponding partition schemes are:
  [[(5, 1)],
  [(1, 1), (4, 1)],
  [(1, 2), (3, 1)],
  [(1, 3), (2, 1)],
  [(1, 5)],
  [(1, 1), (2, 2)],
  [(2, 1), (3, 1)]]
  """
  if not lst and not p_scheme:
    yield []
    return 
  assert len(lst) == sum(a * b for a, b in p_scheme)
  group_size, group_count = p_scheme[0]
  num_elts = group_size * group_count
  for first, second in split(lst, num_elts):
    for firsts in get_partitions_same_size(first, group_count, group_size):
      for seconds in get_partitions_helper(second, p_scheme[1:]):
        yield [*firsts, *seconds]

def get_partitions(lst, min_):
  """
  get all partitions of lst into groups s.t. each group has at least min_ elements
  up to order (of groups and elements within a group)
  """
  for partition in partitions(len(lst), min_):
    p_scheme = list(Counter(partition).items())
    yield from get_partitions_helper(lst, p_scheme)

Generating integer partitions - Converting python code with yield to clojure

The Tupelo library has an implementation of Python's yield function. Here is a translation:

(ns tst.demo.core
  (:use tupelo.core )

(defn partitions [n]
  (lazy-gen
    (if (zero? n)
      (yield [])
      (doseq [p (partitions (dec n))]
        (yield (glue [1] p))
        (when (and (not-empty? p)
                (or (< (count p) 2)
                  (< (first p) (second p))))
          (yield (prepend (inc (first p))
                   (rest p))))))))

(partitions 4) => 
    ([1 1 1 1] [1 1 2] [2 2] [1 3] [4])

Generate restricted weak integer compositions (or partitions) of an integer n into k parts in Python

This kind of problem is most straightforward to solve with a recursive generator function. To generate partitions of n into k parts, we can select the first part v, and then recursively partition n - v into k - 1 parts.

You want earlier solutions to have larger numbers in the first position, so we'll choose v in descending order.

def constrained_partitions(n, k, min_elem, max_elem):
    allowed = range(max_elem, min_elem-1, -1)

    def helper(n, k, t):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield t + (n,)
        elif min_elem * k <= n <= max_elem * k:
            for v in allowed:
                yield from helper(n - v, k - 1, t + (v,))

    return helper(n, k, ())

Example:

>>> for p in constrained_partitions(5, 3, 0, 3):
...     print(p)
... 
(3, 2, 0)
(3, 1, 1)
(3, 0, 2)
(2, 3, 0)
(2, 2, 1)
(2, 1, 2)
(2, 0, 3)
(1, 3, 1)
(1, 2, 2)
(1, 1, 3)
(0, 3, 2)
(0, 2, 3)

Check if a number can be divided into prime partitions

The error lies in the second for loop. You are looping through possible primes x, and wish to then check that y = num - x is also prime.

The error in your logic is that in the second for loop, if the first element in the loop y = num - x is not prime, it will return False, without checking any of the other possible values.

You could correct this by moving the return False statement out one loop, but since you have already generated a list of primes less than num, primelist (and since y = num - x, (if prime y exists) it will be in this list), you can just check for membership of the list:

    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
        # If no such y is prime, not possible
        else:
            return False

Note: I would advise making the logic of your script more modular, separating out the prime list generator into its own function:

def partition(num):
    """
    Return True if there exist primes x,y such that num = x + y.
    Else return False.
    """
    primelist = primes(num)
    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
    # If no such y is prime, not possible
    else:
        return False

def primes(num):
    """Return list of all primes less than num."""
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)
    return primelist

---

Related Topics