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". ...
- 5,239
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
- 538
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
- 3,965
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 ...
- 47.4k
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 ...
-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&...
- 2,685
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} = ...
- 13.4k
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
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. ...
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$...
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}$ ...
- 65.2k
-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$;
...
- 77k
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. ...
- 7,408
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 ...
- 5,809