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?

Dakar

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

Dzerzhinsk

Very smart to use ArraySlice 👍 – Simian

Can you add solution for repetation like[[1, 1], [1, 2],[2, 2],[3,1], [1, 3], [2, 2], [2, 3], [3, 3]] – Unperforated

If you want this version with no repititions, you just need to change the line: let subcombos = combos(elements: elements, k: k - 1) By let subcombos = combos(elements: elements.dropFirst(), k: k - 1) – Liebknecht

Answer 2

Your example gives combinations with repetition. For the record I have written a non-repetitive combination in Swift. I based it on the JavaScript version here: http://rosettacode.org/wiki/Combinations#JavaScript

I hope it helps others and if anyone can see improvement please do.. note this is my first attempt at Swift and was hoping for a neater way of doing the Swift equivalent of JavaScript slice.

func sliceArray(var arr: Array<Int>, x1: Int, x2: Int) -> Array<Int> {
    var tt: Array<Int> = []
    for var ii = x1; ii <= x2; ++ii {
        tt.append(arr[ii])
    }
    return tt
}

func combinations(var arr: Array<Int>, k: Int) -> Array<Array<Int>> {
    var i: Int
    var subI : Int

    var ret: Array<Array<Int>> = []
    var sub: Array<Array<Int>> = []
    var next: Array<Int> = []
    for var i = 0; i < arr.count; ++i {
        if(k == 1){
            ret.append([arr[i]])
        }else {
            sub = combinations(sliceArray(arr, i + 1, arr.count - 1), k - 1)
            for var subI = 0; subI < sub.count; ++subI {
                next = sub[subI]
                next.insert(arr[i], atIndex: 0)
                ret.append(next)
            }
        }

    }
    return ret
}


var myCombinations = combinations([1,2,3,4],2)

---

Per the OP's request, here is a version which removes the custom Array slicing routine in favor of functionality in the standard library

// Calculate the unique combinations of elements in an array
// taken some number at a time when no element is allowed to repeat
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.suffixFrom(1))
    let sub_combos = combinations(rest, takenBy: takenBy - 1)
    result += sub_combos.map { [source[0]] + $0 }

    result += combinations(rest, takenBy: takenBy)

    return result
}

var myCombinations = combinations([1,2,3,4], takenBy: 2)
// myCombinations = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Smacking

You can slice the array using a range, e.g. arr[1...3] to pull the 2nd, 3rd, and 4th elements from the array. In your code the call would be arr[i+1..<arr.count] – Josephson

Answer 3

Updated @richgordonuk answer for Swift 4 which provides a non-repetitive combination:

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
}

Robinett

Answer 4

Follow up on the existing answers extending RangeReplaceableCollection to support strings as well:

extension RangeReplaceableCollection {
    func combinations(of n: Int) -> [SubSequence] {
        guard n > 0 else { return [.init()] }
        guard let first = first else { return [] }
        return combinations(of: n - 1).map { CollectionOfOne(first) + $0 } + dropFirst().combinations(of: n)
    }
    func uniqueCombinations(of n: Int) -> [SubSequence] {
        guard n > 0 else { return [.init()] }
        guard let first = first else { return [] }
        return dropFirst().uniqueCombinations(of: n - 1).map { CollectionOfOne(first) + $0 } + dropFirst().uniqueCombinations(of: n)
    }
}

---

[1, 2, 3, 4, 5, 6].uniqueCombinations(of: 2)  // [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 3], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6], [4, 5], [4, 6], [5, 6]]

"abcdef".uniqueCombinations(of: 3) // ["abc", "abd", "abe", "abf", "acd", "ace", "acf", "ade", "adf", "aef", "bcd", "bce", "bcf", "bde", "bdf", "bef", "cde", "cdf", "cef", "def"]

Sindysine

Answer 5

You can use Apple's new library for this: https://github.com/apple/swift-algorithms/blob/main/Guides/Combinations.md

let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2) {
    print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]

Roam

Answer 6

The main mistake I was making was to use a var named the same as my function:

combos += combos(array, k)

Which is why I was seeing an error on this line and the other line where my function was being called.

After fixing that the rest of the problems were easier to solve :)

In case it will help anyone here's my working 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]

    var ret: Array<Array<T>> = []
    var subcombos = combos(array, k - 1)
    for subcombo in subcombos {
        var sub = subcombo
        sub.insert(head, atIndex: 0)
        ret.append(sub)
    }
    array.removeAtIndex(0)
    ret += combos(array, k)

    return ret
}

If anyone can improve it I'd be happy

For example can anyone explain how to get rid of the line var sub = subcombo. i.e. how do I make subcombo mutable by default?

Dakar

Answer 7

A functional take on the same algorithm:

func headTail<C: Collection>(_ c: C) -> (C.Element, C.SubSequence)? {
    if c.isEmpty { return nil }
    else { return (c.first!, c.dropFirst()) }
}

func combos<C: Collection>(_ c: C, by k: Int) -> [[C.Element]] {
    if k <= 0 { return [[]] }
    else if let (head, tail) = headTail(c) {
        return combos(c, by: k-1).map { [head] + $0 } + combos(tail, by: k)
    } else { return [] }
}

Or, as member functions over Collection:

extension Collection {
    var headTail: (Element, SubSequence)? {
        if isEmpty { return nil }
        else { return (first!, dropFirst()) }
    }
    
    func combos(by k: Int) -> [[Element]] {
        if k <= 0 { return [[]] }
        else if let (head, tail) = headTail {
            return combos(by: k-1).map { [head] + $0 } + tail.combos(by: k)
        } else { return [] }
    }
}

Straightjacket