Swift - Generate combinations with repetition

10,411

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

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

Solution 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
}

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

Solution 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]
Share:
10,411

Related videos on Youtube

matthew
Author by

matthew

Updated on September 14, 2022

Comments

  • matthew
    matthew about 1 year

    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?

  • David Grandinetti
    David Grandinetti about 9 years
    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]
  • Jacob Relkin
    Jacob Relkin about 4 years
    Very smart to use ArraySlice 👍
  • Aiyub Munshi
    Aiyub Munshi over 3 years
    Can you add solution for repetation like[[1, 1], [1, 2],[2, 2],[3,1], [1, 3], [2, 2], [2, 3], [3, 3]]