CODEWITHSUNDEEP
kotlinpermutation
Nick Borisenko
Nick Borisenko

Reputation: 65

Iterating stepwise through permutations of arbitrary sets in Kotlin

I'm trying to find an elegant way to iterate stepwise through all possible permutations of an arbitrary number of sets, or "buckets". I need to do it stepwise because I'm dealing with a great number of possible permutations, and have been running out of memory space trying to store all permutations in memory and then weed out the ones that are invalid. Instead, I am trying to step through each permutations one at a time, and only store it in a final list in memory if it's valid, so that I can save some memory space.

I've been trying to write out a manual solution for this, and it's proven to be a bit difficult - I don't want to know exactly how many lists/sets I'm dealing with, so I can't take the brute force approach of creating a series of nested for loops. Creating a custom iterator for this has proven to be its own set of challenges.

I was hoping that there would be some built-in methods or tools I can leverage for this without reinventing the wheel.

Here is an example: Let's say I have a couple sets of letters:

[a, b, c], [n, c, a]

And my goal is to find all possible permutations of letters from these two "buckets", but only those that do not have duplicates in their sets (in a real world example there could be more complex requirements, just using this simple one for the sake of the example). So all possible permutations are: 

[a, n], [a, c], [a, a], 
[b, n], [b, c], [b, a],
[c, n], [c, c], [c, a].

Now that I have all possible permutations, I want to weed out the ones that don't satisfy the requirements: [a, a] and [c, c].

Rather than weeding those out after the fact (and taking up space in temporary memory where it could otherwise be filled by a valid combination), I want to check at each created permutation if it's valid before storing it in memory.

Is there anything built into Kotlin that'd make this easier?

EDIT: I was able to figure out how I could do this by creating my own "iterator" class that steps through each permutation, and "bubbles up" if the final set has been looped through completely, in order to make sure I hit each permutation. I can post the solution here if anyone in interested by the (probably slightly inefficient) solution, but I would still like to know if there was an easier way to do this using some built in Kotlin tools.

Upvotes: 0

Views: 483

Answers (1)

gidds
gidds

Reputation: 18577

If I understand the question, what you're asking for is the Cartesian product of sets.  (‘Permutations’ usually refers to different orderings of all the elements of a single set, or of subsets thereof.)

Doing this directly is easy, using map() and flatMap():

operator fun <T, U> Iterable<T>.times(other: Iterable<U>)
    = flatMap{ a -> other.map{ b -> a to b }}

(operator fun… times is a bit of magic that lets you overload the * operator.  T and U are type parameters, so this will work for sets of any type.  And to is an easy way to construct a Pair.)

However, as you say, that creates a list of results, and if you want to do any filtering or other post-processing, that would create another.

The usual way to avoid that is to use sequences.  (Equivalent to Java streams.)  These are lazy structures, in which elements are only evaluated when needed.

Normally it's as easy as adding .asSequence() to the list, but because we have two of them here, it's rather tricker…  Here's one way:

operator fun <T, U> Iterable<T>.times(other: Iterable<U>): Sequence<List<Pair<T, U>> {
    val otherSeq = other.asSequence()
    return asSequence().flatMap{ a -> otherSeq.map{ b -> a to b }}
}

That returns a Sequence, so you can do any filtering or other post-processing you want, and then call a terminal operation such as toList() afterward to actually perform the computation:

val result = (setOf('a', 'b', 'c') * setOf('n', 'c', 'a'))
            .filter{ it != 'a' to 'a' && it != 'c' to 'c' }
            .toList()
println(result)
// prints: [(a, n), (a, c), (b, n), (b, c), (b, a), (c, n), (c, a)]

(I'm not too experienced with sequences, so I'm not guaranteeing that's the most efficient way…)

Upvotes: 2

Related Questions