Here is an improved version that should be considerably faster. The main improvements are:
So, 17.5 seconds is spent just converting the permutations to the desired output. This is slow because the list is a mixture of symbols and integers. In other words, the output cannot be packed. If the input consisted strictly of integers, than the output could be packed, and the function would be much faster. For example, suppose the input is:
$\begin{array}{l}
\{a,1\},\{b,1\},\{c,2\},\{d,2\},\{e,2\},\{f,3\} \\
\{a,1\},\{b,1\},\{c,2\},\{d,2\},\{f,3\},\{e,2\} \\
\{a,1\},\{b,1\},\{c,2\},\{f,3\},\{d,2\},\{e,2\} \\
\{a,1\},\{b,1\},\{f,3\},\{c,2\},\{d,2\},\{e,2\} \\
\{a,1\},\{c,2\},\{b,1\},\{d,2\},\{e,2\},\{f,3\} \\
\{a,1\},\{c,2\},\{b,1\},\{d,2\},\{f,3\},\{e,2\} \\
\{a,1\},\{c,2\},\{b,1\},\{f,3\},\{d,2\},\{e,2\} \\
\{a,1\},\{c,2\},\{d,2\},\{b,1\},\{e,2\},\{f,3\} \\
\{a,1\},\{c,2\},\{d,2\},\{b,1\},\{f,3\},\{e,2\} \\
\{a,1\},\{c,2\},\{d,2\},\{e,2\},\{b,1\},\{f,3\} \\
\{a,1\},\{c,2\},\{d,2\},\{e,2\},\{f,3\},\{b,1\} \\
\{a,1\},\{c,2\},\{d,2\},\{f,3\},\{b,1\},\{e,2\} \\
\{a,1\},\{c,2\},\{d,2\},\{f,3\},\{e,2\},\{b,1\} \\
\{a,1\},\{c,2\},\{f,3\},\{b,1\},\{d,2\},\{e,2\} \\
\{a,1\},\{c,2\},\{f,3\},\{d,2\},\{b,1\},\{e,2\} \\
\{a,1\},\{c,2\},\{f,3\},\{d,2\},\{e,2\},\{b,1\} \\
\{a,1\},\{f,3\},\{b,1\},\{c,2\},\{d,2\},\{e,2\} \\
\{a,1\},\{f,3\},\{c,2\},\{b,1\},\{d,2\},\{e,2\} \\
\{a,1\},\{f,3\},\{c,2\},\{d,2\},\{b,1\},\{e,2\} \\
\{a,1\},\{f,3\},\{c,2\},\{d,2\},\{e,2\},\{b,1\} \\
\{c,2\},\{a,1\},\{b,1\},\{d,2\},\{e,2\},\{f,3\} \\
\{c,2\},\{a,1\},\{b,1\},\{d,2\},\{f,3\},\{e,2\} \\
\{c,2\},\{a,1\},\{b,1\},\{f,3\},\{d,2\},\{e,2\} \\
\{c,2\},\{a,1\},\{d,2\},\{b,1\},\{e,2\},\{f,3\} \\
\{c,2\},\{a,1\},\{d,2\},\{b,1\},\{f,3\},\{e,2\} \\
\{c,2\},\{a,1\},\{d,2\},\{e,2\},\{b,1\},\{f,3\} \\
\{c,2\},\{a,1\},\{d,2\},\{e,2\},\{f,3\},\{b,1\} \\
\{c,2\},\{a,1\},\{d,2\},\{f,3\},\{b,1\},\{e,2\} \\
\{c,2\},\{a,1\},\{d,2\},\{f,3\},\{e,2\},\{b,1\} \\
\{c,2\},\{a,1\},\{f,3\},\{b,1\},\{d,2\},\{e,2\} \\
\{c,2\},\{a,1\},\{f,3\},\{d,2\},\{b,1\},\{e,2\} \\
\{c,2\},\{a,1\},\{f,3\},\{d,2\},\{e,2\},\{b,1\} \\
\{c,2\},\{d,2\},\{a,1\},\{b,1\},\{e,2\},\{f,3\} \\
\{c,2\},\{d,2\},\{a,1\},\{b,1\},\{f,3\},\{e,2\} \\
\{c,2\},\{d,2\},\{a,1\},\{e,2\},\{b,1\},\{f,3\} \\
\{c,2\},\{d,2\},\{a,1\},\{e,2\},\{f,3\},\{b,1\} \\
\{c,2\},\{d,2\},\{a,1\},\{f,3\},\{b,1\},\{e,2\} \\
\{c,2\},\{d,2\},\{a,1\},\{f,3\},\{e,2\},\{b,1\} \\
\{c,2\},\{d,2\},\{e,2\},\{a,1\},\{b,1\},\{f,3\} \\
\{c,2\},\{d,2\},\{e,2\},\{a,1\},\{f,3\},\{b,1\} \\
\{c,2\},\{d,2\},\{e,2\},\{f,3\},\{a,1\},\{b,1\} \\
\{c,2\},\{d,2\},\{f,3\},\{a,1\},\{b,1\},\{e,2\} \\
\{c,2\},\{d,2\},\{f,3\},\{a,1\},\{e,2\},\{b,1\} \\
\{c,2\},\{d,2\},\{f,3\},\{e,2\},\{a,1\},\{b,1\} \\
\{c,2\},\{f,3\},\{a,1\},\{b,1\},\{d,2\},\{e,2\} \\
\{c,2\},\{f,3\},\{a,1\},\{d,2\},\{b,1\},\{e,2\} \\
\{c,2\},\{f,3\},\{a,1\},\{d,2\},\{e,2\},\{b,1\} \\
\{c,2\},\{f,3\},\{d,2\},\{a,1\},\{b,1\},\{e,2\} \\
\{c,2\},\{f,3\},\{d,2\},\{a,1\},\{e,2\},\{b,1\} \\
\{c,2\},\{f,3\},\{d,2\},\{e,2\},\{a,1\},\{b,1\} \\
\{f,3\},\{a,1\},\{b,1\},\{c,2\},\{d,2\},\{e,2\} \\
\{f,3\},\{a,1\},\{c,2\},\{b,1\},\{d,2\},\{e,2\} \\
\{f,3\},\{a,1\},\{c,2\},\{d,2\},\{b,1\},\{e,2\} \\
\{f,3\},\{a,1\},\{c,2\},\{d,2\},\{e,2\},\{b,1\} \\
\{f,3\},\{c,2\},\{a,1\},\{b,1\},\{d,2\},\{e,2\} \\
\{f,3\},\{c,2\},\{a,1\},\{d,2\},\{b,1\},\{e,2\} \\
\{f,3\},\{c,2\},\{a,1\},\{d,2\},\{e,2\},\{b,1\} \\
\{f,3\},\{c,2\},\{d,2\},\{a,1\},\{b,1\},\{e,2\} \\
\{f,3\},\{c,2\},\{d,2\},\{a,1\},\{e,2\},\{b,1\} \\
\{f,3\},\{c,2\},\{d,2\},\{e,2\},\{a,1\},\{b,1\} \\
\end{array}$
Permutations[myList]
and removing the duplicates. I really at a loss at how to approach this problem. $\endgroup$