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.

Improve this question
$\endgroup$
  • $\begingroup$ P.s. if anyone can suggest software or e.g. a method to do this in Mathematica that would be fine too! $\endgroup$ – Danny King Jan 12 '12 at 0:51
  • $\begingroup$ UPDATE: I believe I found a tool that does it at users.telenet.be/vdmoortel/dirk/Maths/permutations.html however I do not trust the output. It produces 864 permutations. Can anyone help me prove this is the number of permutations I was looking for? $\endgroup$ – Danny King Jan 12 '12 at 1:03
  • 1
    $\begingroup$ This page answers your question: ken.duisenberg.com/potw/archive/arch04/040714sol.html though a more general solution would be nice $\endgroup$ – nolion Jan 12 '12 at 1:13
  • $\begingroup$ Wonderful! Thanks for that find! $\endgroup$ – Danny King Jan 12 '12 at 1:29
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ I just wanted to thank you for your very clear description. You have helped me tremendously to understand the theory enough to feel confident that my trial design is correct. $\endgroup$ – Danny King Jan 22 '12 at 15:23
  • $\begingroup$ Harry. may I ask how you calculated that about 36.7% of permutations meet my required condition of non-consecutive permutations? $\endgroup$ – Danny King Apr 20 '12 at 2:50
  • $\begingroup$ Henry, not Harry. I took the second expression for large $n$ and divided it by $(2n)!$ [I could have taken the first and divided it by $(2n)!/2^n$] and then looked at what value it tended towards. For example, using the R code sum((-2)^(0:n) * choose(n,0:n) * factorial(2*n - (0:n)) ) / factorial(2*n) for $n=4$ I get 0.3428571 but for $n=64$ I get 0.366434 $\endgroup$ – Henry Apr 22 '12 at 9:59
  • $\begingroup$ By the way - 36.7% is approximately $\frac{1}{e}$, and I'm sure there's a reason why! $\endgroup$ – Vincent Tjeng Jan 17 '15 at 17:14
  • 1
    $\begingroup$ @Vincent Tjeng: see math.stackexchange.com/questions/465318/… for yet another question which converges to $\exp(-1)$. It is a common limit for such questions $\endgroup$ – Henry Jan 17 '15 at 19:53
1
$\begingroup$

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"]])

Improve this answer
$\endgroup$
  • $\begingroup$ do comment if you'd like me to explain the code! $\endgroup$ – Vincent Tjeng Mar 24 '13 at 9:43

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.