1
$\begingroup$

Eight different boys and five different girls are in a row. Girls are required to be next to each other. How many ways are there (the answer is $9!\times5!$)?

Cases[Permutations[Array[boy, 8]~Join~Array[girl, 5]], {___, girl[_], 
   girl[_], ___}] // Length
General::nomem: The current computation was aborted because there was insufficient memory available to complete the computation.

However, the above code indicates that there is not enough memory. What is the memory saving way to solve this problem? Feel free to correct the grammar mistakes and unidiomatic expressions in my posts, please.

$\endgroup$
2
  • $\begingroup$ You first create more than 6 billion permutations, no wonder that you have not enough memory. Instead of creating all permutations and then selecting, you could use NextPermutation from the package Combinatorica . However, this could take a long tome. $\endgroup$ Feb 25 at 8:50
  • 3
    $\begingroup$ Think of 5 gs (g1, ,g2, g3,g4,g5) as a single G (since gs need to stay together). Then 9 objects (G and b1, b2,.., b8) can be arranged in 9! ways, and, for each of 9! permutations, G can be arranged in 5! ways. Hence the answer 9! 5!. $\endgroup$
    – kglr
    Feb 25 at 9:55
2
$\begingroup$

Ambiguous question, smells like homework. Is it?

In any case, the proper way to solve this is via the combinatorics, questions of which belong elsewhere.

If you insist on a more brute force means such as shown, one way is as follows. I presume an arrangement with girl-1 to the left of girl-2 differs from one where they are reversed, and that the criteria is no girl can be isolated from another girl.

Then:

class = Join[ConstantArray[b, 8], ConstantArray[g, 5]]
Times @@ (Tally[class][[All, 2]]!)*
 Count[Permutations[class], z_ /; FreeQ[Split[z], {g}]]

391910400

N.B.: This does not match your 9! 5!, it does match directly tested smaller cases using the above criteria.

$\endgroup$

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.