arrays - 使用枚举查找数组(Swift 5)中的所有组合

Question

我在 C# 中有一些代码完全符合我喜欢做的事情:枚举数组中给定长度的所有组合(有重复)。像这样:

public static IEnumerable<IEnumerable<int>> CombinationsWithRepition(IEnumerable<int> input, int length)
{
    if (length <= 0)
        yield return new List<int>();
    else
    {
        foreach (int i in input)
            foreach (IEnumerable<int> c in CombinationsWithRepition(input, length - 1))
            {
                List<int> list = new List<int>();
                list.Add(i);
                list.AddRange(c);
                yield return list;
            }
    }
}

用法:

foreach (var c in CombinationsWithRepition(new int[] { 0, 1, 2 }, 2))
{
    foreach (var x in c)
        Console.Write(x + " : ");

    Console.WriteLine("");
}

输出:

0 : 0
0 : 1
0 : 2
1 : 0
1 : 1
1 : 2
2 : 0
2 : 1
2 : 2

现在我想把它移植到 swift 5，但我失败了。我在网上搜索，但只能找到没有重复的解决方案或创建大量数组的解决方案。具有枚举整个事物的能力很重要(没有输出为数组或包含所有结果的列表)。我不知道如何将“yield”移植到 swift 代码。

这是我找到的最接近的: How do I return a sequence in Swift?

提前致谢

Answer 1

Swift 没有yield 语句。为了“懒惰地”枚举所有组合(不将所有组合存储在数组中)，我们必须实现 Sequence谁的Iterator在其 next() 中按需计算组合方法。

这是一个可能的实现。这个想法是维护一个“位置”数组作为状态变量。最初是

 [ base.startIndex, ..., base.startIndex ]

其中 base 是构建组合的集合(例如 Array)。在每次迭代中，最后一个位置都会递增。如果它到达 base.endIndex，则将其重置为 base.startIndex，并增加下一个位置。 (这正是您在数字系统中递增数字的方式，例如十进制数。)如果第一个位置已递增到 base.endIndex，则枚举完成。

在每次迭代中，此positions 数组被映射到基础集合中相应的元素数组，并从next() 方法返回。

只需要这个数组和两个 bool 变量作为中间存储。该实现使用了 this answer 中的想法在 Code Review 上，例如 next() 方法中只有一个导出点。

struct CombinationsWithRepetition<C: Collection> : Sequence {

    let base: C
    let length: Int

    init(of base: C, length: Int) {
        self.base = base
        self.length = length
    }

    struct Iterator : IteratorProtocol {
        let base: C

        var firstIteration = true
        var finished: Bool
        var positions: [C.Index]

        init(of base: C, length: Int) {
            self.base = base
            finished = base.isEmpty
            positions = Array(repeating: base.startIndex, count: length)
        }

        mutating func next() -> [C.Element]? {
            if firstIteration {
                firstIteration = false
            } else {
                // Update indices for next combination.
                finished = true
                for i in positions.indices.reversed() {
                    base.formIndex(after: &positions[i])
                    if positions[i] != base.endIndex {
                        finished = false
                        break
                    } else {
                        positions[i] = base.startIndex
                    }
                }

            }
            return finished ? nil : positions.map { base[$0] }
        }
    }

    func makeIterator() -> Iterator {
        return Iterator(of: base, length: length)
    }
}

示例 1:

let comb = CombinationsWithRepetition(of: [0, 1, 3], length: 2)
for c in comb { print(c) }

输出:

[0, 0]
[0, 1]
[0, 3]
[1, 0]
[1, 1]
[1, 3]
[3, 0]
[3, 1]
[3, 3]

Example 2:

let comb = CombinationsWithRepetition(of: "abcd", length: 3)
for c in comb { print(c) }

输出:

["a", "a", "a"]
["a", "a", "b"]
["a", "a", "c"]
["a", "a", "d"]
["a", "b", "a"]
...
["d", "d", "c"]
["d", "d", "d"]