\datethis @*Intro. A quick program to output the domination'' or majorization'' relation when it is defined on permutations of multisets instead of on partitions. Let's say that digits are permuted. Then $x_1\ldots x_n\succeq y_1\ldots y_n$ if and only if $\sum_{i=1}^j [x_i\ge k]\ge\sum_{i=1}^j [y_i\ge k]$ for all $j$ and~$k$. This relation is self-dual in the sense that $x_1\ldots x_n\succeq y_1\ldots y_n$ if and only if $x_n\ldots x_1\preceq y_n\ldots y_1$. And if the digits consist of equal quantities of the numbers 1~through~$k$, then $x_1\ldots x_n\succeq y_1\ldots y_n$ if and only if $\bar x_1\ldots\bar x_n\preceq \bar y_1\ldots\bar y_n$, where $\bar x= k+1-x$. It's emphatically {\it not\/} a lattice, in most cases. Here I just compute the relation and its transitive reduction by brute force. When I learn better algorithms for transitive reduction, I can use this as an interesting example. (Well, maybe not! In the examples I tried, we seem to have $x$ covers $y$ if and only if $x$ differs from $y$ by a transposition and $x$ has exactly one more inversion than $y$. Furthermore, it appears that the covering relation on multiset permutations such as $\{1,1,2,2,3\}$ is obtained by taking the relation on set permutations $\{1,1',2,2',3\}$ and removing all cases in which $1'$ occurs before~1 or $2'$ before~2. Thus, some additional theory apparently lurks in the background, making this whole program unnecessary --- except as a way to confirm the conjectures in further cases before I go ahead and find proofs.) @d maxn 63 /* this many elements at most */ @d maxp 1000 /* this many perms at most */ @c #include #include char perm[maxp][maxn+1]; /* the permutations */ char work[maxn+1]; /* where I generate new ones */ char rel[maxp][maxp]; /* nonzero if $x\prec y$ */ char red[maxp][maxp]; /* reduced relation */ main(int argc, char*argv[]) { register int i,j,k,l,ll,m,n,s,dom; @; @; @; @; @; } @ @= if (argc!=2) { fprintf(stderr,"Usage: %s digits_to_permute\n",argv[0]); exit(-1); } for (j=0;argv[1][j];j++) { if (j>maxn) { fprintf(stderr,"String too long (maxn=%d)!\n",maxn); exit(-2); } if (argv[1][j]<'0' || argv[1][j]>'9') { fprintf(stderr,"The string %s should contain digits only!\n",argv[1]); exit(-3); } if (j>0 && argv[1][j-1]>argv[1][j]) { fprintf(stderr,"The string %s should be nondecreasing!\n",argv[1]); exit(-4); } work[j+1]=argv[1][j]; } n=j; @ Here I use ye olde Algorithm 7.2.1.2L. @= m=0; l1:@+ if (m==maxp) { fprintf(stderr,"Too many permutations (maxp=%d)!\n",maxp); exit(-5); } for (j=0;j=work[j+1];j--); if (j==0) goto done; l3:@+ for (l=n;work[j]>=work[l];l--); s=work[j],work[j]=work[l],work[l]=s; l4:@+ for (k=j+1,l=n;k= for (l=0;l=k? 1: 0)-(perm[ll][i]>=k? 1: 0); if (s>0) goto fin; if (s<0) dom=1; } if (dom) rel[l][ll]=1; fin: continue; } @ Hey, I'm just using brute force today. @= for (l=0;l= for (l=0;l