Re: Unique Combos with Math::Combinatorics

If you start from the lines of the affine plane for GF(5), you get 30 teams of 5 players each, chosen from 25 players:

ABCDE AFKPU AGMSY AHOQX AILTW AJNRV BFOSW BGLQV BHNTU BIKRY BJMPX CFNQ
+Y CGKTX CHMRW CIOPV CJLSU DFMTV DGORU DHLPY DINSX DJKQW EFLRX EGNPW E
+HKSV EIMQU EJOTY FGHIJ KLMNO PQRST UVWXY
[download]

If you omit the last player from each team (thus always omitting Y from the teams ey is in), you get the following 30 teams.

ABCD AFKP AGMS AHOQ AILT AJNR BFOS BGLQ BHNT BIKR BJMP CFNQ CGKT CHMR 
+CIOP CJLS DFMT DGOR DHLP DINS DJKQ EFLR EGNP EHKS EIMQ EJOT FGHI KLMN
+ PQRS UVWX
[download]

This is ~~minimal~~ maximal in that you cannot add a new team to it, but if you remove the team UVWX, you can add several more. If you keep adding the (lexicographically) first team that goes with the rest, you get these 35 teams:

ABCD AFKP AGMS AHOQ AILT AJNR BFOS BGLQ BHNT BIKR BJMP CFNQ CGKT CHMR 
+CIOP CJLS DFMT DGOR DHLP DINS DJKQ EFLR EGNP EHKS EIMQ EJOT FGHI KLMN
+ PQRS 
AEUV BEWX FJUW GJVX KOUX LOVW
[download]

Update: Similarly, you also get 35 teams if you start from nothing and keep adding the (lexicographically) first team that doesn't intersect any chosen team in two or more members (Update: this is the same result as ketema's got):

ABCD AEFG AHIJ AKLM ANOP AQRS ATUV BEHK BFIL BGJM BNQT BORU BPSV CEIM 
+CFHN CGKO CJLP CQUW CRTX DEJN DFKP DGHL DIOQ DMRV DSTW ELOS EPQX FJOT
+ FMSU FVWX GINR HMOW IKSX JKQV LNUX
[download]

The J source code to generate this is (takes several seconds to run):

   players =: a.{~65+i.24
   teams =: (#~]-:"1~."1)~./:~/:~"1>,{4$<players
   good =: teams#~[:(*./"1) 1>: teams&(+/@:e."1"1 _)
   ,,&' '"1 (,{.@:good)^:35 i.0 4
[download]

Comment on Re: Unique Combos with Math::Combinatorics Select or Download Code

Replies are listed 'Best First'.
Re^2: Unique Combos with Math::Combinatorics by roboticus (Chancellor) on Mar 02, 2008 at 12:09 UTC
ambrus: Could you elaborate a little on what you're talking about? I did a google search on "affine GF(n)" but found sites wanting me to log in, abstracts of papers I most likely wouldn't understand, or articles that went whizzing above my head. And then I remembered mathworld! Here are a couple of links for people like me who might want to figure out a little bit of what ambrus is talking about: Affine Plane Finite Field (which discusses Galois field, which they abbreviate as GF(n)). ...roboticus Update: Fixed links, as suggested by ikegami and pKai	[reply]
Re^3: Unique Combos with Math::Combinatorics by ambrus (Abbot) on Mar 02, 2008 at 12:25 UTC
Yep, I'm too lazy to explain finite fields and finite geometry now. Two books come into my mind that explain finite geometry – both are suitable for beginners as they don't have much prerequisites: Hraskó András (editor), Új matematikai mozaik. TypeTEX Kiadó, Budapest, 2002. Reiman István, A geometria határterületei. Gondolat, Budapest, 1986. I won't recommend any books on finite fields for there are plenty of those and this application really only needs the basics. I also forgot to link to the homepage of the J programming language.	[reply]
Re^4: Unique Combos with Math::Combinatorics by roboticus (Chancellor) on Mar 02, 2008 at 12:37 UTC
ambrus: Oh, I didn't expect an explanation. But the field is so foreign to me, that it was kind of like: "Oh, you have this hard problem? Just use Kenlar Blurfle, and you'll see that the obvious answer is 42". A line or two of context would've been helpful. ;^D Of course, then I wouldn't have had the fun of exploring mathworld a bit. Two books come into my mind that explain finite geometry - both are suitable for beginners as they don't have much prerequisites: HraskÃ³ AndrÃ¡s (editor), Ãšj matematikai mozaik. TypeTEX KiadÃ³, Budapest, 2002. Reiman IstvÃ¡n, A geometria hatÃ¡rterÃ¼letei Great <sigh> now I'll have to add "Learn Hungarian" to my long list of ToDos, so I can read them! ;^) ...roboticus	[reply]
Re^2: Unique Combos with Math::Combinatorics (fair 5) by tye (Sage) on Mar 02, 2008 at 15:17 UTC
Trimming your original 30 teams more fairly, it is pretty easy to come up with a fair arrangement where each player gets to play on 5 teams. For example: `AGMS BIKR CFNQ DHLP EJOT UVWX AHOQ AKPU ALTW ANRV BCDE BHTU BJPX BLQV CHMW CIPV CJSU DGOR DINX DJKQ EGNW EHKS EIMU FGIJ FLRX FMTV FOSW GKTX LMNO PQRS` [download] I strongly doubt that such can be broken into "rounds", however. - tye	[reply] [d/l]
Re^3: Unique Combos with Math::Combinatorics (fair 5) by ambrus (Abbot) on Mar 02, 2008 at 16:23 UTC
The 30 lines of the affine plane certainly can be broken to 6 rounds or parallel lines. ( `ABCDE FGHIJ KLMNO PQRST UVWXY AFKPU AGMSY AHOQX AILTW AJNRV BFOSW BGLQV BHNTU BIKRY BJMPX CFNQY CGKTX CHMRW CIOPV CJLSU DFMTV DGORU DHLPY DINSX DJKQW EFLRX EGNPW EHKSV EIMQU EJOTY` [download] ) Update: yeah, the example is wrong, but the statement is still true. Uh. `ABCDE FGHIJ KLMNO PQRST UVWXY AFKPU BGLQV CHMRW DINSX EJOTY AGMSY BHNTU CIOPV DJKQW EFLRX AHOQX BIKRY CJLSU DFMTV EGNPW AILTW BJMPX CFNQY DGORU EHKSV AJNRV BFOSW CGKTX DHLPY EIMQU` [download]	[reply] [d/l] [select]
Re^4: Unique Combos with Math::Combinatorics (fair 5) by tye (Sage) on Mar 03, 2008 at 17:20 UTC
If you use one line to "factor out" extra members from teams from other lines, then you can get 5 fair rounds: `_BCDE FGHI_ KLM_O PQ_ST UVWX. > AJNR. A_KPU _GLQV CHMR_ DIN_X EJOT. > FBWS. AGMS. BHN_U _IOPV DJ_QW EFLR_ > .TCKX AHO_X BIKR. CJLS_ DF_TV _GNPW > Q.UME AI_TW BJM_X CFNQ. _GORU E_KSV > LP.DH ajnrV bfOsw cGktx dhlp. eImqu BCDE FGHI KLMO PQST UVWX AJNR AKPU GLQV CHMR DINX EJOT FBWS AGMS BHNU IOPV DJQW EFLR TCKX AHOX BIKR CJLS DFTV GNPW QUME AITW BJMX CFNQ GORU EKSV LPDH` [download] - tye	[reply] [d/l]