Find combinations of non-repeating integers summing to a certain number
1 Ansicht (letzte 30 Tage)
Ältere Kommentare anzeigen
Daniel
am 1 Okt. 2015
Kommentiert: Daniel
am 2 Okt. 2015
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 Kommentare
Akzeptierte Antwort
John D'Errico
am 2 Okt. 2015
Bearbeitet: John D'Errico
am 2 Okt. 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.
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Matrices and Arrays finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!