Problem with permutations
October 4, 2010 4:32 PM Subscribe
MathFilter: Problem with permutations
I'm trying to organize an exquisite corpse project for 13 artists. So one person passes an image to the next, who passes one to the next, through the entire group. It's essential that everyone has a chance to go first, and I'd like to have everyone have the opportunity to follow every one of the other artists once. However, I can't figure out how to organize it this way.
For an example with four people, I'd want this:
1. A B C D
2. B D A C
3. C A D B
4. D C B A
So A, B, C, and D all get to go first once, and each follows all of the others once (so B gets to follow A, C, and D).
I've noticed there's no solution for 3 people and I can't find one for 5, so I wonder if there are no solutions for odd numbered groups?
If there's no perfect solution for 13, I'd like to distribute the error as much as possible. So, it's better that each person misses following one other person (so A never gets to follow B) rather than having one person always following the same person (don't want C to follow D every single time). But one thing that can't change is that everyone needs to have the opportunity to go first once. Also, if at all possible, it would be great to have each person have the chance to go last once as well (but this is less important)
So, how do I find a solution for 13? Hopefully there's a simple way of doing this I haven't thought of!
Thanks.
I'm trying to organize an exquisite corpse project for 13 artists. So one person passes an image to the next, who passes one to the next, through the entire group. It's essential that everyone has a chance to go first, and I'd like to have everyone have the opportunity to follow every one of the other artists once. However, I can't figure out how to organize it this way.
For an example with four people, I'd want this:
1. A B C D
2. B D A C
3. C A D B
4. D C B A
So A, B, C, and D all get to go first once, and each follows all of the others once (so B gets to follow A, C, and D).
I've noticed there's no solution for 3 people and I can't find one for 5, so I wonder if there are no solutions for odd numbered groups?
If there's no perfect solution for 13, I'd like to distribute the error as much as possible. So, it's better that each person misses following one other person (so A never gets to follow B) rather than having one person always following the same person (don't want C to follow D every single time). But one thing that can't change is that everyone needs to have the opportunity to go first once. Also, if at all possible, it would be great to have each person have the chance to go last once as well (but this is less important)
So, how do I find a solution for 13? Hopefully there's a simple way of doing this I haven't thought of!
Thanks.
I don't have a solution in general, but want to point out that N=1 does have a solution.
posted by autopilot at 5:08 PM on October 4, 2010
posted by autopilot at 5:08 PM on October 4, 2010
I can't help at the moment since I'm just leaving the office, but this shouldn't be hard in principle to solve using your favorite programming language. A quick google search found this java program which will do all the possible permutations for you.
Adding a couple if statements to filter out the permutations that don't meet your criteria should get you to the end.
Sorry if you can't code yourself -- if this isn't solved in a few hours when I get home I'll take a stab at it myself.
posted by auto-correct at 5:25 PM on October 4, 2010
Adding a couple if statements to filter out the permutations that don't meet your criteria should get you to the end.
Sorry if you can't code yourself -- if this isn't solved in a few hours when I get home I'll take a stab at it myself.
posted by auto-correct at 5:25 PM on October 4, 2010
Somewhat similar to what tickingclock said above - start with the regular 13 in alphabetical order, then go ever other, then every third, then every fourth, then every fifth, etc. Everyone will end up going first except the last person (13 people, 12 permutations) and they will always follow someone different. This works (see below) except for M who never gets to go first. Don't know if that's acceptable.
1. ABCDEFGHIJKLM
2. BDFHJLACEGIKM
3. CFILBEHKADGJM
4. DHLCGKBFJAEIM
5. EJBGLDIAFKCHM
6. FLEKDJCIBHAGM
7. GAHBICJDKELFM
8. HCKFAIDLGBJEM
9. IEAJFBKGCLHDM
10. JGDAKHEBLIFCM
11. KIGECALJHFDBM
12. LKJIHGFEDCBAM
posted by garnetgirl at 5:52 PM on October 4, 2010
1. ABCDEFGHIJKLM
2. BDFHJLACEGIKM
3. CFILBEHKADGJM
4. DHLCGKBFJAEIM
5. EJBGLDIAFKCHM
6. FLEKDJCIBHAGM
7. GAHBICJDKELFM
8. HCKFAIDLGBJEM
9. IEAJFBKGCLHDM
10. JGDAKHEBLIFCM
11. KIGECALJHFDBM
12. LKJIHGFEDCBAM
posted by garnetgirl at 5:52 PM on October 4, 2010
I just wanted to say that, in general, it may not be a good idea to generate the full set of all possible permutations due to combinatorial explosion. For example, permuting a set of 13 = 13! = 6 227 020 800 different solutions.
posted by tickingclock at 5:58 PM on October 4, 2010
posted by tickingclock at 5:58 PM on October 4, 2010
garnetgirl has it. The 13th list should be the original list in reverse.
posted by svenx at 6:24 PM on October 4, 2010
posted by svenx at 6:24 PM on October 4, 2010
Response by poster: Maybe garnetgirl's solution would work if I just distribute those M's from the end through the rest of the group, and then, like what svenx said, add the first one backwards, like this:
1. ABCDEFGHIJKLM
2. BDMFHJLACEGIK
3. CFIMLBEHKADGJ
4. DHLMCGKBFJAEI
5. EJBGLDMIAFKCH
6. FLEKDJCIMBHAG
7. GAHBICJDMKELF
8. HCKMFAIDLGBJE
9. IEAJFBKGMCLHD
10. JMGDAKHEBLIFC
11. KIGMECALJHFDB
12. LKJIHGFEDCBAM
13. MLKJIHGFEDCBA
Even if there are a few repeated combinations now, it looks really, really close.
posted by rottytooth at 6:55 PM on October 4, 2010
1. ABCDEFGHIJKLM
2. BDMFHJLACEGIK
3. CFIMLBEHKADGJ
4. DHLMCGKBFJAEI
5. EJBGLDMIAFKCH
6. FLEKDJCIMBHAG
7. GAHBICJDMKELF
8. HCKMFAIDLGBJE
9. IEAJFBKGMCLHD
10. JMGDAKHEBLIFC
11. KIGMECALJHFDB
12. LKJIHGFEDCBAM
13. MLKJIHGFEDCBA
Even if there are a few repeated combinations now, it looks really, really close.
posted by rottytooth at 6:55 PM on October 4, 2010
Response by poster: Whoops, 13 is really close to 12, though... hmm....
posted by rottytooth at 7:39 PM on October 4, 2010
posted by rottytooth at 7:39 PM on October 4, 2010
This is reminiscent of multiplicative groups. You should be able to apply a similar pattern...
posted by Earl the Polliwog at 7:48 PM on October 4, 2010
posted by Earl the Polliwog at 7:48 PM on October 4, 2010
Yeah, I think Earl the Polliwog has it. The image he posted is the multiplication table for the group of units in "Z/7", which is just the integers (with normal addition and multiplication) modulo 7.
IIRC, in such a table (for the multiplicative group of units in Z/n) you'll have (i) everybody leading exactly once and (ii) any given person following each other person exactly once--if and only if n is prime. Note that n is one greater than the number of artists you have; in the Z/7 example we have people numbered 1 through 6, and in general this would be 1 through n-1.
So 4 and 6 work because 5 and 7 are prime, but 13 won't work, because 14 isn't prime. The subproblem of "distributing the error" is interesting though.
posted by AkzidenzGrotesk at 8:24 PM on October 4, 2010 [1 favorite]
IIRC, in such a table (for the multiplicative group of units in Z/n) you'll have (i) everybody leading exactly once and (ii) any given person following each other person exactly once--if and only if n is prime. Note that n is one greater than the number of artists you have; in the Z/7 example we have people numbered 1 through 6, and in general this would be 1 through n-1.
So 4 and 6 work because 5 and 7 are prime, but 13 won't work, because 14 isn't prime. The subproblem of "distributing the error" is interesting though.
posted by AkzidenzGrotesk at 8:24 PM on October 4, 2010 [1 favorite]
13 lines.. 12 transitions per line so 156 transitions are needed. There are 13*12 possible orderings of pairs, the same number. So this seems like it should be doable. The first item of each list is obvious.
I would define the lines as having a "skip", which lays out the order. A skip of one is:
ABCDEFGHIJKLM
Skip of two:
ACEGIKMBDFHJL
Etc. 13 is prime so this works out without any crazy skipping of used letters. Each line starts with the -N position so M isn't always last.
1. ABCDEFGHIJKLM
2. MBDFHJLACEGIK
3. LBEHKADGJMCFI
4. KBFJAEIMDHLCG
5. CTHULHUFHTAGN
etc. This is easier to visualize if you write out the letters in a circle.
I'd enjoy going into this more to see if I have it right but I'm feeling kinda jumpy right now.
posted by chairface at 9:34 PM on October 4, 2010
I would define the lines as having a "skip", which lays out the order. A skip of one is:
ABCDEFGHIJKLM
Skip of two:
ACEGIKMBDFHJL
Etc. 13 is prime so this works out without any crazy skipping of used letters. Each line starts with the -N position so M isn't always last.
1. ABCDEFGHIJKLM
2. MBDFHJLACEGIK
3. LBEHKADGJMCFI
4. KBFJAEIMDHLCG
5. CTHULHUFHTAGN
etc. This is easier to visualize if you write out the letters in a circle.
I'd enjoy going into this more to see if I have it right but I'm feeling kinda jumpy right now.
posted by chairface at 9:34 PM on October 4, 2010
FWIW, I've verified there is no (perfect) solution for 5 people.
posted by DevilsAdvocate at 9:42 PM on October 4, 2010
posted by DevilsAdvocate at 9:42 PM on October 4, 2010
Best answer: Duh. 13 is zero, modulo 13. It's close though:
posted by chairface at 9:45 PM on October 4, 2010
A B C D E F G H I J K L M
M B D F H J L A C E G I K
L B E H K A D G J M C F I
K B F J A E I M D H L C G
J B G L D I A F K C H M E
I B H A G M F L E K D J C
H B I C J D K E L F M G A
G B J E M H C K F A I D L
F B K G C L H D M I E A J
E B L I F C M J G D A K H
D B M K I G E C A L J H F
C B A M L K J I H G F E D
B B B B B B B B B B B B B
posted by chairface at 9:45 PM on October 4, 2010
I don't think it can be done. Take my results above. B would need to be followed by every letter other than itself. There are only 12 such letters though, and we need 13 lines. So by inspection, replace the last line with:
B gets to go first once and that picks up (all?) the missing transitions.
Thanks for a fun problem!
My faulty python code below:
posted by chairface at 10:01 PM on October 4, 2010
B D C I L G K M A H E J F
B gets to go first once and that picks up (all?) the missing transitions.
Thanks for a fun problem!
My faulty python code below:
def sym(i):
return chr(ord('A')-1+i)
def main():
for outer in range(0,13):
start = 14 - outer
if start == 14:
start = 1
skip = outer + 1
for inner in range(0,13):
print sym(start),
start += skip
if start > 13:
start -= 13
print
if __name__ == "__main__":
main()
posted by chairface at 10:01 PM on October 4, 2010
I would define the lines as having a "skip", which lays out the order. A skip of one is:
ABCDEFGHIJKLM
Skip of two:
ACEGIKMBDFHJL
The problem with this approach is you generate twelve lines that work out just fine...then what about the thirteenth? You can't do a "skip of thirteen," obviously, because that's just a repetition of the same letter.
You might at first think that since you've got one possible skip "left over" from each line (e.g., if the skip-of-one line is ABCDEFGHIJKLM, you have MA left over; and if your skip-of-three line is LBEHKADGJMCFI, you have IL left over; etc.) you could string the unused combinations into the thirteenth line. The problem is that the left over skips—one each of one through twelve—add up to 78, a multiple of thirteen, which would mean the first and last letter of the final line would be identical.
posted by DevilsAdvocate at 10:14 PM on October 4, 2010
ABCDEFGHIJKLM
Skip of two:
ACEGIKMBDFHJL
The problem with this approach is you generate twelve lines that work out just fine...then what about the thirteenth? You can't do a "skip of thirteen," obviously, because that's just a repetition of the same letter.
You might at first think that since you've got one possible skip "left over" from each line (e.g., if the skip-of-one line is ABCDEFGHIJKLM, you have MA left over; and if your skip-of-three line is LBEHKADGJMCFI, you have IL left over; etc.) you could string the unused combinations into the thirteenth line. The problem is that the left over skips—one each of one through twelve—add up to 78, a multiple of thirteen, which would mean the first and last letter of the final line would be identical.
posted by DevilsAdvocate at 10:14 PM on October 4, 2010
(Didn't preview, obviously.)
B would need to be followed by every letter other than itself. There are only 12 such letters though, and we need 13 lines.
Which means if a perfect solution is possible, B (and every other letter) would have to be the last letter on one line.
posted by DevilsAdvocate at 10:17 PM on October 4, 2010
B would need to be followed by every letter other than itself. There are only 12 such letters though, and we need 13 lines.
Which means if a perfect solution is possible, B (and every other letter) would have to be the last letter on one line.
posted by DevilsAdvocate at 10:17 PM on October 4, 2010
Best answer: I hacked up the code a bit more to see what transitions the initial 12 rows will miss:
['MA', 'DC', 'FD', 'HE', 'JF', 'LG', 'AH', 'CI', 'EJ', 'GK', 'IL', 'KM']
My manually added last row covers all these but FD so I think my inspection was ok. Interestingly, you could make a 13 row that just doesn't use B at all and that would cover all transitions but that seems unfair.
posted by chairface at 11:08 PM on October 4, 2010
['MA', 'DC', 'FD', 'HE', 'JF', 'LG', 'AH', 'CI', 'EJ', 'GK', 'IL', 'KM']
My manually added last row covers all these but FD so I think my inspection was ok. Interestingly, you could make a 13 row that just doesn't use B at all and that would cover all transitions but that seems unfair.
posted by chairface at 11:08 PM on October 4, 2010
Response by poster: chairface's comes really close. I changed the 11th one so that B has the chance to go last once, and the put the missing transitions into the 13th. There are still some doubles, but it might be the closest I can get:
A B C D E F G H I J K L M
M B D F H J L A C E G I K
L B E H K A D G J M C F I
K B F J A E I M D H L C G
J B G L D I A F K C H M E
I B H A G M F L E K D J C
H B I C J D K E L F M G A
G B J E M H C K F A I D L
F B K G C L H D M I E A J
E B L I F C M J G D A K H
D M K I G E C A L J H F B
C B A M L K J I H G F E D
B D C I L G K M A H E J F
posted by rottytooth at 5:49 AM on October 5, 2010
A B C D E F G H I J K L M
M B D F H J L A C E G I K
L B E H K A D G J M C F I
K B F J A E I M D H L C G
J B G L D I A F K C H M E
I B H A G M F L E K D J C
H B I C J D K E L F M G A
G B J E M H C K F A I D L
F B K G C L H D M I E A J
E B L I F C M J G D A K H
D M K I G E C A L J H F B
C B A M L K J I H G F E D
B D C I L G K M A H E J F
posted by rottytooth at 5:49 AM on October 5, 2010
My monte-carlo solution has thrown up:
posted by mjg123 at 4:14 PM on October 5, 2010
ABCDEFGHIJKLM BAMDIFALKFBKC CJFJAKDFEHEMJ DCEBHCAEGKBJG EJEDGCLCGBGME FDHKGIBDJIAHB GAICIEKMIHJBF HFMKHAJDBIDMH IMBMACBLDKADL JCHDAFHLGJCFC KELEAGFLHMGFI LBECMFKJMLFKJ MCKILJHGEIKIK 6 missing combinations: [GD, GL, IG, JL, LA, LI]and a few other similar ones. I'll post if there's anything better waiting when I wake up.
posted by mjg123 at 4:14 PM on October 5, 2010
Yeah, nice puzzle.
posted by mjg123 at 4:29 PM on October 5, 2010
ABCDEFGHIJKLM BKCBMIEDGCEGJ CLDHCJDIHDMAC DFJGDKFBHKELC EIMECILGAJCGE FMLBEAMBICFLF GBDLIDAHGMCMD HLJIGIBJHALHJ IFDJFAEMKGKAI JMFHEHFEHEKBG KMHBAFCAFKDCK LEJLKHMJAKIAD MGFIKJEBLAGLA 4 missing combinations: [BF, CH, DB, JB]
posted by mjg123 at 4:29 PM on October 5, 2010
ABCDEFGHIJKLM BFILIDBHEKIHJ CLDMLJMBMIELC DCKFHDACMGBEC EDGIAHLFBGFDL FJHCFMAKGKEAL GAMCIKCBAEMFA HFCHGLEBIBLKH IMDJCGJDIFKBD JAGCJLBJGEIGE KMHBKAFLGMKJF LADKDHMJEGDFE MEHAICAJICEJB 2 missing combinations: [HK, LH]
posted by mjg123 at 10:06 PM on October 5, 2010
Response by poster: Actually, these last one has people repeated within the run, so it won't work for me. I ended up using a variation of chairface's
posted by rottytooth at 9:04 AM on October 28, 2010
posted by rottytooth at 9:04 AM on October 28, 2010
This thread is closed to new comments.
Balanced Latin squares are used in multi-condition experiments to ensure that condition orders are randomized fairly (counterbalanced) to remove ordering effects such as practice effects. The relevant part for you is that, given some number n, you will be able to create n completely different permutations of a sequence, making sure that artist A will follow B once, C once, D once, &c.
It looks like this helpful page has already worked out balanced Latin squares. I've reproduced the first little bit here for size = 13, to illustrate what I mean:
1: A B M C L D K E J F I G H
2: B C A D M E L F K G J H I
3: C D B E A F M G L H K I J
...
It's actually pretty fun and easy to create balanced Latin squares! Here are instructions on how to create one on your own.
posted by tickingclock at 4:58 PM on October 4, 2010 [2 favorites]