4
$\begingroup$

Background: I am trying to design a scientific trial (computer science dissertation) in which participants will answer 8 questions. There are in fact only 4 questions but each is asked in two different ways, so there are 4 unique correct answers, let's call them a, b, c and d. So the set of correct answers will be {a, a, b, b, c, c, d, d}.

The 8 trial questions must appear in a random order however no question with the same correct answer must appear immediately after the other. So e.g. asking a question with answer a means the next question must not also have answer a.

I would like to produce a list of the permutations of {a, a, b, b, c, c, d, d} that do not repeat in this way. I am trying to write an algorithm for this but I'm having a little trouble with the mathematics. Any help would be greatly appreciated.

Could anyone give me some hints on how to either produce this list or how to reduce the list of 2520 permutations of {a, a, b, b, c, c, d, d} to only contain permutations with my condition?

Thanks.

  • 0
    Wonderful! Thanks for that find!2012-01-12

2 Answers 2

4

I know your question as a married couple seating problem: $n$ couples go to the cinema and for some reason spouses do not want to sit next to each other.

The number can be calculated by inclusion-exclusion: you calculate the total number of ways the eight answers can be arranged $8!/2^4$, subtract the number where one pair is stuck together $4\times 7!/2^3$, add the number where two pairs are stuck together ${4 \choose 2}\times 6!/2^2$, subtract ${4 \choose 3}\times 5!/2^1$ and add ${4 \choose 4}\times 4!/2^0$. This gives a result of 864.

So in general you have $\sum_{i=0}^n (-1)^i {n \choose i} (2n-i)! / 2^{n-i}$ and in fact the $n=0$ and $n=1$ terms cancel out.

Although there may only be 2520 permutations of your four pairs of answers, there are in fact 40320 permutations of the questions in total ($2^4$ times as many). Similarly there are $2^4$ times as many acceptable permutations of the questions where no identical answers are together, i.e. 13824 and the general term becomes $\sum_{i=0 }^n (-2)^i {n \choose i} (2n-i)! $

OEIS A114938 and A007060 give more terms if you need them. It looks as if for a large number of pairs, about 36.7% of permutations meet the required condition, so an easy way to generate one in particular rather than all at once might be to take a random permutation but if it fails choose another until you have one which meets the condition.

  • 1
    @Vincent Tjeng: see http://math.stackexchange.com/questions/465318/showing-probability-no-husband-next-to-wife-converges-to-e-1 for yet another question which converges to $\exp(-1)$. It is a common limit for such questions2015-01-17
1

In case you do still need code in Mathematica to solve your problem - this should give you exactly what you need.

Characters /@ (Select[#, StringFreeQ[#, RegularExpression["aa|bb|cc|dd"]] &] &@ Map[StringJoin, #, 1] &@Permutations[Characters["aabbccdd"]])

  • 0
    do comment if you'd like me to explain the code!2013-03-24