Apple Swift - Generate combinations with repetition
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]]
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]]
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
}