如何在 Swift 中生成给定大小的 1 和 0 位的所有排列

Question

我希望能够生成给定大小 n 的 Bool（true/false 或 1/0）所有可能排列的数组，在Swift。例如，给定 n=2，调用 generate(2) 的结果将是

let array: [Bool] = generate(2) // [[false, false], [false, true], [true, false], [true, true]]

我查看了 Swift 算法，但我看到的只是提供的元素数组的排列和组合。这些算法似乎没有解决 Bool 和 n>2 的场景。另外，我不确定该算法的名称。

Answer 1

这是一个简单的递归实现：

import Foundation

func recursion(depth: Int, arr: [[Bool]]) -> [[Bool]] {
  if depth == .zero {
    return arr
  }
  var newArr: [[Bool]] = []
  for item in arr {
    let newItem1 = item + [false]
    let newItem2 = item + [true]
    newArr += [newItem1, newItem2]
  }
  return recursion(depth: depth-1, arr: newArr)
}

print(recursion(depth: 1, arr: [[]]))
print(recursion(depth: 2, arr: [[]]))
print(recursion(depth: 3, arr: [[]]))

这给出了输出：

[[false], [true]]
[[false, false], [false, true], [true, false], [true, true]]
[[false, false, false], [false, false, true], [false, true, false], [false, true, true], [true, false, false], [true, false, true], [true, true, false], [true, true, true]]

Answer 2

只是为了好玩一个功能性的方法：

extension RangeReplaceableCollection {
    var combinations: [Self] { generate(2) }
    func generate(_ n: Int) -> [Self] {
        repeatElement(self, count: n).reduce([.init()]) { result, element in
            result.flatMap { elements in
                element.map { elements + CollectionOfOne([=10=]) }
            }
        }
    }
}

用法：

let elements = [false, true]  // [false, true]
let combinations = elements.combinations  // [[false, false], [false, true], [true, false], [true, true]]
let generateThree = elements.generate(3)  // [[false, false, false], [false, false, true], [false, true, false], [false, true, true], [true, false, false], [true, false, true], [true, true, false], [true, true, true]]

或

let elements = [0, 1]  // [0, 1]
let combinations = elements.combinations  // [[0, 0], [0, 1], [1, 0], [1, 1]]
let generateThree = elements.generate(3)  // [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

或使用字符串（字符集合）：

let elements = "01" // "01"
let combinations = elements.combinations  // ["00", "01", "10", "11"]
let generateThree = elements.generate(3)  // ["000", "001", "010", "011", "100", "101", "110", "111"]

如何在 Swift 中生成给定大小的 1 和 0 位的所有排列

How to generate all permutations of 1 and 0 bits of a given size in Swift

arrays

algorithm

collections

combinatorics

swift