Algorithm to list all tuples from an array of String

Question

I'm trying to solve the following problem, given an array of String, of size n, list all n-tuples from this array, that is:

let A: [String] = ["a","b","c",...]

determine all the tuples

["abc..","bac..",...], of which there are exactly n!.

I've written a solution in Swift, but I'm not quite happy with the result, as it uses closures, making it difficult to iterate over the tuples.

Here's the code, just in case:

public func tuple(seq:[String], value:String, block:(String) -> ()) {
    if seq.count > 0 {
        for i in 0..<seq.count {
            var uu = seq;
            let kk:String = uu[i];
            uu.remove(at: i)
            self.tuple(seq:uu,value: value + kk, block: block)
        }
    } else {
        block(value)
    }
}

Anyone with a valid solution without closure?

Answer 1

Using the code from Sequence-based enumeration of permutations in lexicographic order on Code Review (updated for Swift 4, and with the suggestions from Hamish's answer implemented):

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] < self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] >= self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] < self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] >= self[l] {
            l -= 1
        }
        self.swapAt(j, l)

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            self.swapAt(lo, hi)
            lo += 1
            hi -= 1
        }
        return true
    }
}

struct PermutationSequence<Element : Comparable> : Sequence, IteratorProtocol {

    private var current: [Element]
    private var firstIteration = true

    init(startingFrom elements: [Element]) {
        self.current = elements
    }

    init<S : Sequence>(_ elements: S) where S.Iterator.Element == Element {
        self.current = elements.sorted()
    }

    mutating func next() -> [Element]? {

        var continueIterating = true

        // if it's the first iteration, we avoid doing the permute() and reset the flag.
        if firstIteration {
            firstIteration = false
        } else {
            continueIterating = current.permute()
        }

        // if the array changed (and it isn't the first iteration), then return it,
        // else we're at the end of the sequence.
        return continueIterating ? current : nil
    }
}

one can very efficiently iterate over all permutations of an array:

let a = ["a", "b", "c"]
let permSeq = PermutationSequence(startingFrom: a)

for tuple in permSeq {
    print(tuple.joined())
}

Each call to the iterator creates the next permutation, and only a fixed amount of additional storage is needed (one array for the current permutation, and a boolean variable).

Answer 2

I am not sure why you need the closure to just generate the list. Here is what have used in the past. There is probably a 1 liner using flatmap.

func tuple(_ input:[String])->[String]{
    print()
    if input.count == 1 {return input}
    var output = Array<String>()
    for a in 0...input.count-1 {
        var temp = input
        temp.remove(at: a)
        output += tuple(temp).map{input[a]+$0}
    }
    return output
}
print(tuple(a))