Swift permutations of the digits of an Integer

Question

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?

• user1118321: 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"?
• stevenpcurtis: Exactly. That is correct.
• ielyamani: 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.
• ielyamani: In addition, this code doesn't work for numbers with duplicate digits: There should be only one possible permutation for numbers like 1111, ...

Answer 1

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.

Answer 2

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]