Skip to content

Instantly share code, notes, and snippets.

@FrancescoJo
Last active February 16, 2019 07:32
Show Gist options
  • Save FrancescoJo/ee62c94a050c6cc6122438092b430a53 to your computer and use it in GitHub Desktop.
Save FrancescoJo/ee62c94a050c6cc6122438092b430a53 to your computer and use it in GitHub Desktop.
Logic to yield all `nCr` combinations
/**
* This logic demonstrates how to draw all nCr combinations from given set.
* The time complexity of this logic is O(n²).
* Actual logic invocations are 1/2((n - 2)² + r(n - 2) + 2), where n > 2.
*
* Imagine selecting 3 different numbers from a set which has 4 different
* numbers. Assume that we've given a set as follows:
*
* let dataSet = {1, 2, 3, 4}
*
* then all of the possible combinations are:
*
* {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
*
* in this case, n=4, r=3.
*
* To test:
* ```
* combinations(arrayListOf(1, 2, 3, 4), 3, 0L)
* ```
*/
fun <T> combinations(dataSet: Collection<T>, r: Int, empty: T): List<List<T>> {
if (r > dataSet.size) {
throw IllegalArgumentException("Number of samples(r=$r) must be " +
"smaller than objects count(${dataSet.size})!!")
}
val emptyPicked = ArrayList<T>(r).apply {
for (i in 0 until r) {
add(empty)
}
}
return combinationsInternal(ArrayList(dataSet), r, 0, emptyPicked)
}
private fun <T> combinationsInternal(indexedSet: List<T>, r: Int,
start: Int, picked: MutableList<T>): List<List<T>> {
if (r == 0) {
return ArrayList<List<T>>().apply {
add(ArrayList<T>(picked))
}
}
val results = ArrayList<List<T>>()
for (i in start..indexedSet.size - r) {
picked[picked.size - r] = indexedSet[i]
val selected = allCombinationsInternal(indexedSet, r - 1, i + 1, picked)
if (selected.isNotEmpty()) {
results.addAll(selected)
}
}
return results
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment