Questions tagged [integer-partitions]
Partitions of an integer n are different ways of writing n as sum of smaller integers.
19 questions
0
votes
1
answer
59
views
Set partitions and integer partitions
Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
- 101
0
votes
1
answer
195
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 ...
- 109
5
votes
0
answers
129
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 ...
- 265
3
votes
2
answers
671
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:
...
- 269
1
vote
1
answer
113
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 ...
- 183
1
vote
0
answers
172
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 ...
- 59
0
votes
0
answers
104
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 ...
- 205
1
vote
0
answers
66
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 ...
3
votes
1
answer
2k
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. ...
- 173
4
votes
2
answers
237
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 ...
- 177
1
vote
2
answers
196
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 ...
- 119
0
votes
1
answer
134
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. ...
- 163
1
vote
1
answer
183
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 ...
- 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 ...
- 163
2
votes
0
answers
116
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 ...
