A couple of years ago I worked on an arrangement problem, a "lunch bunch."
The basic idea is that 64 people want to go out to lunch together in
eight groups of eight at a time, with the groups rearranging each month
so that everyone gets to have lunch with each of the others and no two
people have lunch together twice.
With 49 people, or other prime squares, we can arrange a square and
make the sets as follows:
The first set is the rows as-is, the second set is the columns as-is,
and the subsequent sets are generated by shifting the rows as indicated
and then reading down the columns. This gives eight total groupings,
which covers all the members with no duplication.
When I went to expand the solution to 8x8, the simple shifting idea
wouldn't work, because shifts by 2, 4, and 6 caused duplicated
positions. What I ending up doing was finding a Galois field of order 8
and using that for shifting instead.
# The multiplication and addition tables are derived from
# a Galois field order(2^3), from (0, 1, a, a^2, ... a^6)
# where a^3 = a + 1.
#
# multiply
# 0 1 a a^2 a^3 a^4 a^5 a^6
# ------------------------------------------------------
# 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# |------------------------------------------------
# 1 | 0 | 1 | a | a^2 | a^3 | a^4 | a^5 | a^6 |
# |------------------------------------------------
# a | 0 | a | a^2 | a^3 | a^4 | a^5 | a^6 | 1 |
# |------------------------------------------------
# a^2| 0 | a^2 | a^3 | a^4 | a^5 | a^6 | 1 | a |
# |------------------------------------------------
# a^3| 0 | a^3 | a^4 | a^5 | a^6 | 1 | a | a^2 |
# |------------------------------------------------
# a^4| 0 | a^4 | a^5 | a^6 | 1 | a | a^2 | a^3 |
# |------------------------------------------------
# a^5| 0 | a^5 | a^6 | 1 | a | a^2 | a^3 | a^4 |
# |------------------------------------------------
# a^6| 0 | a^6 | 1 | a | a^2 | a^3 | a^4 | a^5 |
# |------------------------------------------------
#
# add
#
# 0 1 a a^2 a^3 a^4 a^5 a^6
# ------------------------------------------------------
# 0 | 0 | 1 | a | a^2 | a^3 | a^4 | a^5 | a^6 |
# |------------------------------------------------
# 1 | 1 | 0 | a^3 | a^6 | a | a^5 | a^4 | a^2 |
# |------------------------------------------------
# a | a | a^3 | 0 | a^4 | 1 | a^2 | a^6 | a^5 |
# |------------------------------------------------
# a^2| a^2 | a^6 | a^4 | 0 | a^5 | a | a^3 | 1 |
# |------------------------------------------------
# a^3| a^3 | a | 1 | a^5 | 0 | a^6 | a^2 | a^4 |
# |------------------------------------------------
# a^4| a^4 | a^5 | a^2 | a | a^6 | 0 | 1 | a^3 |
# |------------------------------------------------
# a^5| a^5 | a^4 | a^6 | a^3 | a^2 | 1 | 0 | a |
# |------------------------------------------------
# a^6| a^6 | a^2 | a^5 | 1 | a^4 | a^3 | a | 0 |
# |------------------------------------------------
BEGIN {
@Field8::mtable = (
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 2, 3, 4, 5, 6, 7, 1],
[0, 3, 4, 5, 6, 7, 1, 2],
[0, 4, 5, 6, 7, 1, 2, 3],
[0, 5, 6, 7, 1, 2, 3, 4],
[0, 6, 7, 1, 2, 3, 4, 5],
[0, 7, 1, 2, 3, 4, 5, 6]
);
@Field8::atable = (
[0, 1, 2, 3, 4, 5, 6, 7],
[1, 0, 4, 7, 2, 6, 5, 3],
[2, 4, 0, 5, 1, 3, 7, 6],
[3, 7, 5, 0, 6, 2, 4, 1],
[4, 2, 1, 6, 0, 7, 3, 5],
[5, 6, 3, 2, 7, 0, 1, 4],
[6, 5, 7, 4, 3, 1, 0, 2],
[7, 3, 6, 1, 5, 4, 2, 0]
);
}
I would like to generalize this solution to other cases. I think it's impossible for composite orders
like 6 or 10, but all orders that are powers of primes
should work.
I see a math package on cpan called Math::Pari
and that is has functions for Galois fields, but I am not
sure how to use it to generate tables like the ones
above. Has anyone worked with Math::Pari or other
packages that might help? Thanks.