 
 
 /*
-  Calculates C(n, k), or "n-choose-k", i.e. how many different selections
-  of size k out of a total number of distinct elements (n) you can make.
-*/
+ Calculates C(n, k), or "n-choose-k", i.e. how many different selections
+ of size k out of a total number of distinct elements (n) you can make.
+ */
 func combinations(n: Int, _ k: Int) -> Int {
-  return permutations(n, k) / factorial(k)
+    return permutations(n, k) / factorial(k)
 }
 
 combinations(3, 2)



/*
  Prints out all the permutations of the given array.
  Original algorithm by Niklaus Wirth.
  See also Dr.Dobb's Magazine June 1993, Algorithm Alley
*/
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 {
      swap(&a[i], &a[n])
      permuteWirth(a, n - 1)
      swap(&a[i], &a[n])
    }
  }
}

let letters = ["a", "b", "c", "d", "e"]


/* Supporting code because Swift doesn't have a built-in 2D array. */
struct Array2D<T> {
    let columns: Int
    let rows: Int
    private var array: [T]
    
    init(columns: Int, rows: Int, initialValue: T) {
        self.columns = columns
        self.rows = rows
        array = .init(count: rows*columns, repeatedValue: initialValue)
    }
    
    subscript(column: Int, row: Int) -> T {
        get { return array[row*columns + column] }
        set { array[row*columns + column] = newValue }
    }
}

/*
 Calculates C(n, k), or "n-choose-k", i.e. the number of ways to choose
 k things out of n possibilities.
 
 Thanks to the dynamic programming, this algorithm from Skiena allows for
 the calculation of much larger numbers, at the cost of temporary storage
 space for the cached values.
 */

func binomialCoefficient(n: Int, _ k: Int) -> Int {
    var bc = Array(count: n + 1, repeatedValue: Array(count: n + 1, repeatedValue: 0))
    
    for i in 0...n {
        bc[i][0] = 1
        bc[i][i] = 1
    }
    
    if n > 0 {
        for i in 1...n {
            for j in 1..<i {
                bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j]
            }
        }
    }
    
    return bc[n][k]
}

binomialCoefficient(30, 15)
