All Questions
Tagged with integer-partitions algorithms
37
questions
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 ...
- 757
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 ...
- 3,445
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
9
votes
1
answer
762
views
Maximal Zero Sums Partition
You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
- 93
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
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
- 419
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
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
4
votes
2
answers
11k
views
Median of medians algorithm
I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
My ...
- 197
4
votes
4
answers
1k
views
Algorithm to partition sum between buckets in all unique ways
The Problem
I need an algorithm that does this:
Find all the unique ways to partition a given sum across 'buckets' not caring about order
I hope I was clear reasonably coherent in expressing ...
- 911
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 ...
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
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 ...
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
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