kotlin-itertools

Multiplatform combinatoric sequences for Kotlin, inspired by python-itertools.

Initially built as part of my solutions for Advent of Code 2023.

Installation

repositories {
    mavenCentral()
}

dependencies {
    implementation("com.michael-bull.kotlin-itertools:kotlin-itertools:1.0.0")
}

Usage

Combinations

Returns a sequence that yields length-sized combinations from this list.

The combination tuples are emitted in lexicographic order according to the order of this list.

fun <T> List<T>.combinations(length: Int = size): Sequence<List<T>>

fun <T> List<T>.pairCombinations(): Sequence<Pair<T, T>>

fun <T> List<T>.tripleCombinations(): Sequence<Triple<T, T, T>>

import com.github.michaelbull.itertools.combinations
import com.github.michaelbull.itertools.pairCombinations
import com.github.michaelbull.itertools.tripleCombinations

// [[A, B], [A, C], [A, D], [B, C], [B, D], [C, D]]
fun example1(): List<List<Char>> {
    return "ABCD".toList()
        .combinations(length = 2)
        .toList()
}

// [(A, B), (A, D), (A, C), (B, D), (B, C), (D, C)]
fun example2(): List<Pair<Char, Char>> {
    return "ABDC".toList()
        .pairCombinations()
        .toList()
}

// [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
fun example3(): List<Triple<Int, Int, Int>> {
    return (0..3).toList()
        .tripleCombinations()
        .toList()
}

Permutations

Returns a sequence that yields length-sized permutations from this list.

The permutation tuples are emitted in lexicographic order according to the order of this list.

fun <T> List<T>.permutations(length: Int = size): Sequence<List<T>>

fun <T> List<T>.pairPermutations(): Sequence<Pair<T, T>>

fun <T> List<T>.triplePermutations(): Sequence<Triple<T, T, T>>

import com.github.michaelbull.itertools.permutations
import com.github.michaelbull.itertools.pairPermutations
import com.github.michaelbull.itertools.triplePermutations

// [[A, B], [A, C], [A, D], [B, A], [B, C], [B, D], [C, A], [C, B], [C, D], [D, A], [D, B], [D, C]]
fun example1(): List<List<Char>> {
    return "ABCD".toList()
        .permutations(length = 2)
        .toList()
}

// [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
fun example2(): List<Pair<Int, Int>> {
    return (0..2).toList()
        .pairPermutations()
        .toList()
}

// [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
fun example3(): List<Triple<Int, Int, Int>> {
    return (0..2).toList()
        .triplePermutations()
        .toList()
}

Cartesian Product

Returns a sequence that yields the Cartesian product of the input iterables/lists.

The product tuples are emitted in lexicographic order according to the order of this iterable/list.

fun <A, B> Iterable<A>.product(other: Iterable<B>): Sequence<Pair<A, B>>
fun <A, B, C> Iterable<A>.product(first: Iterable<B>, second: Iterable<C>): Sequence<Triple<A, B, C>>

fun <A, B> Pair<Iterable<A>, Iterable<B>>.product(): Sequence<Pair<A, B>>
fun <A, B, C> Triple<Iterable<A>, Iterable<B>, Iterable<C>>.product(): Sequence<Triple<A, B, C>>

fun <T> List<List<T>>.product(): Sequence<List<T>>

import com.github.michaelbull.itertools.product

// [(A, x), (A, y), (B, x), (B, y), (C, x), (C, y), (D, x), (D, y)]
fun example1(): List<Pair<Char, Char>> {
    val a = "ABCD".toList()
    val b = "xy".toList()
    return a.product(b).toList()
}

// [(A, C, E), (A, C, F), (A, D, E), (A, D, F), (B, C, E), (B, C, F), (B, D, E), (B, D, F)]
fun example2(): List<Triple<Char, Char, Char>> {
    val a = "AB".toList()
    val b = "CD".toList()
    val c = "EF".toList()

    return Triple(a, b, c)
        .product()
        .toList()
}

// [[A, x], [A, y], [B, x], [B, y], [C, x], [C, y], [D, x], [D, y]]
fun example3(): List<List<Char>> {
    val a = "ABCD".toList()
    val b = "xy".toList()

    return listOf(a, b)
        .product()
        .toList()
}