What category of combinatorial problems appear on the logic games section of the LSAT?
- by Merjit
There's a category of logic problem on the LSAT that goes like this:
Seven consecutive time slots for a broadcast, numbered in chronological order I through 7, will be filled by six song tapes-G, H, L, O, P, S-and exactly one news tape. Each tape is to be assigned to a different time slot, and no tape is longer than any other tape. The broadcast is subject to the following restrictions:
L must be played immediately before O.
The news tape must be played at some time after L.
There must be exactly two time slots between G and
P, regardless of whether G comes before P or whether G comes after P.
I'm interested in generating a list of permutations that satisfy the conditions as a way of studying for the test and as a programming challenge. However, I'm not sure what class of permutation problem this is. I've generalized the type problem as follows:
Given an n-length array A:
How many ways can a set of n unique items be arranged within A? Eg. How many ways are there to rearrange ABCDEFG?
If the length of the set of unique items is less than the length of A, how many ways can the set be arranged within A if items in the set may occur more than once? Eg. ABCDEF = AABCDEF; ABBCDEF, etc.
How many ways can a set of unique items be arranged within A if the items of the set are subject to "blocking conditions"?
My thought is to encode the restrictions and then use something like Python's itertools to generate the permutations. Thoughts and suggestions are welcome.
