[Swift] Factorial / Permutations / Combinations

func factorial(_ n: Int) -> Int {
  var n = n
  var result = 1
  while n > 1 {
    result *= n
    n -= 1
  }
  return result
}

factorial(5)   // 5*4*3*2*1 = 120

---

func permutations(_ n: Int, _ k: Int) -> Int {
  var n = n
  var answer = n
  for _ in 1..<k {
    n -= 1
    answer *= n
  }
  return answer
}

permutations(5, 3)   // returns 60
permutations(50, 6)  // returns 11441304000
permutations(9, 4)   // returns 3024

          9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
P(9, 4) = --------------------------------- = 9 * 8 * 7 * 6 = 3024
                 5 * 4 * 3 * 2 * 1

---

func permuteWirth<T>(_ a: [T], _ n: Int) {
    if n == 0 {
        print(a)   // display the current permutation
    } else {
        var a = a
        permuteWirth(a, n - 1)
        for i in 0..<n {
            a.swapAt(i, n)
            permuteWirth(a, n - 1)
            a.swapAt(i, n)
        }
    }
}

let letters = ["a", "b", "c", "d", "e"]
permuteWirth(letters, letters.count - 1)


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

func permute<C: Collection>(items: C) -> [[C.Iterator.Element]] {
    var scratch = Array(items) // This is a scratch space for Heap's algorithm
    var result: [[C.Iterator.Element]] = [] // This will accumulate our result

    // Heap's algorithm
    func heap(_ n: Int) {
        if n == 1 {
            result.append(scratch)
            return
        }

        for i in 0..<n-1 {
            heap(n-1)
            let j = (n%2 == 1) ? 0 : i
            scratch.swapAt(j, n-1)
        }
        heap(n-1)
    }

    // Let's get started
    heap(scratch.count)

    // And return the result we built up
    return result
}

// We could make an overload for permute() that handles strings if we wanted
// But it's often good to be very explicit with strings, and make it clear
// that we're permuting Characters rather than something else.

let string = "ABCD"
let perms = permute(items: Array(string)) // Get the character permutations
let permStrings = perms.map() { String($0) } // Turn them back into strings
print(permStrings)

---

func combinations<T>(source: [T], takenBy : Int) -> [[T]] {
    if(source.count == takenBy) {
        return [source]
    }

    if(source.isEmpty) {
        return []
    }

    if(takenBy == 0) {
        return []
    }

    if(takenBy == 1) {
        return source.map { [$0] }
    }

    var result : [[T]] = []

    let rest = Array(source.suffix(from: 1))
    let subCombos = combinations(source: rest, takenBy: takenBy - 1)
    result += subCombos.map { [source[0]] + $0 }
    result += combinations(source: rest, takenBy: takenBy)
    return result
}

let numbers = [1,2,3,4,5]
print(combinations(source:numbers,takenBy:2))

// print [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

// 모든 조합 구하기
func allCombos<T>(elements: Array<T>) -> [[T]] {
    var answer: [[T]] = []
    for i in 1...elements.count {
        answer.append(contentsOf: combinations(source: elements, takenBy: i))
    }
    return answer
}

let numbers = [1,2,3]
print(allCombos(elements: numbers))

// prints [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

 

 

 

---

https://github.com/kodecocodes/swift-algorithm-club/tree/master/Combinatorics

GitHub - kodecocodes/swift-algorithm-club: Algorithms and data structures in Swift, with explanations!

https://stackoverflow.com/questions/25162500/swift-generate-combinations-with-repetition

Swift - Generate combinations with repetition

https://stackoverflow.com/questions/34968470/calculate-all-permutations-of-a-string-in-swift

Calculate all permutations of a string in Swift