https://kotlinlang.org logo
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()
			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?
d

Dominaezzz

01/11/2020, 2:08 PM
Since we're talking subsets, I say the data structure to use would be
Set<T>
instead of
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()
            currentSubsetCopy.add(get(i))
            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