Magic: the Gathering is a 25 year old card game where each card can have a 'colour identity'. There are five such identities ([White (W), Blue (U), Black (B), Red (R), Green (G)] ignoring colourless), and when a new collection of cards are released they are often grouped into factions.

Factions often have more than one colour identity (Cards in the 'Blue Red' (UR) faction may be Blue, Red or Blue and Red).

Further, a set is always* colour balanced (meaning that the same number of identities exist across all colours, e.g. you might have one set of factions UBR,WRG,UG,WB wherein all the colours appear twice in each faction).

What are all the ways of constructing the sets of distinct factions, for $n$ factions? Is there a pattern I can use based off of small numbers of factions?

*Exceptions exist outside the scope of this question.

  • $\begingroup$ Presumably all factions in a set have different, um, identity palettes? $\endgroup$ – Joffan Jul 12 '18 at 19:53
  • $\begingroup$ @joffan I think I know what you mean? If so yes. They need to be distinct. $\endgroup$ – Pureferret Jul 12 '18 at 21:09
  • $\begingroup$ I am building an answer. Current estimates are a little under 4 million total faction groupings, not counting those that include colorless or rainbow, though any given one has up to 39 others that it is similar to via symmetric relationships. My code sucks though, mostly because of trying to take advantage of these symmetries, and I haven't been able to verify that it's fully correct yet. $\endgroup$ – Dan Uznanski Jul 13 '18 at 0:47
  • 1
    $\begingroup$ Well, it's more like -- if I have W,BG,UR, I can also have B,RW,UG. Or UBRG,WUR,WBG. or a thing with 27 different factions, just not those three. All told we get a symmetry group with 40 elements, assuming we respect the actual pairing types between colors: there are ten ways to pick color order, then we can replace every faction with its counterpart, then we can replace the list with everything that isn't in the list. $\endgroup$ – Dan Uznanski Jul 13 '18 at 7:47
  • 1
    $\begingroup$ Well okay I won't leave you hanging too much: many faction lists can be decomposed into shorter faction lists. It may be possible to come up with a tractable list of faction groups by short circuiting when we find that an existing faction list is contained within the list we're looking at $\endgroup$ – Dan Uznanski Jul 13 '18 at 9:26

There are 133 distinct canonical primitive faction groups.

A primitive faction group is one that does not contain any other faction groups; all non-primitive faction groups can be expressed as a combination of primitive faction groups.

There's still quite a lot of those - some 967 - so what we also need to do is pick a way to coalesce those that are similar into a single canonical faction group. For this, I have chosen the following: each faction is represented by a number, found by summing the values W = 1, U = 2, B = 4, R = 8, G = 16 for that faction. Then, a faction group is represented by another number, $\sum_f 2^f$ for each faction number in the group. THe canonical faction group for a particular group is the smallest faction group number among the (up to) ten similar faction groups, where things are similar if rotation and reflection of the faction group around the color wheel can make them match up.

Here is the full list of canonical faction groups. 0x00000001 - 0x00010116 W,U,B,R,G # five pures 0x00010118 R,G,WU,B # allies vs pures 0x00010124 R,G,U,WB # enemies vs pures 0x00010180 R,G,WUB # shard vs pures 0x00010240 G,WR,UB # enemies vs allies vs pure 0x00010420 G,UR,WB # enemies vs enemies vs pure 0x00010810 G,WUR,B # wedge vs pures 0x00011008 G,WU,BR # allies vs allies vs pure 0x00018000 G,WUBR # quartet vs pures 0x00024000 WG,UBR # allies vs shard 0x00042000 UG,WBR # enemies vs wedge 0x80000000 WUBRG # rainbow 0x00031442 W,UB,UR,BR,G,WG 0x00031480 WUB,UR,BR,G,WG 0x00031840 UB,WUR,BR,G,WG 0x00032440 UB,UR,WBR,G,WG 0x00051224 U,WB,WR,BR,G,UG 0x00051280 WUB,WR,BR,G,UG 0x00051820 WB,WUR,BR,G,UG 0x00054220 WB,WR,UBR,G,UG 0x00061240 UB,WR,BR,WG,UG 0x00061420 WB,UR,BR,WG,UG 0x00068110 B,R,WUBR,WG,UG 0x00069000 WG,UG,BR,WUBR 0x00092140 UB,R,WBR,G,WUG 0x00092410 B,UR,WBR,G,WUG 0x00094120 WB,R,UBR,G,WUG 0x00094210 B,WR,UBR,G,WUG 0x00096000 G,WUG,WBR,UBR 0x00128104 U,R,WUBR,WG,BG 0x00128400 WG,UR,BG,WUBR 0x00140620 WB,WR,UR,UG,BG 0x00148102 W,R,WUBR,UG,BG 0x00148200 WR,UG,BG,WUBR 0x00182400 UR,WUG,BG,WBR 0x00184200 WR,WUG,BG,UBR 0x00188100 R,WUG,BG,WUBR 0x00210940 UB,R,WUR,G,WBG 0x00211804 U,WUR,BR,G,WBG 0x00214800 G,WUR,WBG,UBR 0x00240910 B,R,WUR,UG,WBG 0x00241800 UG,WUR,BR,WBG 0x00248100 R,UG,WBG,WUBR 0x00412800 G,WUR,WBR,UBG 0x00421800 WG,WUR,BR,UBG 0x00428100 R,WG,UBG,WUBR 0x01021048 WU,UB,BR,WG,RG 0x01028014 U,B,WUBR,WG,RG 0x01028040 RG,WG,UB,WUBR 0x01082040 RG,WUG,WBR,UB 0x01084012 W,B,UBR,WUG,RG 0x01084020 RG,WUG,WB,UBR 0x01088010 RG,WUG,B,WUBR 0x01208004 RG,U,WBG,WUBR 0x01808000 RG,WUBG,WUBR 0x02014080 G,WRG,UBR,WUB 0x02048010 WRG,UG,B,WUBR 0x02408000 WRG,UBG,WUBR 0x02804000 WRG,UBR,WUBG 0x04208000 URG,WBG,WUBR 0x08108000 WURG,BG,WUBR 0x00161680 WUB,WR,UR,BR,WG,UG,BG 0x01061860 WB,UB,WUR,BR,WG,UG,RG 0x01186006 W,U,WBR,UBR,WUG,BG,RG 0x01186008 WU,WBR,UBR,WUG,BG,RG 0x01188240 UB,WR,WUBR,WUG,BG,RG 0x01188420 WB,UR,WUBR,WUG,BG,RG 0x0118a004 U,WBR,WUBR,WUG,BG,RG 0x0118c002 W,UBR,WUBR,WUG,BG,RG 0x01244812 W,B,WUR,UBR,UG,WBG,RG 0x01244820 WB,WUR,UBR,UG,WBG,RG 0x01248240 UB,WR,WUBR,UG,WBG,RG 0x01248810 B,WUR,WUBR,UG,WBG,RG 0x01249008 WU,BR,WUBR,UG,WBG,RG 0x0124c002 W,UBR,WUBR,UG,WBG,RG 0x01284810 B,WUR,UBR,WUG,WBG,RG 0x01286004 U,WBR,UBR,WUG,WBG,RG 0x01288140 UB,R,WUBR,WUG,WBG,RG 0x0128c000 UBR,WUBR,WUG,WBG,RG 0x01422814 U,B,WUR,WBR,WG,UBG,RG 0x01422840 UB,WUR,WBR,WG,UBG,RG 0x01428420 WB,UR,WUBR,WG,UBG,RG 0x01428810 B,WUR,WUBR,WG,UBG,RG 0x01429008 WU,BR,WUBR,WG,UBG,RG 0x01482810 B,WUR,WBR,WUG,UBG,RG 0x01488120 WB,R,WUBR,WUG,UBG,RG 0x0148a000 WBR,WUBR,WUG,UBG,RG 0x01602804 U,WUR,WBR,WBG,UBG,RG 0x01608108 WU,R,WUBR,WBG,UBG,RG 0x01608800 WUR,WUBR,WBG,UBG,RG 0x02144182 W,WUB,R,UBR,UG,BG,WRG 0x02144280 WUB,WR,UBR,UG,BG,WRG 0x02148180 WUB,R,WUBR,UG,BG,WRG 0x02148420 WB,UR,WUBR,UG,BG,WRG 0x02149008 WU,BR,WUBR,UG,BG,WRG 0x02184180 WUB,R,UBR,WUG,BG,WRG 0x02186004 U,WBR,UBR,WUG,BG,WRG 0x02188410 B,UR,WUBR,WUG,BG,WRG 0x0218c000 UBR,WUBR,WUG,BG,WRG 0x02244810 B,WUR,UBR,UG,WBG,WRG 0x02249004 U,BR,WUBR,UG,WBG,WRG 0x0224c000 UBR,WUBR,UG,WBG,WRG 0x02482410 B,UR,WBR,WUG,UBG,WRG 0x02486000 WBR,UBR,WUG,UBG,WRG 0x02604800 WUR,UBR,WBG,UBG,WRG 0x02849000 BR,WUBR,UG,WUBG,WRG 0x02902404 U,UR,WBR,BG,WUBG,WRG 0x02908400 UR,WUBR,BG,WUBG,WRG 0x02c02400 UR,WBR,UBG,WUBG,WRG 0x04602800 WUR,WBR,WBG,UBG,URG 0x04829000 BR,WUBR,WG,WUBG,URG 0x04908200 WR,WUBR,BG,WUBG,URG 0x06808010 B,WUBR,WUBG,WRG,URG 0x08249000 BR,WUBR,UG,WBG,WURG 0x08429000 BR,WUBR,WG,UBG,WURG 0x08608100 R,WUBR,WBG,UBG,WURG 0x12084080 WUB,UBR,WUG,WRG,BRG 0x12808004 U,WUBR,WUBG,WRG,BRG 0x18028040 UB,WUBR,WG,WURG,BRG 0x18048020 WB,WUBR,UG,WURG,BRG 0x18208004 U,WUBR,WBG,WURG,BRG 0x18808000 WURG,WUBG,BRG,WUBR 0x24808000 URG,WUBG,WBRG,WUBR 0x01686800 WUR,WBR,UBR,WUG,WBG,UBG,RG 0x06186080 WUB,WBR,UBR,WUG,BG,WRG,URG 0x06909008 WU,BR,WUBR,BG,WUBG,WRG,URG 0x09609008 WU,BR,WUBR,WBG,UBG,RG,WURG 0x12848420 WB,UR,WUBR,UG,WUBG,WRG,BRG 0x16808080 WUB,WUBR,WUBG,WRG,URG,BRG 0x18248240 UB,WR,WUBR,UG,WBG,WURG,BRG 0x18608800 WUR,WUBR,WBG,UBG,WURG,BRG 0x68808000 WUBR,WUBG,WURG,WBRG,UBRG # five quartets

Source Code

  • $\begingroup$ This is really interesting! Curious about the patterns, but I'll have to look at the source code to understand it. $\endgroup$ – Pureferret Jul 14 '18 at 19:52
  • $\begingroup$ The source code is pretty optimized, working with bit operations instead of proper sets (which I can do because I know the entire universe of elements), to make it so it can actually get anything done in a reasonable time, but it still takes ten minutes. I'm thinking about drawing the diagrams for these but it's pretty annoying. $\endgroup$ – Dan Uznanski Jul 15 '18 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.