arrays - Swift - Generate combinations with repetition

Question

I'm trying to generate a nested array containing all combinations with repetition in Apple's Swift programming language.

An detailed explanation of combinations with repetition can be found near the bottom of this page: http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Briefly; order does not matter, and we can repeat

n = the set of things we are choosing form

r = the number of things we are choosing

I want to create a function that will generate a nested array containing all combinations with repetition for any (small) values of n and r.

If there are n=3 things to choose from, and we choose r=2 of them.

n = [0, 1, 2]
r = 2

The result of the function combos(n: [0, 1, 2], r: 2) would be:

result = [
  [0, 0],
  [0, 1],  
  [0, 2],
  [1, 1],
  [1, 2],
  [2, 2]
]

// we don't need [1, 0], [2, 0] etc. because "order does not matter"

There are examples for doing this in many programming languages here: http://rosettacode.org/wiki/Combinations_with_repetitions

Here's the PHP example. It is one of the simplest and returns an array, which is what I want:

function combos($arr, $k) {
    if ($k == 0) {
        return array(array());
    }

    if (count($arr) == 0) {
        return array();
    }

    $head = $arr[0];

    $combos = array();
    $subcombos = combos($arr, $k-1);
    foreach ($subcombos as $subcombo) {
        array_unshift($subcombo, $head);
        $combos[] = $subcombo;
    }
    array_shift($arr);
    $combos = array_merge($combos, combos($arr, $k));
    return $combos;
}

Here's where I've got so far with porting the function to Swift:

func combos(var array: [Int], k: Int) -> AnyObject { // -> Array<Array<Int>> {
    if k == 0 {
        return [[]]
    }
    
    if array.isEmpty {
        return []
    }
    
    let head = array[0]
    
    var combos = [[]]
    var subcombos: [Array<Int>] = combos(array, k-1)    // error: '(@Ivalue [Int], $T5) -> $T6' is not identical to '[NSArray]'
    for subcombo in subcombos {
        var sub = subcombo
        sub.insert(head, atIndex: 0)
        combos.append(sub)
    }
    array.removeAtIndex(0)
    combos += combos(array, k)    // error: '(@Ivalue [Int], Int) -> $T5' is not identical to '[NSArray]'
    
    return combos
}

Mostly I seem to be having problems with the type declarations of the various variables and whether these are mutable or immutable.

I've tried being more explicit and less explicit with the type declarations but all I'm managed to achieve are slightly different error messages.

I would be most grateful if someone would explain where I'm going wrong and why?

Answer 1

You can get rid of var sub = subcombo by writing the loop as

for subcombo in subcombos {
    ret.append([head] + subcombo)
}

This can be further simplified using the map() function:

func combos<T>(var array: Array<T>, k: Int) -> Array<Array<T>> {
    if k == 0 {
        return [[]]
    }

    if array.isEmpty {
        return []
    }

    let head = [array[0]]
    let subcombos = combos(array, k: k - 1)
    var ret = subcombos.map {head + $0}
    array.removeAtIndex(0)
    ret += combos(array, k: k)

    return ret
}

---

Update for Swift 4:

func combos<T>(elements: ArraySlice<T>, k: Int) -> [[T]] {
    if k == 0 {
        return [[]]
    }

    guard let first = elements.first else {
        return []
    }

    let head = [first]
    let subcombos = combos(elements: elements, k: k - 1)
    var ret = subcombos.map { head + $0 }
    ret += combos(elements: elements.dropFirst(), k: k)

    return ret
}

func combos<T>(elements: Array<T>, k: Int) -> [[T]] {
    return combos(elements: ArraySlice(elements), k: k)
}

Now array slices are passed to the recursive calls to avoid the creation of many temporary arrays.

Example:

print(combos(elements: [1, 2, 3], k: 2))
// [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]