What category of combinatorial problems appears in the logic games section of the LSAT?
EDIT : See Solution and Who Owns Zebra "Programmatically?" For a similar class of problems
There is a logical task category in the LSAT that looks like this:
Seven consecutive broadcast time slots, numbered in chronological order from i to 7, will be filled with six song feeds - G, H, L, O, P, S - and exactly one news feed. Each tape must be assigned to a different time slot, and no tape will be larger than any other tape. Broadcasting is subject to the following restrictions:
L must be played just before O.
News feed must be played some time after L.
There must be exactly two time slots between G and P, regardless of whether G comes before P or G comes after P.
I'm interested in creating a list of permutations that satisfy the conditions as a way of learning a test and as a programming challenge. However, I'm not sure what class of the permutation problem. I generalized the type problem as follows:
Given an n-length array A:
- How many ways can a set of n unique elements be set inside A? For instance. How many ways to change ABCDEFG?
- If the length of the set of unique elements is less than the length of A, how many ways can A be set if the elements in the set can occur more than once? For instance. ABCDEF => AABCDEF; ABBCDEF etc.
- How many ways can a set of unique elements within A be set if the elements of the set are subject to "locking conditions"?
My thought is to code the constraints and then use something like Python's itertools to generate the permutations. Thoughts and suggestions are welcome.
a source to share
Ok so I see it, there are two ways to approach this problem:
-
Move on to writing a program that will first approach this problem. It will be hard.
-
But combinatorics teaches us that an easier way to do this is to count all permutations and subtract those that don't satisfy your constraints.
I would go with number 2.
You can find all permutations of a given string or list using this algorithm . Using this algorithm, you can get a list of all permutations. You can now apply multiple filters in this list by checking the various problem limits.
def L_before_O(s):
return (s.index('L') - s.index('O') == 1)
def N_after_L(s):
return (s.index('L') < s.index('N'))
def G_and_P(s):
return (abs(s.index('G') - s.index('P')) == 2)
def all_perms(s): #this is from the link
if len(s) <=1:
yield s
else:
for perm in all_perms(s[1:]):
for i in range(len(perm)+1):
yield perm[:i] + s[0:1] + perm[i:]
def get_the_answer():
permutations = [i for i in all_perms('GHLOPSN')] #N is the news tape
a = [i for i in permutations if L_before_O(i)]
b = [i for i in a if N_after_L(i)]
c = [i for i in b if G_and_P(i)]
return c
I haven't tested this, but this is a general idea of how I would code a question like this.
Hope it helps
a source to share
It's easy to solve (a few lines of code) as an integer program. By using a tool such as the GNU Linear Programming Kit , you specify your constraints in a declarative way and let the solver find the best solution. Here's a sample GLPK program.
You can code this using a general purpose programming language like Python, but this is the type of thing you'll see in the early chapters of an integer programming tutorial. The most efficient algorithms have already been developed by others.
EDIT: To answer Merjit's question:
Definition:
- matrix Y, where Y_ (ij) = 1 if tape i is played before tape j, and 0 otherwise.
- vector C where C_i indicates the time interval when i (eg, 1,2,3,4,5,6,7).
- Big constant M (look up the term for "big M" in the optimization tutorial)
Minimize the sum of the vector C with the following constraints:
Y_(ij) != Y_(ji) // If i is before j, then j must not be before i
C_j < C_k + M*Y_(kj) // the time slot of j is greater than the time slot of k only if Y_(kj) = 1
C_O - C_L = 1 // L must be played immediately before O
C_N > C_L // news tape must be played at some time after L
|C_G - C_P| = 2 // You will need to manipulate this a bit to make it a linear constraint
This should get you the most of the way. You want to capture the above restrictions in the syntax of the MathProg language (as shown in the links) and make sure I don't leave any restrictions. Then run the GLPK solver on constraints and see what it comes up with.
a source to share