We give better lower bounds for M(n, d), for various positive integers d and n with d < n, where M(n, d) is the largest number of permutations on n symbols with pairwise Hamming distance at least d. Larger 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, Parallel Partition and Extension, is universally applicable to constructing such sets for all n and all d, d < n.