逐步迭代Kotlin中任意集合的排列

问题描述 投票:0回答:1

我正在尝试找到一种优雅的方法来逐步遍历任意数量的集合或“存储桶”的所有可能排列。我需要逐步执行此操作,因为我正在处理大量可能的排列,并且已经用尽了存储空间,试图将所有排列存储在内存中,然后淘汰了无效的排列。取而代之的是,我尝试一次遍历每个排列,并且仅在有效的情况下才将其存储在内存中的最终列表中,以便节省一些内存空间。

我一直在尝试为此编写一个手动解决方案,事实证明这有点困难-我不想确切知道我要处理多少个列表/集合,因此我无法接受创建一系列嵌套的for循环的蛮力方法。为此,创建自定义迭代器被证明是其自身的挑战。

我希望有一些内置的方法或工具可以在不重新发明轮子的情况下加以利用。

这里是一个例子:假设我有几组字母:

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

而不是清除事实之后的结果(并占用临时内存中的空间,否则可以通过有效的组合来填充空间),我想先检查每个创建的排列是否有效,然后再将其存储在内存中。

Kotlin内建了什么可以使此操作变得更容易?

编辑:我能够通过创建自己的“迭代器”类来弄清楚如何做到这一点,该类会逐步遍历每个排列,如果最终集合已被完全遍历,则会“冒泡”,以确保我击中每个排列。如果有人对此解决方案感兴趣(可能效率不高),我可以在此处发布该解决方案,但我仍然想知道是否有使用内置的Kotlin工具进行此操作的简便方法。

kotlin permutation
1个回答
0
投票

如果我理解这个问题,您要的是集合的Cartesian product。 (“ Permutations”通常是指单个集合的所有元素或其子集的不同顺序。)

使用map()map()直接进行此操作很容易:

flatMap()

([flatMap()是一个魔术,它使您可以覆盖operator fun <T, U> Iterable<T>.times(other: Iterable<U>) = flatMap{ a -> other.map{ b -> a to b }} 运算符。operator fun… times*是类型参数,因此适用于任何类型的集合。并且T是一种简单的方法构造一个U。)

但是,正如您所说,这将创建结果列表,并且,如果您要进行任何过滤或其他后处理,则会创建另一个结果。

避免这种情况的通常方法是使用to。 (等效于Java Pair。)这些是惰性结构,其中的元素仅在需要时才进行评估。

通常这很容易,将sequences添加到列表中,但是由于我们这里有两个,所以比较棘手……这是一种方法:

streams

返回一个.asSequence(),因此您可以进行任何过滤或所需的其他后处理,然后在以后调用诸如.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 }}
}

((我对序列不太有经验,所以我保证这是most有效的方法……)

© www.soinside.com 2019 - 2024. All rights reserved.