What category of combinatorial problems appear on

问题:

EDIT: See Solving "Who owns the Zebra" programmatically? for a similar class of problem

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:

1. How many ways can a set of n unique items be arranged within A? Eg. How many ways are there to rearrange ABCDEFG?
2. 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.
3. 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.

回答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

回答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.