LastExceed
01/11/2020, 2:03 PMfun main() {
val elements = listOf('A', 'B', 'C', 'D', 'E', 'F')
val subsets = elements.getAllSubsets(3)
subsets.forEach {
println(it)
}
}
desired output:
[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]
here's my implementation:
fun <T> List<T>.getAllSubsets(size: Int): List<List<T>> {
fun <T> getAllSubsetsRecursive(
elements: List<T>,
currentSubset: MutableList<T>,
remaining: Int,
minimumIndex: Int,
results: MutableList<List<T>>
) {
for (i in minimumIndex until elements.size - remaining) {
val currentSubsetCopy = currentSubset.toMutableList()
currentSubsetCopy.add(elements[i])
if (remaining == 0) {
results.add(currentSubsetCopy.toList())
continue
}
getAllSubsetsRecursive(
elements,
currentSubsetCopy,
remaining - 1,
i + 1,
results
)
}
}
val results = mutableListOf<List<T>>()
getAllSubsetsRecursive(
this,
mutableListOf(),
size - 1,
0,
results
)
return results.toList()
}
it does the job, however this still feels a bit verbose and messy to me, especially considering how often I create a copy of a list.
is there any cleanup potential here?Dominaezzz
01/11/2020, 2:08 PMSet<T>
instead of List<T>
.val results = mutableListOf<List<T>>()
to the top of the function. Then don't pass it down to the helper functions.LastExceed
01/11/2020, 2:10 PMDominaezzz
01/11/2020, 2:11 PM<T>
from the inner function.LastExceed
01/11/2020, 2:12 PMSet<T>
isn't indexable, how do I deal with the line
currentSubsetCopy.add(elements[i])
since elements[i]
now gives an error?Dominaezzz
01/11/2020, 2:17 PMelements
param. You can do `
val elements: List<T> = this
at the top.LastExceed
01/11/2020, 2:18 PMDominaezzz
01/11/2020, 2:19 PMresults.add(currentSubsetCopy.toSet())
LastExceed
01/11/2020, 2:20 PMval elements: List<T> = this
is a good idea, but couldn't i just inline this
and get rid of the elements
parameter altogether?Dominaezzz
01/11/2020, 2:21 PMfun <T> List<T>.getAllSubsets(size: Int): Sequence<List<T>> = sequence {
suspend fun SequenceScope<List<T>>.yieldSubsetsRecursive(
currentSubset: MutableList<T>,
remaining: Int,
minimumIndex: Int
) {
for (i in minimumIndex until size - remaining) {
val currentSubsetCopy = currentSubset.toMutableList()
currentSubsetCopy.add(get(i))
if (remaining == 0) {
yield(currentSubsetCopy.toList())
continue
}
yieldSubsetsRecursive(currentSubsetCopy, remaining - 1, i + 1)
}
}
yieldSubsetsRecursive(mutableListOf(), size - 1, 0)
}
LastExceed
01/11/2020, 2:35 PMmolikuner
01/11/2020, 3:19 PMfun <T> Collection<T>.subsets(subsetLength: Int): List<List<T>> {
require(subsetLength >= 0) { "Can't create subsets with negative amount of elements!" }
if (this.size < subsetLength || subsetLength == 0) return emptyList()
val element = this.first()
val reduced = this.drop(1)
val subSubsets = if (subsetLength > 1) reduced.subsets(subsetLength - 1) else listOf(emptyList())
return subSubsets.map { it + element } + reduced.subsets(subsetLength)
}
Don’t know whether you like this more, but thats what I got after trying to solve this.