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
295
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$...
- 74.9k
-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
292
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
528
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