What category of combinatorial problems appear on the logic games section of the LSAT?

Answer 1

Okay, so the way I see it, there are two ways to approach this problem:

1. Go about writing a program that will approach this problem head first. This is going to be difficult.

2. But combinatorics teaches us that the easier way to do this is to count all permutations and subtract the ones that don't satisfy your constraints.

I would go with number 2.

You can find all permutations of a given string or list by using this algorithm. Using this algorithm, you can get a list of all permutations. You can now apply a number of filters on this list by checking for the various constraints of the problem.

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 general idea of how I would go about coding such a question.

Hope this helps

Answer 2

This is easy to solve (a few lines of code) as an integer program. Using a tool like the GNU Linear Programming Kit, you specify your constraints in a declarative manner and let the solver come up with the best solution. Here's an example of a GLPK program.

You could code this using a general-purpose programming language like Python, but this is the type of thing you'll see in the first few chapters of an integer programming textbook. The most efficient algorithms have already been worked out by others.

EDIT: to answer Merjit's question:

Define:

1. matrix Y where Y_(ij) = 1 if tape i is played before tape j, and 0 otherwise.
2. vector C, where C_i indicates the time slot when i is played (e.g. 1,2,3,4,5,6,7)
3. Large constant M (look up the term for "big M" in an optimization textbook)

Minimize the sum of the vector C subject to 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

That should get you most of the way there. You want to write up the above constraints in the MathProg language's syntax (as shown in the links), and make sure I haven't left out any constraints. Then run the GLPK solver on the constraints and see what it comes up with.