=
for (k=d;del[k]<=0;k--) del[k]=-del[k];
if (sig[k]==0) break; /* all but |del[k]| were negative or zero */
del[k]=-del[k]; /* some entry preceding |del[k]| is positive */
@ We use the mixed-radix addition technique again when generating moves.
@~~y$ and $x$ precedes $y$ from left to right, counting
multiplicity. For example, 2010 has four inversions, corresponding to
$xy\in\{20,21,20,10\}$. When two permutations are adjacent, one of
them has exactly one more inversion than the other. It is not
difficult to verify that the number of inversions of a permutation is
equal to the distance in the graph from that permutation to the
lexicographically first permutation.
Parameters |n0| through |n4| specify the composition of the multiset,
just as in the |subsets| routine.
Roughly speaking, there are |n0| elements equal to~0, |n1| elements
equal to~1, and so on. The multiset $\{0,0,1,2,3,3\}$ would, for example,
be represented by |(n0,n1,n2,n3,n4)=(2,1,1,2,0)|.
Of course, we sometimes want to have multisets with more than five distinct
elements; when there are $d+1$ distinct elements, the multiset should have
$n_k$ elements equal to~$k$ and $n=n_0+n_1+\cdots+n_d$ elements in all.
The value of $d$ can be specified by making |n0=-d| (in which case
each multiplicity $n_k$ is taken to be~1); or by making |n0>0| and |n1=-d|
(in which case each multiplicity $n_k$ is taken to be equal to~|n0|); or
|n0>0|, |n1>0|, |n2=-d| (in which case the multiplicities are alternately
$(|n0|,|n1|,|n0|,|n1|,|n0|,\ldots\,)$); or |n0>0|, |n1>0|, |n2>0|, |n3=-d|,
(in which case the multiplicities are the first~|d+1| elements of the
periodic sequence $(|n0|,|n1|,|n2|,|n0|,|n1|,\ldots\,)$); or all
but |n4| are positive, while |n4=-d| (in which case the multiplicities again
are periodic).
An example like |(n0,n1,n2,n3,n4)=(1,2,3,4,-8)| is about as tricky
as you can get. It specifies the multiset $\{0,1,1,2,2,2,3,3,3,3,4,5,5,
6,6,6,7,7,7,7,8\}$.
If any of the multiplicity parameters is negative or zero, the
remaining multiplicities are ignored. For example, if |n2<=0|, the
subroutine does not look at |n3| or~|n4|.
You probably don't want to try |perms(n0,0,0,0,0,max_inv,directed)|
when |n0>0|, because a multiset with |n0| identical elements has only
one permutation.
The special case when you want all $n!$ permutations of an $n$-element set
can be obtained by calling |all_perms(n,directed)|.
@(gb_basic.h@>=
#define all_perms(n,directed) @[perms(1-n,0,0,0,0,0,directed)@]
@ If |max_inv=0|, all permutations will be considered, regardless of
the number of inversions. In that case the total number of vertices in
the graph will be the multinomial coefficient $${n\choose
n_0,n_1,\ldots,n_d}\,,\qquad n=n_0+n_1+\cdots+n_d.$$ The maximum
number of inversions in general is the number of inversions of the
lexicographically last permutation, namely ${n\choose2}-{n_0\choose2}-
{n_1\choose2}-\cdots-{n_d\choose2}=\sum_{0\le j~~__v.v; /* then we look for prior lines that touch the other one */
for (a=v->arcs;a;a=a->next) {
vv=a->tip;
if (vv =new_graph->vertices) gb_new_edge(u,vv,1);
else if (vv>=v && vv__