l

LastExceed

01/11/2020, 2:03 PM
I tried to write a generic extension function for lists that returns all subsets of a given size that would be :
Copy code
``````fun main() {
val elements = listOf('A', 'B', 'C', 'D', 'E', 'F')
val subsets = elements.getAllSubsets(3)
subsets.forEach {
println(it)
}
}``````
desired output:
Copy code
``````[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:
Copy code
``````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()
if (remaining == 0) {
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?
d

Dominaezzz

01/11/2020, 2:08 PM
Since we're talking subsets, I say the data structure to use would be
``Set<T>``
``List<T>``
.
Take advantage of closure by moving
``val results = mutableListOf<List<T>>()``
to the top of the function. Then don't pass it down to the helper functions.
l

LastExceed

01/11/2020, 2:10 PM
the former is a good idea, but the latter isn't possible because the compiler can't be sure that the type params of the 2 functions are the same
or maybe i just did it wrong?
d

Dominaezzz

01/11/2020, 2:11 PM
Remove the
``<T>``
from the inner function.
l

LastExceed

01/11/2020, 2:12 PM
oh right didn't think of that. ty
hmm
``Set<T>``
isn't indexable, how do I deal with the line
Copy code
``currentSubsetCopy.add(elements[i])``
since
``elements[i]``
now gives an error?
d

Dominaezzz

01/11/2020, 2:17 PM
Also, you don't need the
``elements``
param. You can do `
Copy code
``val elements: List<T> = this``
at the top.
Uhhh, not sure.
l

LastExceed

01/11/2020, 2:18 PM
guess i'll just stick with lists then
d

Dominaezzz

01/11/2020, 2:19 PM
You could do
Copy code
``results.add(currentSubsetCopy.toSet())``
l

LastExceed

01/11/2020, 2:20 PM
``val elements: List<T> = this``
is a good idea, but couldn't i just inline
``this``
and get rid of the
``elements``
parameter altogether?
d

Dominaezzz

01/11/2020, 2:21 PM
Might as well. Which-ever is easier to read.
I also recommend using sequences. That way you don't have to worry too much about stackoverflow.
Copy code
``````fun <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()
if (remaining == 0) {
yield(currentSubsetCopy.toList())
continue
}
yieldSubsetsRecursive(currentSubsetCopy, remaining - 1, i + 1)
}
}
yieldSubsetsRecursive(mutableListOf(), size - 1, 0)
}``````
l

LastExceed

01/11/2020, 2:35 PM
ok thanks for your help so far, i need some time to wrap my head around sequences
m

molikuner

01/11/2020, 3:19 PM
Copy code
``````fun <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.
2 Views