gb_basic.w

来自「模拟器提供了一个简单易用的平台」· W 代码 · 共 1,575 行 · 第 1/5 页

for (k=d-1;;k--) {
  if (xx[k]<sig[k] && xx[k]<nn[k]) break;
  if (k==0) goto last;
}
xx[k]++;

@ As in the |board| routine, we represent the sequence of coordinates
$(2,0,1)$ by the string `\.{2.0.1}'.
The string won't exceed |BUF_SIZE|, because the ratio |BUF_SIZE/MAX_D| is
plenty big.

The first three coordinate values, $(x_0,x_1,x_2)$, are placed into
utility fields |x|, |y|, and |z|, so that they can be accessed immediately
if an application needs them.

@<Assign a symbolic name for $(x_0,\ldots,x_d)$ to vertex~|v|@>=
{@+register char *p=buffer; /* string pointer */
  for (k=0;k<=d;k++) {
    sprintf(p,".%ld",xx[k]);
    while (*p) p++;
  }
  v->name=gb_save_string(&buffer[1]); /* omit |buffer[0]|, which is |'.'| */
  v->x.I=xx[0];@+v->y.I=xx[1];@+v->z.I=xx[2];
}

@ Since we are generating the vertices in lexicographic order of their
coordinates, it is easy to identify all adjacent vertices that
precede the current setting of $(x_0,x_1,\ldots,x_d)$. We locate them
via their symbolic names.

@<Create arcs or edges from previous points to~|v|@>=
for (j=0;j<d;j++)
  if (xx[j]) {@+register Vertex *u; /* previous vertex adjacent to |v| */
    xx[j]--;
    for (k=j+1;k<=d;k++)
      if (xx[k]<nn[k]) {@+register char *p=buffer; /* string pointer */
        xx[k]++;
        for (i=0;i<=d;i++) {
          sprintf(p,".%ld",xx[i]);
          while (*p) p++;
        }
        u=hash_out(&buffer[1]);
        if (u==NULL) panic(impossible+2); /* can't happen */
        if (directed) gb_new_arc(u,v,1L);
        else gb_new_edge(u,v,1L);
        xx[k]--;
      }
    xx[j]++;
  }

@* Subset graphs. The subroutine call {\advance\thinmuskip 0mu plus 2mu
|subsets(n,n0,n1,n2,n3,n4,size_bits,directed)|}
creates a graph having the same vertices as
|simplex(n,n0,n1,n2,n3,n4,directed)| but with a quite different notion
of adjacency. In this we interpret a solution $(x_0,x_1,\ldots,x_d)$ to
the conditions $x_0+x_1+\cdots+x_d=n$ and $0\le x_j\le n_j$ not as a
position on a game board but as an $n$-element submultiset of the multiset
$\{n_0\cdot0,n_1\cdot 1,\ldots,n_d\cdot d\}$ that has $x_j$ elements
equal to~$j$. (If each $n_j=1$, the multiset is a set; this is an
important special case.) Two vertices are adjacent if and only if
their intersection has a cardinality that matches one of the bits in
|size_bits|, which is an unsigned integer. Each arc has length~1.

For example, suppose $n=3$ and |(n0,n1,n2,n3)=(2,2,2,0)|. Then the vertices
are the 3-element submultisets of $\{0,0,1,1,2,2\}$, namely
$$\{0,0,1\},\quad \{0,0,2\},\quad \{0,1,2\},\quad
\{0,2,2\},\quad \{1,1,2\},\quad \{1,2,2\},$$
which are represented by the respective vectors
$$(2,1,0),\quad (2,0,1),\quad (1,1,1),\quad
(1,0,2),\quad (0,2,1),\quad (0,1,2).$$
The intersection of multisets represented by $(x_0,x_1,\ldots,x_d)$ and
$(y_0,y_1,\ldots,y_d)$ is $$\bigl(\min(x_0,y_0),\min(x_1,y_1),\ldots,
\min(x_d,y_d)\bigr);$$ each element occurs as often as it occurs
in both multisets being intersected. If now |size_bits=3|, the
multisets will be considered adjacent whenever their
intersection contains exactly 0 or~1 elements, because $3=2^0+2^1$.
The vertices adjacent to $\{0,0,1\}$, for example, will be
$\{0,2,2\}$ and $\{1,2,2\}$. In this case, every pair of submultisets
has a nonempty intersection, so the same graph would be obtained
if |size_bits=2|.

If |directed| is nonzero, the graph will have directed arcs, from |u|
to~|v| only if $u\le v$. Notice that the graph will have self-loops if
and only if the binary representation of |size_bits| contains the term
$2^n$, in which case there will be a loop from every vertex to itself.
(In an undirected graph, such loops are represented by two arcs.)

We define a macro |disjoint_subsets(n,k)| for the case
of $n\choose k$ vertices, adjacent if and only if they represent
disjoint $k$-subsets of an $n$-set.
One important special case is the Petersen graph, whose vertices
@^Petersen, Julius Peter Christian, graph@>
are the 2-element subsets of $\{0,1,2,3,4\}$, adjacent when they
are disjoint. This graph is remarkable because it contains 10 vertices,
each of degree~3, but it has no circuits of length less than~5.

@(gb_basic.h@>=
#define disjoint_subsets(n,k) @[subsets((long)(k),1L,(long)(1-(n)),0L,0L,0L,1L,0L)@]
#define petersen() @[disjoint_subsets(5,2)@]

@ @<Basic subroutines@>=
Graph *subsets(n,n0,n1,n2,n3,n4,size_bits,directed)
  unsigned long n; /* the number of elements in the multiset */
  long n0,n1,n2,n3,n4; /* multiplicities of elements */
  unsigned long size_bits; /* intersection sizes that trigger arcs */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@#
  @<Normalize the simplex parameters@>;
  @<Create a graph with one vertex for each subset@>;
  @<Name the subsets and create the arcs or edges@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* rats, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Create a graph with one vertex for each subset@>=
@<Determine the number of feasible $(x_0,\ldots,x_d)$,
  and allocate the graph@>;
sprintf(new_graph->id,"subsets(%lu,%ld,%ld,%ld,%ld,%ld,0x%lx,%d)",
    n,n0,n1,n2,n3,n4,size_bits,directed?1:0);
strcpy(new_graph->util_types,"ZZZIIIZZZZZZZZ");
 /* hash table will not be used */

@ We generate the vertices with exactly the logic used in |simplex|.

@<Name the subsets and create the arcs or edges@>=
v=new_graph->vertices;
yy[d+1]=0;@+sig[0]=n;
for (k=d;k>=0;k--) yy[k]=yy[k+1]+nn[k];
if (yy[0]>=n) {
  k=0;@+xx[0]=(yy[1]>=n? 0: n-yy[1]);
  while (1) {
    @<Complete the partial solution $(x_0,\ldots,x_k)$@>;
    @<Assign a symbolic name for $(x_0,\ldots,x_d)$ to vertex~|v|@>;
    @<Create arcs or edges from previous subsets to~|v|@>;
    v++;
    @<Advance to the next partial solution $(x_0,\ldots,x_k)$, where |k| is
       as large as possible; |goto last| if there are no more solutions@>;
  }
}
last:@+if (v!=new_graph->vertices+new_graph->n)
  panic(impossible); /* can't happen */

@ The only difference is that we generate the arcs or edges by brute
force, examining each pair of vertices to see if they are adjacent or not.

The code here is character-set dependent: It assumes that `\..' and null
have a character code less than `\.0', as in ASCII. It also assumes
that characters occupy exactly eight bits.
@^system dependencies@>

@d UL_BITS 8*sizeof(unsigned long) /* the number of bits in |size_bits| */

@<Create arcs or edges from previous subsets to~|v|@>=
{@+register Vertex *u;
  for (u=new_graph->vertices;u<=v;u++) {@+register char *p=u->name;
    long ss=0; /* the number of elements common to |u| and |v| */
    for (j=0;j<=d;j++,p++) {
      for (s=(*p++)-'0';*p>='0';p++) s=10*s+*p-'0'; /* |sscanf(p,"%ld",&s)| */
@^character-set dependencies@>
      if (xx[j]<s) ss+=xx[j];
      else ss+=s;
    }
    if (ss<UL_BITS && (size_bits&(((unsigned long)1)<<ss))) {
      if (directed) gb_new_arc(u,v,1L);
      else gb_new_edge(u,v,1L);
    }
  }
}

@* Permutation graphs. The subroutine call
|perms(n0,n1,n2,n3,n4,max_inv,directed)|
creates a graph whose vertices represent the permutations of a
multiset that have at most |max_inv| inversions. Two permutations are adjacent
in the graph if one is obtained from the other by interchanging two
adjacent elements. Each arc has length~1.

For example, the multiset $\{0,0,1,2\}$ has the following twelve permutations:
$$\vcenter{\halign{#&&\quad#\cr
0012,&0021,&0102,&0120,&0201,&0210,\cr
1002,&1020,&1200,&2001,&2010,&2100.\cr}}$$
The first of these, 0012, has two neighbors, 0021 and 0102.

The number of inversions is the number of pairs of elements $xy$ such
that $x>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\}$. It is not difficult to verify that the number
of inversions of a permutation is 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\}$, for example, would
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.
Larger values of $d$ can be specified by using |-d| as a parameter:
If |n0=-d|, each multiplicity $n_k$ is taken to be~1; if |n0>0| and |n1=-d|,
each multiplicity $n_k$ is taken to be equal to~|n0|;
if |n0>0|, |n1>0|, and |n2=-d|, the multiplicities are alternately
$(|n0|,|n1|,|n0|,|n1|,|n0|,\ldots\,)$; if  |n0>0|, |n1>0|, |n2>0|, and
|n3=-d|, the multiplicities are the first~|d+1| elements of the
periodic sequence $(|n0|,|n1|,|n2|,|n0|,|n1|,\ldots\,)$; and if all
but |n4| are positive, while |n4=-d|, 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((long)(1-(n)),0L,0L,0L,0L,0L,\
   (long)(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<k\le d}n_jn_k$.

\vskip1pt
Notice that in the case $d=1$, we essentially obtain all combinations of
|n0+n1| elements taken |n1| at a time. The positions of the 1's correspond
to the elements of a subset or sample.

If |directed| is nonzero, the graph will contain only directed arcs
from permutations to neighboring permutations that have exactly one more
inversion. In this case the graph corresponds to a partial ordering that is a
lattice with interesting properties; see the article by Bennett and Birkhoff
@^Bennett, Mary Katherine@>
@^Birkhoff, Garrett@>
in {\sl Algebra Universalis\/} (1994), to appear.

@ The program for |perms| is very similar in structure to the program
for |simplex| already considered.

@<Basic subroutines@>=
Graph *perms(n0,n1,n2,n3,n4,max_inv,directed)
  long n0,n1,n2,n3,n4; /* composition of the multiset */
  unsigned long max_inv; /* maximum number of inversions */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@+@q{@>@t}\6{@>@q}@>
  register long n; /* total number of elements in multiset */
  @<Normalize the permutation parameters@>;
  @<Create a graph with one vertex for each permutation@>;
  @<Name the permutations and create the arcs or edges@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* shucks, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Normalize the permutation parameters@>=
if (n0==0) {@+n0=1;@+n1=0;@+} /* convert the empty set into $\{0\}$ */
else if (n0<0) {@+n1=n0;@+n0=1;@+}
n=BUF_SIZE; /* this allows us to borrow code from |simplex|, already written */
@<Normalize the simplex parameters@>;
@<Determine |n| and the maximum possible number of inversions@>;

@ Here we want to set |max_inv| to the maximum possible number of
inversions, if the given value of |max_inv| is zero or
if it exceeds that maximum number.

@<Determine |n| and the maximum possible number of inversions@>=
{@+register long ss; /* max inversions known to be possible */
  for (k=0,s=ss=0;k<=d;ss+=s*nn[k],s+=nn[k],k++)
    if (nn[k]>=BUF_SIZE) panic(bad_specs);
      /* too many elements in the multiset */
  if (s>=BUF_SIZE) panic(bad_specs+1); /* too many elements in the multiset */
  n=s;
  if (max_inv==0 || max_inv>ss) max_inv=ss;  
}

@ To determine the number of vertices, we sum the first |max_inv+1|
coefficients of a power series in which the coefficient of~$z^j$
is the number of permutations having $j$ inversions. It is known
[{\sl Sorting and Searching}, exercise 5.1.2--16] that this power series
is the ``$z$-multinomial coefficient''
$${n\choose n_0,\ldots,n_d}_{\!z}={n!_z\over n_0!_z\ldots n_d!_z}\,,
\qquad\hbox{where}\qquad m!_z=\prod_{k=1}^m{1-z^k\over 1-z}\,.$$

@<Create a graph with one vertex for each permutation@>=
{@+long nverts; /* the number of vertices */
  register long *coef=gb_typed_alloc(max_inv+1,long,working_storage);
  if (gb_trouble_code) panic(no_room+1); /* can't allocate |coef| array */
  coef[0]=1;
  for (j=1,s=nn[0];j<=d;s+=nn[j],j++)
    @<Multiply the power series coefficients by
       $\prod_{1\le k\le n_j}(1-z^{s+k})/(1-z^k)$@>;
  for (k=1,nverts=1;k<=max_inv;k++) {
    nverts+=coef[k];
    if (nverts>1000000000) panic(very_bad_specs); /* way too big */
  }
  gb_free(working_storage); /* recycle the |coef| array */
  new_graph=gb_new_graph(nverts);
  if (new_graph==NULL)