Combinations of items in array with multithreading using Swift

Question

I'm writing a small algorithm and I have to calculate all combinations of items in an array without repetitions. Until now I have used this code below but I now need to speed up this process because it takes too long. I have tried to implement concurrency with Swift (the code will run on a Mac) but unfortunately it doesn't work.

The algorithm I'm using was taken from http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ and then converted from C to Swift. Could you please help me out to solve this problem?

func printCombination(arr: [Int], r: Int) {
    trips.removeAll()
    var data: [Int] = []
    for _ in 1...r
    {
        data.append(Int())
    }
    combinationUtil(arr: arr, r: r, index: 0, data: data, i: 0)
}

func combinationUtil(arr: [Int], r: Int, index: Int, data: [Int], i: Int) {
    var data: [Int] = data
    if (index == r)
    {
        for j in 0..<r {
           array.append(data[j])

        }
        return
    }

    if (i >= arr.count) {
        return
    }

    data[index] = arr[i]
    combinationUtil(arr: arr, r: r, index: index + 1, data: data, i: i + 1)
    combinationUtil(arr: arr, r: r, index: index, data: data, i: i + 1)
}
    /* arr[]  ---> Input Array
   r      ---> Size of a combination to be printed
   index  ---> Current index in data[]
   data[] ---> Temporary array to store current combination
   i      ---> index of current element in arr[]     */

Can you turn "it doesn't work" into something useful? What do you want to have happen and what happens instead? — Phillip Mills, Dec 13 '17 at 16:37
Are you actually familiar with Swift? That code truly looks like it was just line by line ported from C. Moreover, there's nothing concurrent in that piece of code... — Dávid Pásztor, Dec 13 '17 at 16:51
For Phillip Mills, the above code works fine, I tried implementing concurrency because I wanted it to calculate the combinations simultaneously and it literally didn't do anything, the code ran without throwing errors. — Federico G, Dec 13 '17 at 17:11
For Dávid Pásztor, I have been studying Swift for about a year now but I never write algorithms that I really have to optimise so I don't have a lot of experience. Because I have to finish this code in a really short time I unfortunately had to port the code line by line to Swift. The code I posted is the one I'm using without concurrency. I would like either to add concurrency to it, or to write an entirely different code to solve the problem using concurrency. — Federico G, Dec 13 '17 at 17:17
"I tried implementing concurrency" how? there's no concurrency in your posted code. — GetSwifty, Dec 13 '17 at 18:28
"It takes too long" ... Define "too long". What's your input array size and what is the number of elements you want in your resulting combinations? — Rob, Dec 13 '17 at 18:33

Rob · Accepted Answer · 2017-12-13T19:51:25.980

You say that the above code in your example "works fine", but I don't see how, as you reference some variables not in this code snippet (trips and array) and you're just appending more and more integers to array.

Personally, I'd step away from this literal translation of the C++/Java code, and just focus on how to best implement this conceptual algorithm in Swift. The idea is to pick a value out of the array, add it to the data set, and recursively call the routine again having removed the picked value out. That yields something like:

func printCombinations(with combinationThusFar: [Int] = [], from array: [Int], size: Int, startingAt: Int = 0) {
    if size == 0 {
        print(combinationThusFar)
        return
    }

    for i in startingAt ... array.count - size {
        var remaining = array
        remaining.remove(at: i)
        printCombinations(with: combinationThusFar + [array[i]], from: remaining, size: size - 1, startingAt: i)
    }
}

And then:

let array = [1, 2, 3, 4, 5]
printCombinations(from: array, size: 3)

Note, I haven't introduced any concurrency yet, but with an algorithm like this, I see no reason to do that as there is nothing computationally intensive here. For concurrency to improve performance, you need enough work on each thread to offset the overhead of managing multiple threads. Making this run code in parallel can actually make it slower if you don’t have enough code running on each dispatched piece of code.

If you were going to introduce concurrency into a routine, one of the best ways is using concurrentPerform. (See https://stackoverflow.com/a/39949292/1271826 for an example.) But that's going to be tricky here (it lends itself best for non-recursive algorithms). Besides, I don't see the need to do that here.

Combinations of items in array with multithreading using Swift

1 Answers1