Объединение группы в несколько групп без повторения

Question

У нас есть список элементов [A, B, C, D, E] и 3 группы , чтобы объединить эти элементы, я хотел бы напечатать список всех уникальных комбинаций без повторения для этих 3 групп .Допустимы только группы длин [2,2,1] (их можно отфильтровать после, это не обязательно, но было бы неплохо эффективно, и, если необходимо, длины групп можно было бы указать вручную в качестве параметра.).Что я имею в виду для уникального без повторения:

[[A, B], [C, D], [E]] и [[C, D], [A, B], [E]] и[[B, A], [C, D], [E]] были бы одинаковыми, поэтому не имеет значения порядок элементов внутри группы или порядок групп, меня это не интересуеткомбинации.

В моем конкретном случае у меня есть 16 предметов и 3 группы по 5, 5 и 6 предметов в каждой группе.

Пример того, чего я хочу достичь:

/**
 * Returns all the unique combinations of a group into multiple groups
 * [data] the group of elements to combine
 * [numberOfGroups] the number of groups
 */
fun combinations(data: List<String>, numberOfGroups: Int): List<List<List<String>>> {
    // The combinations code
}

val data = listOf("A", "B", "C", "D", "E")
print(combinations(data, 3))

Вывод будет примерно таким:

[
   [[A,B],[C,D],[E]],
   [[A,D],[B,C],[E]],
   ...
]

Заранее спасибо.

Answer 1

Я не знаю ответа на вашу проблему в целом, но я постараюсь решить этот конкретный случай разбиения списка из 5 элементов на группы [2, 2, 1] и поделиться некоторыми принципами, которые могут помочь вам придумать более общее решение.

Сначала поговорим о том, как представить результат. Если порядок элементов внутри группы незначителен, удобно представлять группу с Set<String>, так что setOf("A", "B") равно setOf("B", "A"). Тогда, если порядок самих групп в комбинации не имеет значения, эта комбинация может быть набором групп, то есть Set<Set<String>>.

Теперь о самом алгоритме. Удобно структурировать такой алгоритм, как рекурсивный поиск: вы выбираете первую группу элементов из ваших данных, а затем решаете задачу для данных без выбранных элементов и объединяете первую группу со всеми решениями, кроме нее. Поэтому наша функция, которая ищет комбинации, может выглядеть следующим образом:

fun combinationSequence(data: List<String>): Sequence<Set<Set<String>>> = sequence {
    for (group in possibleFirstGroups(data)) {
        val remaining = data - group
        if (remaining.isEmpty()) {
            yield(setOf(group))
        } else {
            yieldAll(combinationSequence(remaining).map { r -> setOf(group) + r })
        }
    }
}

Тогда как выбрать первую группу всеми возможными способами. Для групп размера 1 или 2 мы можем выбрать первый элемент группы из всех элементов данных, а затем выбрать второй элемент из оставшихся:

fun possibleFirstGroups(data: List<String>): Sequence<Set<String>> =
        when (data.size) {
            0 -> emptySequence()
            1, 2 -> sequenceOf(data.toSet())
            else -> sequence {
                for (e1 in data) {
                    for (e2 in data - e1) {
                        yield(setOf(e1, e2))
                    }
                }
            }
        }

Наши combinationSequence возвращают результаты, но будет много дубликатов, таких как [[A, B], [C, D], [E]] и [[C, D], [A, B], [E]]. Чтобы оставить только отдельные из них, мы можем использовать функцию distinct:

combinationSequence(data).distinct().forEach { println(it) }

Обратите внимание, что сложность этого решения возрастает экспоненциально с количеством элементов, поэтому я не ожидаю, что решение для 16 элементов будет завершено своевременно:)

Одним из подходов к снижению сложности является сокращение пространства поиска. Например, если мы уже нашли все комбинаций, начиная с группы [A, B], мы можем избежать получения комбинаций, содержащих эту группу где-то посередине, например [C, D], [A, B], ....