6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – hjpotter92 Apr 16 '18 at 3:59
5
\$\begingroup\$

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()
\$\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.