Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

## GROUP THEORY

Previous Up Next

### ITEM 102 (Schroeppel):

As opposed to the usual formulation of a group, where you are given
1. there exists an I such that A * I = I * A = A, and
2. for all A, B and C, (A * B) * C = A * (B * C), and
3. for each A there exists an A' such that A * A' = A' * A = I, and
4. 4 sometimes you are given that I and A' are unique.
If instead you are given A * I = A and A * A' = I, then the above rules can be derived. But if you are given A * I = A and A' * A = I, then something very much like a group, but not necessarily a group, results. For example, every element is duplicated.

### ITEM 103 (Gosper):

The Hamiltonian paths through the N! permutations of N objects using only SWAP (swap any specific pair) and ROTATE (1 position) are as follows:
```N       PATHS + DISTINCT REVERSES
2       2 + 0, namely, S, R
3       2 + 1, namely, SRRSR, RRSRR
4       3 + 3, namely:
SRR RSR SRR RSR RRS RSR RSR RR
RSR SRR RSR RRS RSR RRS RSR RR
SRR RSR RRS RRS RSR RRS RRR SR
```
PROBLEM: A questionable program said there are none for N = 5; is this so?

### ITEM 104 (Schroeppel):

Any permutation on 72 bits can be coded with a routine containing only the PDP-6/10 instructions "ROT" and "ROTC".

## SET THEORY

### ITEM 105 (Komolgoroff, maybe?):

Given a set of real numbers, how many sets can you get using only closure and complement? Answer: 14.