Какие категории комбинаторных задач появляются в разделе логических игр LSAT?

Итак, как я понимаю, есть два пути решения этой проблемы:

1. Подумайте о написании программы, которая в первую очередь решит эту проблему. Это будет сложно.

2. Но комбинаторика учит нас, что более простой способ сделать это - подсчитать все перестановки и вычесть те, которые не удовлетворяют вашим ограничениям.

Я бы выбрал номер 2.

Вы можете найти все перестановки данной строки или списка, используя этот алгоритм. Используя этот алгоритм, вы можете получить список всех перестановок. Теперь вы можете применить ряд фильтров к этому списку, проверив различные ограничения проблемы.

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

Я не тестировал это, но это общее представление о том, как я буду писать такой вопрос.

Надеюсь это поможет

Это легко решить (несколько строк кода) как целочисленную программу. Используя такой инструмент, как GNU Linear Programming Kit, вы декларативно указываете свои ограничения и пусть решатель найдет лучшее решение. Вот пример программы GLPK.

Вы можете закодировать это, используя язык программирования общего назначения, такой как Python, но именно такие вещи вы увидите в первых нескольких главах учебника по целочисленному программированию. Наиболее эффективные алгоритмы уже разработаны другими.

РЕДАКТИРОВАТЬ: чтобы ответить на вопрос Мерджита:

Определять:

1. матрица Y, где Y_ (ij) = 1, если лента i воспроизводится перед лентой j, и 0 в противном случае.
2. вектор C, где C_i указывает временной интервал, когда играется i (например, 1,2,3,4,5,6,7)
3. Большая константа M (найдите термин "большой M" в учебнике по оптимизации)

Минимизируйте сумму вектора C при следующих ограничениях:

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

Это должно помочь вам добраться до цели. Вы хотите записать указанные выше ограничения в синтаксисе языка MathProg (как показано в ссылках) и убедиться, что я не пропустил никаких ограничений. Затем запустите решатель GLPK для ограничений и посмотрите, что он даст.