tall_man has asked for the wisdom of the Perl Monks concerning the following question:
With 49 people, or other prime squares, we can arrange a square and make the sets as follows:
1 2 3 4 5 6 7 < shift by 0 8 9 10 11 12 13 14 < shift by 1 15 16 17 18 19 20 21 < shift by 2 22 23 24 25 26 27 28 < shift by 3 29 30 31 32 33 34 35 < shift by 4 36 37 38 39 40 41 42 < shift by 5 43 44 45 46 47 48 49 < shift by 6
The first set is the rows asis, the second set is the columns asis, 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.


Replies are listed 'Best First'.  

Re: Lunch Bunch arrangement problem
by abell (Chaplain) on May 17, 2003 at 10:25 UTC  
by tall_man (Parson) on May 17, 2003 at 19:03 UTC  
Re: Lunch Bunch arrangement problem
by shemp (Deacon) on May 16, 2003 at 18:48 UTC  
by tall_man (Parson) on May 16, 2003 at 19:39 UTC  
by shemp (Deacon) on May 16, 2003 at 20:13 UTC  
by tall_man (Parson) on May 16, 2003 at 20:29 UTC  
Re: Lunch Bunch arrangement problem
by shemp (Deacon) on May 21, 2003 at 15:53 UTC  
by tall_man (Parson) on May 21, 2003 at 19:09 UTC  
by shemp (Deacon) on May 21, 2003 at 19:56 UTC 