Combination generation is a math concept. Given an n and k, how many combinations of k that can be picked from n-th elements, irrespective of the order (i.e. [1, 2, 3] is regarded the same as [3, 1, 2])? Also what are the actual combination sets?
As an example, with n = 5, and k = 3, the number of combination is 10, and the generated combinations are:
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
This demo application build a combination generation library based on the algorithm suggested by Dr. James McCaffrey. What's nice about the implementation are:
-
Returns an iterator so it doesn't take up as much memory space as when generating all the combination up front. The generated combination set grows very fast. with n = 30, k = 10, the total combination is: 3,0045,015.
-
With a speicified
m-th element, this library can return only that single element of the combination set based on its lexicographical order. This is also based on the algorithm suggested by Dr. James McCaffrey.
The implementation of the combination library. I encountered this programming problem when I was solving Day 22 of Advent of Code.