We are interested in the following notions in the case $G=S_N$, the symmetric group on $\{1,\dots,N\}$.

Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\dots,g_d)^x := (g_1^x,\dots,g_d^x).$$
(Throughout, $g^x:=x^{-1}gx$.)
$d$-tuples $g=(g_1,\dots,g_d)$ and $h=(h_1,\dots,h_d)$ in $G^d$ are *conjugate* if there is $x\in G$ such that (in the above notation) $g^x=h$.
The ($d$-dimensional) *Simultaneous Conjugacy Problem (SCP)* is $G$ is that of deciding whether
given $d$-tuples $g,h\in G^d$ are conjugate.

We need an efficient solution of the SCP in the symmetric group $S_N$. (In fact, for our specific use we are more interested in the *search* version of this problem (given conjugate $g,h\in G^d$, find $x\in G$ such that $g^x=h$), if that matters.)

One very nice way to solve the SCP is to come up with efficiently computable representatives of conjugacy classes. For ordinary (1-dimensional) conjugacy this is trivial: E.g., the representative of the conjugacy class of the permutation $(7, 9, 5, 3)(1, 2, 4)(6,8)\in S_9$ would be $(1,2,3,4)(5,6,7)(8,9)$. For larger dimension $d$, one can define the representative as follows:

Define a linear order on $S_N$ as follows: Given $g$, order its cycles from longest to shortest. Make each cycle begin with its minimal element, and order every set of cycles of equal length by their first element. This results in a sequence of $N$ natural numbers. Compare two permutations by comparing their corresponding sequences, lexicographically.

Given $(g_1,\dots,g_d)\in S_N^d$, bring $g_1$ by conjugation to the above canonical form $\tilde g_1$. Then minimize $g_2$ by conjugation with elements of the centeralizer of $\tilde g_1$ to obtain $\tilde g_2$, then minimize $g_3$ by conjugation with elements of the centeralizer of $\{\tilde g_1,\tilde g_2\}$ to obtain $\tilde g_3$, etc. The canonical representative is $(\tilde g_1,\dots,\tilde g_d)$ (and we can also keep track how to conjugate there).

**Question:** In the above notation, can we find $(\tilde g_1,\dots,\tilde g_d)$ in polynomial time?

Of course, I would appreciate any efficient solution of the SCP.

*Comments:*

In each stage, one can take generators of the centralizers, compute the orbits using them, and choose the minimal elements. This is better than conjugating by the whole centralizer, but seems inefficient in the worst case.

This algorithm is needed to speed up an algorithm for the SCP in Artin's braid group $B_N$.

The answers for a related question do not seem to help here.