I tried to write a generic extension function for ...

# announcements

[LastExceed]

I tried to write a generic extension function for lists that returns all subsets of a given size that would be :

fun 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]

Since we're talking subsets, I say the data structure to use would be Set<T> instead of List<T> .

[Dominaezzz]

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.

[LastExceed]

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

[LastExceed]

or maybe i just did it wrong?

[Dominaezzz]

Remove the <T> from the inner function.

[LastExceed]

oh right didn't think of that. ty

[LastExceed]

hmm Set<T> isn't indexable, how do I deal with the line

currentSubsetCopy.add(elements[i])

since elements[i] now gives an error?

[Dominaezzz]

Also, you don't need the elements param. You can do `

val elements: List<T> = this

at the top.

[Dominaezzz]

Uhhh, not sure.

[LastExceed]

guess i'll just stick with lists then

[Dominaezzz]

You could do

results.add(currentSubsetCopy.toSet())

[LastExceed]

val elements: List<T> = this
is a good idea, but couldn't i just inline this and get rid of the elements parameter altogether?

[Dominaezzz]

Might as well. Which-ever is easier to read.

[Dominaezzz]

I also recommend using sequences. That way you don't have to worry too much about stackoverflow.

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)
}

[LastExceed]

ok thanks for your help so far, i need some time to wrap my head around sequences

[molikuner]

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.