2
\$\begingroup\$

I want to return all of the permutations of an integer in Swift.

var outputArray = [[Int]]()
func perms ( _ input: [Int], _ output: [Int]) {
    if input.count == 0 {
        outputArray.append( [ Int( output.map{  String($0) }.joined() )! ] )
    }
    else {
        for i in 0..<input.count {
            let current = [input[i]]
            let before = Array( input [0..<i] )
            let after = Array( input [(i + 1) ..< input.count] )
            perms(before + after, current + output)
        }
    }
}

func permsOfInteger(_ input: Int) -> [[Int]] {
    var inp = input
    var inpArray = [Int]()
    while inp > 0 {
        inpArray.append(inp % 10)
        inp = inp / 10
    }
    perms(inpArray, [])
    return (outputArray)
}

( permsOfInteger(5432) )

I don't want to switch the algorithm (I'm aware of Heap's algorithm) but rather improve my implementation here. Any advice?

\$\endgroup\$
  • 1
    \$\begingroup\$ Just a quick clarification - can you elaborate on what it means to permute an integer? Do you mean generate all the permutations of the numerals that make up the number? Like the number 123 would generate "123", "132", "213", "231", "312", "321"? \$\endgroup\$ – user1118321 Dec 17 '18 at 2:15
  • \$\begingroup\$ Exactly. That is correct. \$\endgroup\$ – stevenpcurtis Dec 17 '18 at 2:16
  • \$\begingroup\$ Int.max, 0, and -123 are also integers but would cause a crash. This code is slow for many reasons. Have a look here and there for inspiration. This one is also good. \$\endgroup\$ – ielyamani Dec 17 '18 at 19:26
  • \$\begingroup\$ In addition, this code doesn't work for numbers with duplicate digits: There should be only one possible permutation for numbers like 1111, ... \$\endgroup\$ – ielyamani Dec 17 '18 at 20:52
2
\$\begingroup\$

permsOfInteger uses math operations divide and module to convert an Int to an array. By contrast, perms converts digits to strings and joins them to convert an array to Int. I think it's good to be consistent, I would use math operations for converting in both directions. And I would extract these operations to helper methods intToDigits and digitsToInt.

\$\endgroup\$
2
\$\begingroup\$

My main point of criticism is that the code uses a global variable to share data between the main function and the auxiliary function. That is problematic for various reasons:

  • The variable must be reset before the function can be called again.
  • The variable can be modified from outside of your function, causing wrong results.
  • The function is not thread-safe.

Example:

print(permsOfInteger(12)) // [[12], [21]]
print(permsOfInteger(12)) // [[12], [21], [12], [21]]

So

var outputArray = [[Int]]()

should be a local variable of func permsOfInteger(). You can then pass it as an “inout argument” to the helper function func perms(), or make that helper function a nested function of the main function:

func permsOfInteger(_ input: Int) -> [[Int]] {

    var outputArray = [[Int]]()

    func perms (_ input: [Int], _ output: [Int]) {
        // ... adds something to `outputArray` ...
    }

    // ...
    perms(inpArray, [])
    return (outputArray)
}

Why is the return type a nested array where each “integer permutation” is wrapped into a single-element array? Returning a simple array of integers seems more natural to me, and would be more efficient:

func permsOfInteger(_ input: Int) -> [Int] {
    // ...
}

print(permsOfInteger(12)) // [12, 21]

As @janos already said, combining the digits to an integer should be done in “pure maths” instead of using string operations. This can be done with reduce(), for example:

let digits = [1, 2, 3]
let number = digits.reduce(0, { $0 * 10 + $1 })
print(number) // 123

An [UInt8] array would be sufficient to store the decimal digits and save some memory. Here is a possible implementation as a computed property and custom initializer of the Int type:

extension Int {
    var decimalDigits: [UInt8] {
        precondition(self >= 0, "Value must not be negative")
        var digits = [UInt8]()
        var n = self
        while n > 0 {
            digits.append(UInt8(n % 10))
            n /= 10
        }
        return digits
    }

    init(decimalDigits: [UInt8]) {
        self = decimalDigits.reduce(0, { $0 * 10 + Int($1) })
    }
}

The slicing

let before = Array(input[0..<i])
let after = Array(input[(i + 1) ..< input.count])

can be slightly shorted with partial ranges:

let before = Array(input[..<i])
let after = Array(input[(i + 1)...])

An alternative would be to remove the current element from the input array:

var remaining = input
let current = [remaining.remove(at: i)]
perms(remaining, current + output)

Instead of if input.count == 0 you can test if input.isEmpty – it does not make a difference for arrays, but can be more efficient for arbitrary collections, where determining the count requires a traversal of the entire collection.

For the same reason you might want to replace

for i in 0..<input.count { ... }

by

for i in input.indices { ... }

since collection indices are not always zero based.

Finally, I would suggest some more descriptive variable names and argument names. Putting it all together, the function could look like this:

func permutations(of number: Int) -> [Int] {

    var permutations = [Int]()

    func addPermutations(of digits: [UInt8], withSuffix suffix: [UInt8]) {
        if digits.isEmpty {
            permutations.append( Int(decimalDigits: suffix) )
        } else {
            for i in digits.indices {
                var remainingDigits = digits
                let currentDigit = [remainingDigits.remove(at: i)]
                addPermutations(of: remainingDigits, withSuffix: currentDigit + suffix)
            }
        }
    }

    addPermutations(of: number.decimalDigits, withSuffix: [])
    return (permutations)
}

print(permutations(of: 123))
// [123, 213, 132, 312, 231, 321]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.