使用枚举查找数组 (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("");
}

输出：

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

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

提前致谢

Answer 1

以下似乎可以实现你想要的：

let source = Array((0...5))
let length = 3

func combinationsWithRepetition(input source: [Int], length: Int) -> [[Int]] {
  if length == 0 { return [[]] }
  let baseArray = combinationsWithRepetition(input: source, length: length - 1)
  var newArray = [[Int]]()
  for value in source {
    baseArray.forEach {
      newArray.append([=10=] + [value])
    }
  }
  return newArray
}

print(combinationsWithRepetition(input: [0, 1, 2], length: 2))
// [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]]

或者更实用：

func combinationsWithRepetition(input source: [Int], length: Int) -> [[Int]] {
  if length == 0 { return [[]] }
  let baseArray = combinationsWithRepetition(input: source, length: length - 1)
  return baseArray.flatMap { array in
    return source.map { array + [[=11=]] }
  }
}

基本上，combinationsWithRepetition returns length 个元素的所有可能组合的数组。例如，combinationsWithRepetition(input: [0, 1, 2, 3], length: 1) returns [[0], [1], [2], [3]]。超过 0 的 length 使用递归处理，您最初似乎使用递归（可能是因为我不知道 C# 语法）。 Swift 支持数组添加，例如，[1] + [2] 是 [1, 2]，上面的代码对从 source 到元素的所有值（它们是长度 length - 1) 结果数组。

第二个代码使用 flatMap 其中 "flattens" 将嵌套数组转换为数组，例如[[[1, 2], [1, 3]], [[1, 4], [1, 5]]] 变成 [[1, 2], [1, 3], [1, 4], [1, 5]]。否则逻辑与使用迭代的逻辑完全相同。

要获得 post 中的输出，您可以执行以下操作：

combinationsWithRepetition(input: [0, 1, 2], length: 2).forEach {
  print([=12=].map(String.init).joined(separator: " : "))
}

这导致

Answer 2

Swift 没有 yield 语句。为了“懒惰地”枚举所有组合（不将所有组合存储在数组中），我们必须实现一个 Sequence whose Iterator computes the combinations on demand in its next() 方法。

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

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

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

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

只需要这个数组和两个布尔变量作为中间存储。该实现使用了代码审查 this answer 中的想法，例如 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[[=11=]] }
        }
    }

    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]

示例 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"]

Answer 3

在具有 yield 的语言中，它是对调用函数 return 结果的回调。 yield returns.

时保持当前函数状态并继续

我们可以在 Swift 中使用闭包回调实现类似的东西。

这几乎是对您例程的直接翻译：

func combinationsWithRepetition(_ input: [Int], length: Int, yield: ([Int]) -> ()) {
    if length <= 0 {
        yield([])
    }
    else {
        for i in input {
            combinationsWithRepetition(input, length: length - 1) { c in
                var list = [Int]()
                list.append(i)
                list += c
                yield(list)
            }
        }
    }
}

combinationsWithRepetition([0, 1, 2], length: 2) { c in
    print(c.map(String.init).joined(separator: " : "))
}

输出：

有时调用者想要控制正在产生的函数。如果您希望能够停止该函数，您可以让 yield 回调 return 一个 Bool 告诉让步函数是否应该继续。

考虑这个例子：

// Generate squares until told to stop
func squares(_ yield: (_ n: Int) -> Bool) {
    var i = 1
    var run = true
    while run {
        run = yield(i * i)
        i += 1
    }
}

// print squares until they exceed 200
squares() { n -> Bool in
    print(n)
    return n < 200
}

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

Finding all combinations in an array (Swift 5) with enumeration

arrays

combinations

enumeration

find

swift