0
$\begingroup$

I find the problem of calculating $n \times n$ Young tableaux from here. I can get the number of $3\times 3$ Young tableaux by violent enumeration is $42$

Partition[#, 3] & /@ 
  Select[Permutations[
    Range[9]], ((#[[2]] > #[[1]]) && (#[[3]] > #[[2]]) && (#[[5]] > \
#[[4]]) && (#[[6]] > #[[5]]) && (#[[8]] > #[[7]]) && (#[[9]] > \
#[[8]]) && (#[[1]] < #[[4]]) && (#[[4]] < \
#[[7]]) && (#[[2]] < #[[5]]) && (#[[5]] < #[[8]]) && (#[[3]] < \
#[[6]]) && (#[[6]] < #[[9]])) &] // Length

But in the case of $4\times 4$, the calculation speed of my algorithm below is very slow. How can I modify it to improve the calculation speed?

Needs["Combinatorica`"]
s = {};
k = 0;
rule = ((#[[1]] < #[[2]]) && (#[[2]] < #[[3]]) && (#[[3]] < #[[4]]) \
&& (#[[5]] < #[[6]]) && (#[[6]] < #[[7]]) && (#[[7]] < #[[8]]) && \
(#[[9]] < #[[10]]) && (#[[10]] < #[[11]]) && (#[[11]] < #[[12]]) && \
(#[[13]] < #[[14]]) && (#[[14]] < #[[15]]) && (#[[15]] < #[[16]]) && \
(#[[1]] < #[[5]]) && (#[[5]] < #[[9]]) && (#[[9]] < #[[13]]) && \
(#[[2]] < #[[6]]) && (#[[6]] < #[[10]]) && (#[[10]] < #[[14]]) && \
(#[[3]] < #[[7]]) && (#[[7]] < #[[11]]) && (#[[11]] < #[[15]]) && \
(#[[4]] < #[[8]]) && (#[[8]] < #[[12]]) && (#[[12]] < #[[16]])) &;

For[i = 1, i <= 16! - 1, i++, 
 If[MatchQ[Combinatorica`NthPermutation[i, Range[16]], _?(rule)], 
  k++;]]
k
$\endgroup$
1
  • $\begingroup$ @Bill Thank you for pointing out the typo. I wrote (#[[1]]<#[[4]]) again in that place. And I have updated my question. $\endgroup$ Commented Mar 1, 2020 at 5:29

1 Answer 1

4
$\begingroup$

Here is a recursive code that constructs the Young tableaux directly:

fill[L_, x_] := If[x == Length[L]^2 + 1, Sow[L],
  fill[#, x + 1] & /@ Reap[Do[If[Length[L[[i]]] < Length[L] &&
                                 (i == 1 || Length[L[[i]]] < Length[L[[i - 1]]]), 
                                 Sow[ReplacePart[L, i -> Append[L[[i]], x]]]],
                              {i, Length[L]}]][[2, 1]]]
YT[n_] := Reap[fill[ConstantArray[{}, n], 1]][[2, 1]]

You get the 24'024 Young tableaux $4\times4$ in about two seconds:

YT[4]
(*    {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}},
       {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 13}, {12, 14, 15, 16}},
       {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 14}, {12, 13, 15, 16}},
       {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 15}, {12, 13, 14, 16}},
       {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 12, 13}, {11, 14, 15, 16}},
       ...
       {{1, 5, 9, 11}, {2, 6, 10, 14}, {3, 7, 12, 15}, {4, 8, 13, 16}},
       {{1, 5, 9, 12}, {2, 6, 10, 13}, {3, 7, 11, 14}, {4, 8, 15, 16}},
       {{1, 5, 9, 12}, {2, 6, 10, 13}, {3, 7, 11, 15}, {4, 8, 14, 16}},
       {{1, 5, 9, 12}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 13, 16}},
       {{1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12, 16}}}    *)

As for the 701'149'020 Young tableaux $5\times5$, further optimizations may be necessary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.