  We give new lower bounds for $M(n,d)$, for various positive integers $n$ and
$d$ with $n>d$, where $M(n,d)$ is the largest number of permutations on $n$
symbols with pairwise Hamming distance at least $d$. Large sets of permutations
on $n$ symbols with pairwise Hamming distance $d$ is a necessary component of
constructing error correcting permutation codes, which have been proposed for
power-line communications. Our technique, {\em partition and extension}, is
universally applicable to constructing such sets for all $n$ and all $d$,
$d<n$. We describe three new techniques, {\em sequential partition and
extension}, {\em parallel partition and extension}, and a {\em modified
Kronecker product operation}, which extend the applicability of partition and
extension in different ways. We describe how partition and extension gives
improved lower bounds for M(n,n-1) using mutually orthogonal Latin squares
(MOLS). We present efficient algorithms for computing new partitions: an
iterative greedy algorithm and an algorithm based on integer linear
programming. These algorithms yield partitions of positions (or symbols) used
as input to our partition and extension techniques. We report many new lower
bounds for for $M(n,d)$ found using these techniques for $n$ up to $600$.
