Code 1 - SW’s

mincase[rule_,s_Integer]:=First[Sort[Map[Sort,(rule/.#)&/@(Thread[Range[s]#]&/@Permutations[Range[s]]),{2}]]]
In[]:=

Code 2 - EdP’s

PutInStandardOrder[rule_Rule]:=Module[{alphabet,s,t,convertedrule,parts},​​alphabet=Union[Flatten[Table[rule[[n]],{n,1,Length[rule]}]]];​​s=Length[alphabet];​​convertedrule=rule/.Thread[alphabetRange[s]];​​parts=Table[SortBy[convertedrule[[n]],{-Length[#],-PadRight[Length/@Split[#],Length[#]],#}&],{n,1,2}];​​convertedrule=convertedrule/.Thread[DeleteDuplicates[Flatten[parts]]Range[s]];​​parts=Table[SortBy[convertedrule[[n]],{-Length[#],#}&],{n,1,2}];​​Rule@@parts]
In[]:=
CanonRule[rule_Rule]:=Module[{standard,r,s,partR,orderstart,ordering,parts},​​standard=PutInStandardOrder[rule];​​{r,s}=Table[Max[Flatten[standard[[n]]]],{n,1,Length[standard]}];​​If[s<r,s=r];​​partR=First[Sort[{SortBy[(standard[[1]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[r]#]&/@Permutations[Range[r]])]];​​orderstart=partR[[2]];​​ordering=Switch[​​s-r,​​0,orderstart,​​1,Append[orderstart,s],​​_,Last[First[Sort[{SortBy[(standard[[2]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[s]Join[orderstart,#]]&/@Permutations[Range[r+1,s]])]]]];​​parts=Table[SortBy[standard[[n]]/.Thread[Range[s]ordering],{-Length[#],#}&],{n,1,2}];​​Rule@@parts];
In[]:=

Code 3 - SushmaK’s merger

FindCanonicalWolframModel[rule_Rule]:=Module[{alphabet,s,t,convertedrule,parts},​​alphabet=Union[Flatten[Table[rule[[n]],{n,1,Length[rule]}]]];​​s=Length[alphabet];​​convertedrule=rule/.Thread[alphabetRange[s]];​​First[Sort[Map[SortBy[#,{-Length[#],#}&]&,(convertedrule/.#)&/@(Thread[Range[s]#]&/@Permutations[Range[s]]),{2}]]]]
In[]:=

Code 4 - EdP’s update

NewPutInStandardOrder[rule_Rule]:=Module[{alphabet,s,t,convertedrule,convertedrule2,tally,parts,parts2},​​alphabet=Union[Flatten[Table[rule[[n]],{n,1,Length[rule]}]]];​​s=Length[alphabet];​​convertedrule=rule/.Thread[alphabetRange[s]];​​parts=Table[SortBy[convertedrule[[n]],{-Length[#],-PadRight[Length/@Split[#],Length[#]],#}&],{n,1,2}];​​convertedrule=convertedrule/.Thread[DeleteDuplicates[Flatten[parts]]Range[s]];​​parts=Table[SortBy[convertedrule[[n]],{-Length[#],#}&],{n,1,2}];​​tally=First/@SortBy[Tally[First[DeleteDuplicates[#]]&/@Select[Flatten[Join[parts],1],Length[#]>0&]],-Last[#]&];​​convertedrule2=convertedrule/.Thread[tallySort[tally]];​​parts2=Table[SortBy[convertedrule2[[n]],{-Length[#],#}&],{n,1,2}];​​First[Sort[{Rule@@parts,Rule@@parts2}]]]
In[]:=
NewCanonRule[rule_Rule]:=Module[{standard,r,s,partR,partS,orderstart,ordering,parts},​​standard=NewPutInStandardOrder[rule];​​{r,s}=Table[Max[Flatten[standard[[n]]]],{n,1,Length[standard]}];​​If[s<r,s=r];​​partR=First[Sort[{SortBy[(standard[[1]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[r]#]&/@Permutations[Range[r]])]];​​partS=First[Sort[{SortBy[(standard[[2]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[r]Prepend[#,1]]&/@Permutations[Range[2,r]])]];​​orderstart={partR[[2]],partS[[2]]};​​ordering=Switch[​​s-r,​​0,{orderstart[[1]],orderstart[[1]]},​​1,{Append[orderstart[[1]],s],Append[orderstart[[1]],s]},​​_,Table[Last[First[Sort[{SortBy[(standard[[2]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[s]Join[orderstart[[k]],#]]&/@Permutations[Range[r+1,s]])]]],{k,1,2}]];​​parts=First[Sort[Table[Table[SortBy[standard[[n]]/.Thread[Range[s]ordering[[k]]],{-Length[#],#}&],{n,1,2}],{k,1,2}]]];​​Rule@@parts];
In[]:=
NewFindCanonicalWolframModel[rule_Rule]:=NewCanonRule[rule]
In[]:=

Tests

Example 1

mincase[{{2,3,3}}{{3,2,2},{2,1,1}},3]//AbsoluteTiming
In[]:=
{0.000179,{{1,2,2}}{{1,3,3},{2,1,1}}}
Out[]=
CanonRule[{{2,3,3}}{{3,2,2},{2,1,1}}]//AbsoluteTiming
In[]:=
{0.000427,{{1,2,2}}{{1,3,3},{2,1,1}}}
Out[]=
FindCanonicalWolframModel[{{2,3,3}}{{3,2,2},{2,1,1}}]//AbsoluteTiming
In[]:=
{0.000328,{{1,2,2}}{{1,3,3},{2,1,1}}}
Out[]=
NewFindCanonicalWolframModel[{{2,3,3}}{{3,2,2},{2,1,1}}]//AbsoluteTiming
In[]:=
{0.000485,{{1,2,2}}{{1,3,3},{2,1,1}}}
Out[]=

Example 2

mincase[{{a,e,d},{d,c},{c,b},{b,a}}{{}},5]//AbsoluteTiming
In[]:=
{0.003884,{{b,a},{c,b},{d,c},{a,e,d}}{{}}}
Out[]=
CanonRule[{{a,e,d},{d,c},{c,b},{b,a}}{{}}]//AbsoluteTiming
In[]:=
{0.003471,{{1,2,3},{3,4},{4,5},{5,1}}{{}}}
Out[]=
FindCanonicalWolframModel[{{a,e,d},{d,c},{c,b},{b,a}}{{}}]//AbsoluteTiming
In[]:=
{0.004121,{{1,2,3},{3,4},{4,5},{5,1}}{{}}}
Out[]=
NewFindCanonicalWolframModel[{{a,e,d},{d,c},{c,b},{b,a}}{{}}]//AbsoluteTiming
In[]:=
{0.003293,{{1,2,3},{3,4},{4,5},{5,1}}{{}}}
Out[]=

Example 3

mincase[{{2,5},{5,2},{2,3,1},{5,0,4},{4,9,4,8}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6},{9,8,7,2}},14]//AbsoluteTiming
In[]:=
CanonRule[{{2,5},{5,2},{2,3,1},{5,0,4},{4,9,4,8}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6},{9,8,7,2}}]//AbsoluteTiming
In[]:=
Out[]=
FindCanonicalWolframModel[{{2,5},{5,2},{2,3,1},{5,0,4},{4,9,4,8}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6},{9,8,7,2}}]//AbsoluteTiming
General
:The current computation was aborted because there was insufficient memory available to complete the computation.
Throw
:Uncaught SystemException returned to top level. Can be caught with Catch[…, _SystemException].
SystemException[MemoryAllocationFailure]
NewFindCanonicalWolframModel[{{2,5},{5,2},{2,3,1},{5,0,4},{4,9,4,8}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6},{9,8,7,2}}]//AbsoluteTiming
In[]:=
Out[]=

Example 4

mincase[{{1,1},{2,2}}{{2,2}},2]//AbsoluteTiming
In[]:=
{0.000166,{{1,1},{2,2}}{{1,1}}}
Out[]=
CanonRule[{{1,1},{2,2}}{{2,2}}]//AbsoluteTiming
In[]:=
{0.000271,{{1,1},{2,2}}{{2,2}}}
Out[]=
FindCanonicalWolframModel[{{1,1},{2,2}}{{2,2}}]//AbsoluteTiming
In[]:=
{0.000228,{{1,1},{2,2}}{{1,1}}}
Out[]=
NewFindCanonicalWolframModel[{{1,1},{2,2}}{{2,2}}]//AbsoluteTiming
In[]:=
{0.000323,{{1,1},{2,2}}{{1,1}}}
Out[]=

Example 5: all 3 sub examples should produce same canonical form

mincase

mincase[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}},6]//AbsoluteTiming
In[]:=
{0.024663,{{0,1},{0,2},{0,3}}{{1,4},{2,5},{4,2},{4,5},{4,6},{5,1},{5,4},{5,6},{6,3},{6,4},{6,5}}}
Out[]=
mincase[{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}},6]//AbsoluteTiming
In[]:=
{0.023306,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
mincase[{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}},6]//AbsoluteTiming
In[]:=
{0.024763,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=

CanonRule

CanonRule[{{2,5},{5,2},{2,3,1},{5,0,4},{4,9,4,8}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6},{9,8,7,2}}]//Timing
{1.51563,{{1,2,1,3},{4,5,1},{6,7,8},{4,6},{6,4}}{{2,3,9,6},{1,10,11},{2,12,7},{8,3,9},{13,14,15},{2,3},{3,2},{9,11},{10,13},{11,9},{12,14},{13,10},{14,12}}}
CanonRule[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]//AbsoluteTiming
{0.001593,{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}}
Out[]=
CanonRule[{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.001416,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
CanonRule[{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.001771,{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}}
Out[]=

FindCanonicalWolframModel

FindCanonicalWolframModel[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]//AbsoluteTiming
In[]:=
{0.217031,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
FindCanonicalWolframModel[{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.217529,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
FindCanonicalWolframModel[{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.217924,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=

NewFindCanonicalWolframModel

NewFindCanonicalWolframModel[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]//AbsoluteTiming
In[]:=
{0.002886,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
NewFindCanonicalWolframModel[{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.001665,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=
NewFindCanonicalWolframModel[{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}]//AbsoluteTiming
In[]:=
{0.001617,{{1,2},{1,3},{1,4}}{{2,5},{3,6},{5,3},{5,6},{5,7},{6,2},{6,5},{6,7},{7,4},{7,5},{7,6}}}
Out[]=