All Questions
Tagged with integer-partitions algorithms
37
questions
1
vote
1
answer
62
views
Computing integer partitions subject to certain constraints
Context:
I am programming a videogame.
Background:
Let $I$ be a set of named items such that each is assigned a difficulty score, and each is tagged either as "food" or "obstacle". ...
- 1,312
0
votes
1
answer
63
views
Integer partition weighted minimum of maximum
Given a non-negative integer $n$ and a positive real weight vector $w$ with dimension $m$, partition $n$ into a length-$m$ non-negative integer vector that sums to $n$ (call it $v$) such that $\max ...
- 183
3
votes
0
answers
86
views
Given $n\in\mathbb{N}_{\geqslant 2}$, find the partition $(a_1,...,a_k)\in\mathbb{N}^k:\sum_{i=1}^k a_i=n$ of $n$ that maximizes $\prod_{i=1}^k a_i$
I am a solving programming question in Leetcode in which, given a number $n \in \mathbb{N}_{\geqslant 2}$, I have to find $(a_1, ..., a_k) \in \mathbb{N}^k$ such that $k \in \mathbb{N}$, $2 \leqslant ...
1
vote
0
answers
298
views
An algorithm to generate all unique combinations of addends for a sum, from a range of small addends which are greater than 1?
I'm looking for an algorithm to generate all unique combinations of addends for a given sum, within a certain given range of addends. The size of the sum could range from two digits to five digits, ...
- 11
1
vote
1
answer
58
views
Proving injectivity for a function between sets of different types of partitions
I am attempting to solve the following problem:
Let $A$ be the set of partitions of $n$ with elements $(a_1, \dots, a_s)$ such that $a_i > a_{i+1}+a_{i+2}$ for all $i < s,$ taking $a_{s+1} = ...
- 5,230
1
vote
0
answers
42
views
Algorithm to find the distinct representations of the integer $n$ as a sum of $k$ non-negative p^(th) integer powers.
I am a user of Wolfram Mathematica and in that software there is a function called: PowersRepresentations. This function returns lists of integers $0\le n_1\le n_2\le\dots\le n_k$ such that $n_1^p+n_2^...
- 21
7
votes
2
answers
126
views
A sum of partitions
A friend of mine presented a problem I found interesting:
Compute the following: $$\sum_{n=0}^\infty\left(\prod_{k=1}^j(1+x^k)\right)[x^{mn}]$$ where $P(x)[x^n]$ denotes the $x^n$ coefficient of $P$...
-6
votes
1
answer
517
views
list partitions (python) - why is the index out of range? [closed]
General problem: Using the elements of some list of length $m* n$, create a list with $m$ sub-lists, each of length $n$.
In my case, $m= 10 > n=3$.
The final output should be a list ("lis1&...
- 1
0
votes
1
answer
86
views
Why does this definition of the 3-PARTITION problem imply that every set contains exactly 3 elements?
I have the following definition of the 3-PARTITION problem taken from this paper: https://www.sciencedirect.com/science/article/pii/0166218X93900853
Given $3m$ positive integers $a_1, a_2,...,a_{3m}$ ...
- 197
-1
votes
1
answer
1k
views
Represent $N$ as the sum of exactly $K$ distinct positive integers
You are given two integers $N$ and $K$. Find all ways to represent $N$ as the sum of exactly $K$ distinct positive integers $x_1,x_2, \ldots,x_K$ — in other words.
$xi_>0$ for each valid $i$;
...
5
votes
1
answer
103
views
Sharing a pie evenly among an unknown number of people. [duplicate]
This is a question inspired by the question "Nine gangsters and a gold bar" on the Puzzling Stack Exchange.
Suppose you're throwing a party, and you know that either 7, 8, or 9 people will arrive. ...
- 5,072
1
vote
1
answer
73
views
Non-greedy method of partitioning numbers
I want to find an example of where a non-greedy method of partitioning numbers is better than the greedy method. The greedy method would be to partition them so that you group as many numbers as ...
- 93
0
votes
2
answers
293
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 ...
- 417
4
votes
1
answer
1k
views
How to turn number into sum of unique primes?
I have to find algorithm which find prime number less than $n$ which is sum of the largest amount of unique primes, for example for $n=81$, the answer is $79 = 3 + 5 + 7 + 11 + 13 + 17 + 23$.
I have ...
2
votes
1
answer
531
views
Number of integer partitions
Let's $N$ be a positive integer and $P$ - set of all possible partitions of the $N$, where $p = (a_1,a_2,...,a_n)$ with $a_1\le a_2 \le ... \le a_n$ and $a_1+a_2+...+a_n = N$. Let's $A$ be the number ...
- 53
0
votes
2
answers
119
views
Fastest algorithm for splitting an integer
I have a number $n$ in the range $1$ - $255$. What I'm trying to do is split $n$ into the shortest list of numbers $1$ -$16$ that add up to $n$. For example, let's say $n$ is $32$. Then, we could ...
- 4,954
0
votes
1
answer
113
views
An algorithm for the set of subsets with equal sums of a set of numbers (distinct partitions)
Given a set $T\subset\mathbb N^+$ called the set of terms and let $T_n=\{k\in T|k\leq n\}$.
I want to design an efficient algorithm computing the set $\mathcal S_n$ of all subsets $S\subseteq T$ such ...
- 13.9k
1
vote
1
answer
2k
views
Partitions Into at Least Two Distinct Parts
I am looking for a formula/algorithm to give me the distinct (I might be using this term wrong) partitions of number N if it meets the following conditions:
all I need is the number of partitions ...
- 113
2
votes
3
answers
2k
views
Algorithm for the number of partitions of $n$ into distinct parts
I am looking for an algorithm to find the number of ways of writing $n$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. ...
- 65
1
vote
1
answer
49
views
How we can partition $a_1, a_2, a_3, ... a_n$ in two sequence X and Y such that their sum of differences be minimum?
I couldn't write any algorithm that can do this in good order for $a_i < 100$ and $n < 2000$ :(
how we can partition $a_1, a_2, a_3, ... a_n$ in two sequence X and Y such that $|X_1 - X_2| + |...
1
vote
4
answers
669
views
Is there any Algorithm to Write a Number $N$ as a Sum of $M$ Natural Numbers?
I have a number $N$ (for example $N=64$).
Is there any algorithm to find all the feasible ways for writing the number $N$ as a sum of $M$ positive numbers?
(For example $M=16$) --- Repetition is ...
- 2,123
3
votes
0
answers
1k
views
How to make a canonical coin system so that greedy solution is the only optimal solution for change-making problem
Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general.
We say that a coin system of coins canonical if the greedy algorithm to the coin ...
- 31
1
vote
1
answer
110
views
Tool for the partition problem with planar rectangles
The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed ...
- 23.1k
1
vote
1
answer
3k
views
Coin Change Problem with Fixed Coins
Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins.
...
- 61
1
vote
1
answer
55
views
What is the name of the transform which finds the number of ways to make partitions of the given sizes?
I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
- 32.3k
4
votes
0
answers
93
views
Counting the number of partitions that are a distance d away from a fixed partition.
Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
- 41
1
vote
1
answer
973
views
Find all Combinations of 1 and 2 which sums up to k.
I have two numbers $1$ and $2$. I have to print all ordered combinations which sums up to $k$.
For example:
$k=1$ Its only $1$.
$k=2$ It's ${1,1},{2}$.
$k=3$ Its ${1,1,1},{1,2},{2,1}$
What ...
- 133
2
votes
0
answers
127
views
Integer partitions without rotated solutions?
I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of (...
- 35k
5
votes
3
answers
2k
views
Number of ways of partitioning a number $n$ in unique ways.
Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater ...
- 4,512
0
votes
1
answer
119
views
General term of this sequence
I wanted to know the General term or the function to generate this sequence I found on OEIS.
It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
- 827