1 /****************************************************************************
2 **
3 *A get_definition_sets.c ANUPQ source Eamonn O'Brien
4 **
5 *Y Copyright 1995-2001, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
6 *Y Copyright 1995-2001, School of Mathematical Sciences, ANU, Australia
7 **
8 */
9
10 #include "pq_defs.h"
11 #include "pga_vars.h"
12 #include "pq_functions.h"
13
14 int *subset; /* temporary storage for definition set */
15
16 /* a definition set is a subset of cardinality pga->s
17 of the relative nucleus, a set of cardinality pga->r;
18 here, we find all subsets of cardinality pga->s which
19 contain the elements 0 .. pga->fixed - 1;
20 set up all of the definition sets as a array, list */
21
get_definition_sets(struct pga_vars * pga)22 void get_definition_sets(struct pga_vars *pga)
23 {
24 register int i;
25 register int bound;
26
27 pga->nmr_def_sets = 0;
28 subset = allocate_vector(pga->s, 0, 0);
29
30 /* initialise each definition set to contain 0 .. pga->fixed - 1 */
31 for (i = 0; i < pga->fixed; ++i)
32 subset[i] = i;
33
34 if (pga->fixed == pga->s)
35 add_to_list(subset, pga);
36 else {
37 bound = MIN(pga->r - (pga->s - pga->fixed), pga->r);
38 for (i = pga->fixed; i <= bound; ++i)
39 visit(i, pga->s - pga->fixed - 1, pga);
40 }
41
42 free_vector(subset, 0);
43 }
44
45 /* store the definition set as a bit string; compute the number
46 of available positions determined by this definition set */
47
add_to_list(int * subset,struct pga_vars * pga)48 void add_to_list(int *subset, struct pga_vars *pga)
49 {
50 register int i;
51 int bit_string = 0; /* to store subset */
52
53 /* convert each subset to bit string */
54 for (i = 0; i < pga->s; ++i)
55 bit_string |= 1 << subset[i];
56
57 pga->list[pga->nmr_def_sets] = bit_string;
58
59 /* compute the number of available positions */
60 pga->available[pga->nmr_def_sets] = available_positions(subset, pga);
61
62 ++pga->nmr_def_sets;
63 }
64
65 /* visit node k; d remaining elements to be found to make up
66 subset of cardinality pga->s */
67
visit(int k,int d,struct pga_vars * pga)68 void visit(int k, int d, struct pga_vars *pga)
69 {
70 register int i;
71
72 subset[pga->s - d - 1] = k;
73
74 if (d == 0)
75 add_to_list(subset, pga);
76
77 for (i = k + 1; i < pga->r && d > 0; ++i)
78 visit(i, d - 1, pga);
79 }
80
81 /* find the number of available positions for definition set K */
82
available_positions(int * K,struct pga_vars * pga)83 int available_positions(int *K, struct pga_vars *pga)
84 {
85 register int l;
86 register int available = pga->q * pga->s - pga->s * (pga->s - 1) / 2;
87
88 for (l = 0; l < pga->s; ++l)
89 available -= (K[l] + 1);
90 return available;
91 }
92