Downset calculation code

I'm looking to port a Python script I have over to Swift, partly for some performance benefits, and partly to dip my toe into a new language.

My program computes what is called the downset of a permutation of $[n] := \{1,2,\cdots,n\}$. For me, a permutation of $[n]$ is a tuple containing each integer precisely once. Deleting the entry $\pi(i)$ from a permutation $\pi = \pi(1) \pi(2) \cdots \pi(n)$ produces a permutation $\sigma = \pi(1) \pi(2) \cdots \pi(i-1) \pi(i+1) \cdots \pi(n)$ with each entry larger than $\pi(i)$ lowered by $1$. The downset of a permutation is the set of all permutations which can be obtained by a sequence of such deletions. I'm calculating it so that the downset is sorted by rank: I'll return an array L such that L[m] is the set of permutations in the downset of length m.

Here's the working Python3 code I have:

def one_deletion(sigma,i):
""" Deletes by value, not by index.
"""
smaller_perm = tuple(val if val < i else val-1 for val in sigma if val != i)
return smaller_perm

def downset(pi):
L = []
new_perms = {pi}
L.append(new_perms)
for _ in range(len(pi)):
old_perms = new_perms
new_perms = set()
for sigma in old_perms:
new_perms.update(one_deletion(sigma,i) for i in sigma)
L.append(new_perms)
return L[::-1]

if __name__ == "__main__":
u3 = tuple([2,5,3,1,4])
print(downset(u3))


In trying to port this to Swift code, I've learned a lot! Here's my code:

struct Permutation: Hashable {
let perm : Array<Int>
var hashValue: Int {
return perm.description.hashValue
}
static func == (lhs: Permutation, rhs: Permutation) -> Bool {
return lhs.perm == rhs.perm
}
}

func one_deletion (sigma: Permutation, i: Int) -> Permutation {
var A = [Int]() // Empty array of integers
for val in sigma.perm {
if val < i {
A.append(val)
} else if val > i {
A.append(val-1)
}
}
let B = Permutation(perm:A)
return B
}

func downset (pi: Permutation) -> [Set<Permutation>] {
var L = [Set<Permutation>]()
var new_perms = Set([pi])
L.append(new_perms)

for _ in pi.perm {
let old_perms = new_perms
new_perms = []
for sigma in old_perms {
for val in sigma.perm {
new_perms.insert(one_deletion(sigma:sigma, i:val))
}
}
L.append(new_perms)
}
return L
}

let u3 = Permutation(perm:[2,5,3,1,4])
print(downset(pi: u3))


Now, some questions!

1. Is there a better way to make an array of integers hashable in Swift? Here, two Permutation objects are the same when they're literally the same tuple, so hashing by description works.
2. Are there any obvious things I'm doing wrong in Swift? In practice, this code is slower than my Python code.

Any general purpose comments are encouraged as well.

• Could you provide a sample of the outputs of the program with some input values? Because I did not understand what a downset permutation actually is. Apr 16, 2018 at 3:59

Naming

According to the Swift API Design Guidelines,

Names of types and protocols are UpperCamelCase. Everything else is lowerCamelCase

therefore it should be func oneDeletion, oldPerms, newPerms etc.

Some variable names such as A, L are non-descriptive.

I would use a different name for the array inside struct Permutation, for example

struct Permutation: Hashable {
let sigma: [Int]
// ...
}


so that perm can be used for a Permutation variable without causing confusion. (This is of course opinion-based.)

Hashing

You don't need to implement

static func == (lhs: Permutation, rhs: Permutation) -> Bool


because that is automatically synthesized in Swift 4.1. A future version of Swift will also synthesize the hashValue automatically, this is currently discussed at

and implemented in https://github.com/apple/swift/pull/15382.

Until that is implemented, you have to provide a hashValue method. I would probably not choose the description method because that requires a conversion to strings. A good choice would be the _combineHashValues function in Hashing.swift from the above pull request, this is also what hash.hpp from the Boost library uses:

// From https://github.com/lorentey/swift/blob/e03cb1340ad89013bbaef1c4f802a72de06e9e1a/stdlib/public/core/Hashing.swift
func combineHashValues(_ firstValue: Int, _ secondValue: Int) -> Int {
let magic = 0x9e3779b9 as UInt
var x = UInt(bitPattern: firstValue)
x ^= UInt(bitPattern: secondValue) &+ magic &+ (x &<< 6) &+ (x &>> 2)
return Int(bitPattern: x)
}

struct Permutation: Hashable {
let sigma: [Int]

var hashValue: Int {
return sigma.reduce(0, combineHashValues)
}

// ...
}


Use functional methods

The loop

var A = [Int]() // Empty array of integers
for val in sigma.perm {
if val < i {
A.append(val)
} else if val > i {
A.append(val-1)
}
}


in func one_deletion can be simplified using compactMap:

let a = sigma.perm.compactMap { val in
val < i ? val : val > i ? val - 1 : nil
}


and in func downset the inner loop

        for val in sigma.perm {
new_perms.insert(one_deletion(sigma:sigma, i:val))
}


can be simplified using map:

        new_perms.formUnion(sigma.perm.map { one_deletion(sigma: sigma, i: $0) } )  Define instance methods Both func one_deletion and func downset operate on an instance of struct Permutation, therefore I would replace the free functions by instance methods: struct Permutation: Hashable { // ... func deleting(i: Int) -> Permutation { /* ... */ } func downset() -> [Set<Permutation>] { /* ... */ } }  which would then be used as let reduced = perm.deleting(val: i)  or let ds = perm.downset()  Further remarks Array<Int> and [Int] are equivalent notations for an array of integers, but I would suggest to use only one of them consistently. The comment in var A = [Int]() // Empty array of integers  is useless, and here let B = Permutation(perm:A) return B  the intermediate variable is not needed. Instead of re-initializing the set with an empty set  new_perms = []  it might be more efficient to call  new_perms.removeAll(keepingCapacity: true)  to avoid subsequence reallocations of the element storage. Putting it all together // From https://github.com/lorentey/swift/blob/e03cb1340ad89013bbaef1c4f802a72de06e9e1a/stdlib/public/core/Hashing.swift func combineHashValues(_ firstValue: Int, _ secondValue: Int) -> Int { let magic = 0x9e3779b9 as UInt var x = UInt(bitPattern: firstValue) x ^= UInt(bitPattern: secondValue) &+ magic &+ (x &<< 6) &+ (x &>> 2) return Int(bitPattern: x) } struct Permutation: Hashable { let sigma: [Int] var hashValue: Int { return sigma.reduce(0, combineHashValues) } func deleting(val: Int) -> Permutation { let newSigma = sigma.compactMap { j in j < val ? j : j > val ? j - 1 : nil } return Permutation(sigma: newSigma) } func downset() -> [Set<Permutation>] { var newPerms = Set([self]) var result = [newPerms] for _ in 0..<sigma.count { let oldPerms = newPerms newPerms.removeAll(keepingCapacity: true) for perm in oldPerms { newPerms.formUnion(perm.sigma.map { perm.deleting(val:$0)} )
}
result.append(newPerms)
}

return result
}
}

let u3 = Permutation(sigma: [2,5,3,1,4])
let ds = u3.downset()