We wish to make a list of all distinct subgroups and also maintain a list of the corresponding generators. Thus the ordered list will be indices into a table of subgroups and generators. SUBGTABLE is a record structure that holds subgroups and generators for them. The comparison function SGCOMP was chosen so that subgroups get listed in increasing size. After generating all subgroups, one can access them as an array SUBGROUP with indices 0..#SUBGROUPS-1.
Ordered Lists Package
We make use of a package for handing ordered lists that was written in 1989. Rather than exhibit the code for this package, we describe the words used here.
Note: The implementation of ORDLIST used here uses single bytes for indices and therefore can contain at most 256 indices.
ORDLIST |
<number> ORDLIST <name><comparison> | This is a defining word. <number>
is the maximum number of elements in the list. <comparison> is the
name of a comparison function with the stack diagram ( i j -- -1 | 0 | 1 ) |
>LST |
( list -- ) | Install list as the current list |
ISIN? |
( n list - i t/f ) | Check if the element of index n is in the list. If it is, i is the position, and the flag is TRUE. If it is not on the list, then i is the place where it should be inserted. |
(INS) |
( n i --) | Insert n at position i |
LST@ |
( i - n ) | n is the entry at position i in the current list. |
OL-EMPTY |
( list -- ) | Empty the given list. |
An ORDLIST is paired with an array-like structure that holds the actual data. The ordered list is a list of indices of data. When we create an ordered list, we supply a comparison function.
Suppose i and j are two indices and L[i], L[j] the corresponding data. The comparison function has stack diagram
( i j -- -1 | 0 | 1 ).
-1 if L[i] < L[j], 0 if L[i] = L[j], and 1 if L[i] > L[j].
One of the uses of ordered lists in this system is to keep a list without duplicates.
In the following code, we establish an array SUBGTABLE that holds subgroups and generators. The comparison function SGCOMP compares subgroups. S1 < S2 if S1 has fewer elements than S2 or, if they have the same number of elements, S1 comes before S2 as unsigned integers. SUBGLIST is the name for the ordered list. When this name is used, an address is put on the stack. >LST uses this address to make SUBGLIST the current ordered list and all the ordered list words refer to it.
CREATE SUBTABLE 100 2* CELLS ALLOT (Note 9) : 'SUBG ( index -- addr_of_subg ) 2 CELLS * SUBTABLE + ; : 'GEN ( index -- addr_of_gen ) 'SUBG CELL + ; : SGCOMP ( idx1 idx2 -- -1|0|1 ) 'SUBG @ SWAP 'SUBG @ SWAP OVER #SET OVER #SET - ?DUP 0= IF 2DUP U< IF 2DROP 1 ELSE U> THEN ELSE >R 2DROP R> 0> IF -1 ELSE 1 THEN THEN ;100 ORDLIST SUBGLIST SGCOMPVARIABLE SGPTR : >SGTABLE ( genset -- ) \ put at end DUP 1 SGPTR +! SGPTR @ 'GEN ! GENERATES SGPTR @ 'SUBG ! ;
: NEWSUB ( ele subgidx -- ) |
NEWSUB takes an element and the index of a subgroup in SUBTABLE. It will produce a new subgroup if the element is not in the existing one. |
2DUP 'SUBG @ MEMBER? |
|
IF 2DROP |
if ele is in the subgroup, then drop both |
ELSE 'GEN @ MEMBER! |
Else add the element to generating set. This returns a new generating set with the element added. |
>SGTABLE |
>SGTABLE takes a generating set and puts it and the subgroup it generates at the end of SUBTABLE. |
SGPTR @ SUBGLIST ISIN? |
We now check the ordered list SUBGLIST to see if this subgroup has previously appeared. |
IF DROP -1 SGPTR +! |
If it is already there, we DROP the position (produced by ISIN?) and decrease the SGPTR - in effect, removing the subgroup from the end of the table. |
ELSE SGPTR @ SWAP |
If it is new, we insert the index in the proper place in the ordered list SUBGLIST. |
THEN ; |
GENERATE-SUBGROUPS repeatedly tries to add generators to existing subgroups. Notice that the inner loop is over all elements, while the outer loop is over only the indices of SUBTABLE corresponding to subgroups added in the previous pass. (Any subgroups prior to that already have been processed.)
: GENERATE-SUBGROUPS ( grp# -- ) >GROUP SUBGLIST OL-EMPTY SUBGLIST >LST 0 SGPTR ! 1 0 'SUBG ! 0 0 'GEN ! 0 0 (INS) -1 BEGIN ( old_top ) \ previous top of SUBTABLE 1+ SGPTR @ DUP >R \ save current SGPTR value 1+ SWAP \ use only recently added subgroups DO \ loop over subgroups FOR-ALL-ELEMENTS DO \ loop over elements I J LST@ NEWSUB LOOP LOOP R> SGPTR @ OVER = \ compare old SGPTR with current UNTIL ( exit when no more subgroups have been added ) DROP ;
Once the subgroups have been generated, we display them in increasing order, first ordered by size then by lexicographic order of elements.
: SHOW-SUBGROUPS SUBGLIST >LST CR ." * = Normal subgroup" CR ." Generators" 25 TAB ." Subgroup" SGPTR @ 1+ 0 DO CR I 3 .R 2 SPACES I LST@ DUP 'GEN @ SET. 25 TAB 'SUBG @ DUP NORMAL? IF 42 ELSE BL THEN EMIT SG. LOOP CR ;
After GENERATE-SUBGROUPS, the subgroups are in an array. <k> 'SUBG gives the address of the subgroup in position k, 0 < k < N (where N is the number of subgroups). The index of the k-th subgroup in the ordered list is <k> LST@ .
: #SUBGROUPS SGPTR @ 1+ ;: SUBGROUP ( indx -- subg or empty ) SUBGLIST >LST DUP 0 #SUBGROUPS WITHIN IF LST@ 'SUBG @ ELSE DROP 0 THEN ;: SUBGROUPS ( grp# -- ) GENERATE-SUBGROUPS SHOW-SUBGROUPS ;
Example:
8 SUBGROUPS
* = Normal subgroup
Generators Subgroup
0 { } *{ A }
1 { D } { A D }
2 { E } { A E }
3 { F } { A F }
4 { B } *{ A B C }
5 { B D } *{ A B C D E F }