Find combinations of non-repeating integers summing to a certain number
1 visualizzazione (ultimi 30 giorni)
Mostra commenti meno recenti
Given a number x, I would like to find all non-repeating combinations of integers in range 1:n that form a vector of length m whose elements sum to x.
For example: x = 9; n = 6; m = 3;
Should return: [4 3 2] [5 3 1] [6 2 1]
This will be used many times with an n ~ 100, and needs to be general for any x or m, so the method should be as efficient as possible.
0 Commenti
Risposta accettata
John D'Errico
il 2 Ott 2015
Modificato: John D'Errico
il 2 Ott 2015
Using my partitions code...
partitions(9,1:6,1,3)
ans =
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 1
A 1 in any row indicates that element appears in the sum.
For a larger problem, here are the set of all solutions with a sum of 100, 3 elements in the sum, from the set 1:60. 423 possible solutions.
sols = partitions(100,1:60,1,3);
size(sols)
ans =
423 60
partitions can be found on the file exchange.
Of course, it is trivial to create an impossibly large problem, but partitions is reasonably efficient on rationally sized problems.
Più risposte (0)
Vedere anche
Categorie
Scopri di più su Matrices and Arrays in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!