Questions tagged [integer-partitions]

Partitions of an integer n are different ways of writing n as sum of smaller integers.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
91 views

Integer decomposition algorithm

Suppose I have a 32-bit integer $x$, I want to find $\{ x_i \}_{i \in 1\dots\ell}$ such that $x = e + \sum_{i=1}^\ell x_i \cdot 2^{32 - B\cdot i}$ where the error $e$ is as small as possible. The ...
lamba's user avatar
  • 107
5 votes
0 answers
100 views

Optimization problem with discrete and continuous components

Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between ...
dpalma's user avatar
  • 265
3 votes
2 answers
415 views

Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...
Samuel Bismuth's user avatar
1 vote
1 answer
50 views

Does this Qualify as Sub-Exponential?

I don't have a strong CS background so apologies if the question is trivially simple: So I am working on an algorithm, say $A(n)$ , which runs over all integer partitions of $n$. Now the algorithm ...
SagarM's user avatar
  • 173
0 votes
0 answers
115 views

prove that Integer partition problem is NP complete using Hamiltonian Cycle

Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete My Thoughts : Integer paritition problem is about partitioning a given set of integers into two ...
Amit wadhwa's user avatar
0 votes
0 answers
66 views

Efficient triangular decomposition of an integer

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right? Its specification is that if I do (q, r) = f(n, d), I get ...
iago-lito's user avatar
  • 195
0 votes
0 answers
40 views

Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
giulioandreolli's user avatar
3 votes
1 answer
1k views

Number of ways n can be written as sum of at least two positive integers

I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. ...
ktm5124's user avatar
  • 173
4 votes
2 answers
172 views

A problem on constrained combinatorics

Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics). I'm looking for ...
mavzolej's user avatar
  • 177
1 vote
2 answers
128 views

A physical algorithm that finds all integer partitions of a number

If this is not the right forum for this question let me know. I am looking for a physical algorithm that can be easily followed by anyone not knowing much ...
user13107's user avatar
  • 119
0 votes
1 answer
99 views

sub-optimal but fast partition generation

I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ...
user_1_1_1's user avatar
1 vote
1 answer
119 views

Given a valid combination, how to get its index in the sequence of integer partition

This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that ...
Li Wang's user avatar
  • 33
1 vote
3 answers
2k views

Divide N sticks among M boys as homogeneously as possible (ignoring order)

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is ...
user_1_1_1's user avatar
2 votes
0 answers
98 views

Generating a distinct k-partition of n

Let us consider a specific case of an extended Kakuro puzzle. Given an integer $n$, we must form $n$ as the sum of $k$ distinct positive integers each less than or equal to $r$. From a mathematical ...
Samurdhi Karunarathne's user avatar
5 votes
1 answer
222 views

Practical Implementation for Refinement Order on Integer Partitions

The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ ...
Martin Rubey's user avatar
2 votes
1 answer
143 views

Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering

Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins. Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\{0,...
R B's user avatar
  • 2,624
1 vote
1 answer
1k views

Applications in Computer Sciences of Partition Functions

A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$. These were studied ...
user13675's user avatar
  • 1,614
5 votes
4 answers
3k views

Divide an integer into the sum of consecutive positive numbers

Today I am trying to solve an classical problem: For any $n\in \Bbb{N}^+$, If it can be represent as the sum of consecutive positive numbers, find out them. For example: $$15 = 1+2+3+4+5$$ $$15=...
Laura's user avatar
  • 291