Order array of objects into every possible sequence in Swift

Question

Wondering if there is a clean way of doing this in Swift. Maybe using one or a couple of the global functions, ie Map / Reduce etc

The array contains unique custom objects of n quantity.

For example, with 3 items. But could have more or less. [1,2,3]

Would return an Array of Arrays

[ [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] ]

Here is a way in Java to complete the task. Just need to get into Swift form.

score 2 · Accepted Answer · edited Jun 02 '15 at 04:31

https://gist.github.com/JadenGeller/5d49e46d4084fc493e72

He created structs to handle permutations:

var greetingPermutations = PermutationSequenceGenerator(elements: ["hi", "hey", "hello"])
while let greetingSequence = greetingPermutations.next(){
    for greeting in greetingSequence {
    print("\(greeting) ")
   }
   println()
}

or:

var numberSpace = PermutationSpaceGenerator(objects: Array(1...4))
while let numberArray = numberSpace.next() {
   println(numberArray)
}

EDIT:

Here is a simpler way found on objc.io

Add Extension

extension Array {
    var decompose : (head: T, tail: [T])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil 
    }
}

Add outside your extension / and class

infix operator >>= {}
func >>=<A, B>(xs: [A], f: A -> [B]) -> [B] {
    return xs.map(f).reduce([], combine: +)
}

Normal Class Functions

func between<T>(x: T, ys: [T]) -> [[T]] {
    if let (head, tail) = ys.decompose {
        return [[x] + ys] + between(x, ys: tail).map { [head] + $0 }
    } else {
        return [[x]]
    }
}


func permutations<T>(xs: [T]) -> [[T]] {
    if let (head, tail) = xs.decompose {
        return permutations(tail) >>= { permTail in
            self.between(head, ys: permTail)
        }
    } else {
        return [[]]
    }
}

Testing

    let example = permutations([1,2,3,5,6,7,8])
    println(example)

This code extends Array with decompose function and also adds >>== operator (flattening) More about flattening: http://www.objc.io/snippets/4.html

what is between in: between(head, permTail) – DogCoffee Jun 02 '15 at 03:49 — DogCoffee, Jun 02 '15 at 03:49
Sorry, forgot to paste between function – chrisamanse Jun 02 '15 at 04:05 — chrisamanse, Jun 02 '15 at 04:05

score 2 · Answer 2 · answered Jun 02 '15 at 04:46

Probably too c-ish, but here is an alternative to the already posted examples.

var a = [1, 2, 3, 4, 5]
var b = [[Int]]()

func perms<T>(n: Int, inout a: [T], inout b: [[T]]) {
    if n == 0 {
        b.append(a)
    } else {
        for i in 0..<n {
            perms(n - 1, &a, &b)
            var j = 0
            if n % 2 == 0 {
                j = i
            }
            swap(&a[j], &a[n - 1])
        }
    }
}


perms(a.count, &a, &b)
println(b)

score 1 · Answer 3 · edited Jul 04 '20 at 11:14

Swift 5

Updated version of @DogCoffee for swift 5.x, all within an array extension :

extension Array {
    private var decompose : (head: Element, tail: [Element])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
    }
    
    private func between<T>(x: T, ys: [T]) -> [[T]] {
        if let (head, tail) = ys.decompose {
            return [[x] + ys] + between(x: x, ys: tail).map { [head] + $0 }
        } else {
            return [[x]]
        }
    }
    
    private func permutations<T>(xs: [T]) -> [[T]] {
        if let (head, tail) = xs.decompose {
            return permutations(xs: tail) >>= { permTail in
                self.between(x: head, ys: permTail)
            }
        } else {
            return [[]]
        }
    }
    
    func allPermutations() -> [[Element]] {
        return permutations(xs: self)
    } 
}

infix operator >>=
func >>=<A, B>(xs: [A], f: (A) -> [B]) -> [B] {
    return xs.map(f).reduce([], +)
}

Order array of objects into every possible sequence in Swift

3 Answers3