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

I would like to be able to generate an array of all possible permutations of a Bool (true/false or 1/0) of a given size n, in Swift. For example, given n=2 the result of calling generate(2) would be

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

I looked in Swift-algorithms but all I see is permutations and combinations of a provided array of elements. These algorithms don't appear to address scenario for a Bool with n>2. Also, I'm not sure what name to call this algorithm.

CodePudding user response：

Just for fun a functional approach:

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($0) }
            }
        }
    }
}

Usage:

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

or with Strings (Collection Of Characters):

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

CodePudding user response：

Here's a simple recursive implementation:

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

This gives the output:

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