Пошаговая перестановка перестановок произвольных множеств в Kotlin

Question

Я пытаюсь найти элегантный способ пошагового перебора всех возможных перестановок произвольного числа наборов или «сегментов». Мне нужно сделать это поэтапно, потому что я имею дело с большим количеством возможных перестановок и исчерпал пространство памяти, пытаясь сохранить все перестановки в памяти, а затем отсеять недопустимые. Вместо этого я пытаюсь выполнить каждую перестановку по одной за раз и сохранить ее только в окончательном списке в памяти, если он действителен, чтобы я мог сэкономить место в памяти.

Я пытался написать ручное решение для этого, и оказалось, что это немного сложно - я не хочу точно знать, сколько списков / наборов я имею в виду, поэтому я не может использовать подход грубой силы создания серии вложенных циклов. Создание собственного итератора для этого оказалось своим собственным набором проблем.

Я надеялся, что будут некоторые встроенные методы или инструменты, которые я мог бы использовать для этого, не изобретая колесо.

Вот пример: допустим, у меня есть пара наборов букв:

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

И моя цель - найти все возможные сочетания букв из этих двух «ведер», но только те, которые не имеют дубликатов в своих наборах (в реальном мире могут быть более сложные требования, просто используя этот простой пример для примера). Итак, все возможные перестановки:

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

Теперь, когда у меня есть все возможные перестановки, я хочу отсеять те, которые не удовлетворяют требованиям: [a, a] and [c, c].

Вместо того, чтобы отсеивать их после факта (и занимать место во временной памяти, где оно могло бы быть заполнено допустимой комбинацией), я хочу проверить при каждой созданной перестановке, является ли она действительной, прежде чем сохранять ее в памяти ,

Есть ли в * 1021 что-нибудь, что могло бы облегчить это?

РЕДАКТИРОВАТЬ: я смог выяснить, как я мог сделать это, создав свой собственный класс "итератор", который проходит через каждую перестановку, и "пузыриться", если окончательный набор был циклически пройден полностью, в порядке чтобы убедиться, что я ударил каждую перестановку. Я могу опубликовать решение здесь, если кто-то заинтересован (возможно, немного неэффективным) решением, но я все же хотел бы знать, есть ли более простой способ сделать это, используя некоторые встроенные Kotlin инструменты.

Answer 1

Если я понимаю вопрос, то, что вы просите, это декартово произведение наборов. (' Перестановки ' обычно относятся к различным упорядочениям всех элементов одного набора или их подмножеств.)

Выполнить это напрямую легко, используя map() и flatMap():

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

(operator fun… times - это волшебный c, позволяющий переопределить оператор *. T и U являются параметрами типа, так что это будет работать для наборов любого типа. И to - это простой способ создать Pair.)

Однако, как вы говорите, это создает список результатов, и если вы хотите выполнить какую-либо фильтрацию или другую постобработку, это создаст другую.

Обычный способ избежать этого - использовать sequence . (Эквивалентно Java streams .) Это ленивые структуры, в которых элементы оцениваются только при необходимости.

Обычно это так же просто, как добавить .asSequence() к списку, но поскольку у нас их два здесь, это довольно сложно… Вот один из способов:

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

, который возвращает Sequence, так что вы можете выполнить любую фильтрацию или другой постобработки, которую вы хотите, а затем вызвать терминальную операцию, такую ​​как toList(), чтобы потом выполнить вычисления:

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

(я не слишком опытен с последовательностями, так что я не гарантирую, что это самый эффективный способ ...)