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
ITEM 102 (Schroeppel):
As opposed to the usual formulation of a group, where you are given
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.
- there exists an I such that A * I = I * A = A, and
- for all A, B and C, (A * B) * C = A * (B * C), and
- for each A there exists an A' such that A * A' = A' * A = I, and
- 4 sometimes you are given that I and A' are unique.
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
instructions "ROT" and "ROTC".
ITEM 105 (Komolgoroff, maybe?):
Given a set of real numbers, how many sets can you get using only closure and
complement? Answer: 14.