Stack Overflow
Stack Overflow

Questions tagged [integer-partition]

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.)

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.)

References:

47 questions
27
votes
4 answers

Integer Partition (algorithm and recursion)

Finding how many combinations of a sum number (the variable n in code). For ex.: 3 = 1+1+1 = 2+1 = 3 => ANS is 3 5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 => ANS is 7 In the following example, m is the max number and n is sum, the…
PlusA
  • 545
  • 1
  • 6
  • 15
25
votes
4 answers

Python Integer Partitioning with given k partitions

I'm trying to find or develop Integer Partitioning code for Python. FYI, Integer Partitioning is representing a given integer n as a sum of integers smaller than n. For example, an integer 5 can be expressed as 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1…
user2211319
15
votes
6 answers

Is there an efficient algorithm for integer partitioning with restricted number of parts?

I have to create a method that takes two integers, let them be n and m, and returns how many ways there are to sum m positive numbers to get n. For example, a method call like this partition(6, 2) should return 3 because there are 3 ways possible.…
Renat Kaitmazov
  • 245
  • 3
  • 10
10
votes
3 answers

conjugate integer partitions in place

I'm building a C++ library that includes a Partitions class. I'm trying to implement conjugation (explained below) in place, and I cannot get it to work. My class members are: size_t _size; size_t _length; std::vector _parts; As an example,…
PengOne
  • 48,188
  • 17
  • 130
  • 149
9
votes
2 answers

Find the lexicographic order of an integer partition

For permutations, given N and k, I have a function that finds the kth permutation of N in lexicographic order. Also, given a permutation perm, I have a function that finds the lexicographic index of the permutation among all permutations of N. To do…
Daniel
  • 944
  • 1
  • 7
  • 24
6
votes
2 answers

Generating integer partition by its number

I'm trying to generate decent partition of given integer number N numbered K in lexicographical order, e.g. for N = 5, K = 3 we got: 5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 1 + 1 + 2 5 = 1 + 1 + 3 5 = 1 + 2 + 2 5 = 1 + 4 5 = 2 + 3 5 = 5 And the third one is…
siziyman
  • 61
  • 3
5
votes
3 answers

All possible permutations of decimal numbers (hundredths) that sum up to 1 for a given length

Consider vector s as follows: s=seq(0.01, 0.99, 0.01) > s [1] 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 .......... 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 Now given s and a fixed length m, I would like to have a matrix for all…
989
  • 12,579
  • 5
  • 31
  • 53
4
votes
3 answers

Rank of Partition with specific length

How can I determine the rank/index of a partition of integer n with length k? For instance, if n=10 and k=3, the possible partitions (sorted in reverse lexicographic order) are: 0 (8, 1, 1) 1 (7, 2, 1) 2 (6, 3, 1) 3 (6, 2, 2) 4 (5, 4, 1) 5 (5, 3,…
Biereagu Sochima
  • 510
  • 6
  • 13
4
votes
4 answers

Partition of an Integer + Number of partitions

A partition of an integer n is a way of writing n as a sum of positive integers. For example, for n=7, a partition is 1+1+5. I need a program that finds all the partitions of an integer 'n' using 'r' integers. For example, all the partitions of n=7…
user3519448
  • 111
  • 1
  • 9
3
votes
1 answer

variable number of dependent nested loops

Given two integers n and d, I would like to construct a list of all nonnegative tuples of length d that sum up to n, including all permutations. This is similar to the integer partitioning problem, but the solution is much simpler. For example for…
Nico Schlömer
  • 53,797
  • 27
  • 201
  • 249
3
votes
1 answer

Unique permutations of fixed length integer partitions where each element has a maximum

This question is similar to a question I had several months ago: Generating a numpy array with all combinations of numbers that sum to less than a given number. In that question, I wanted to generate all numbers that summed to at most a constant,…
Forzaa
  • 1,465
  • 4
  • 15
  • 27
2
votes
3 answers

Optimize: Restricted integer partioning with max value

with the following code, I count the restricted integer partitions(each number can only occure once in each partition) with k numbers in each partition, each number is equal or greater than 1 and not greater than m. This code generate a lot of cache…
TTho Einthausend
  • 609
  • 4
  • 13
2
votes
2 answers

Count integer partions with k parts, each below some threshold m

I want to count the number of ways we can partition the number n, into k distinct parts where each part is not larger than m. For k := 2 i have following algorithm: public int calcIntegerPartition(int n, int k, int m) { int cnt=0; for(int i=1;…
TTho Einthausend
  • 609
  • 4
  • 13
2
votes
2 answers

Distinct partitions of an integer excluding repetitious combinations

I found this code online somewhere and I'm trying to make sense of how it works. You supply the partitions() function with an integer and the code returns the number of distinct partitions that do NOT include repeating numbers (e.g. n = 5 -> 2…
wsmyth
  • 69
  • 7
2
votes
1 answer

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

(Re-posting, as I did not get any response to my previous post) I am trying to write a Python code to generate weak integer compositions (partitions) of a number 'n' into 'k' parts but with a MINIMUM and MAXIMUM value constraint on each partition…
Aman_X
  • 87
  • 8
1
2 3 4