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

Question

РЕДАКТИРОВАТЬ : См. Программное решение "Кто владеет Зеброй"? для аналогичного класса проблемы

На LSAT есть категория логических проблем, которая идеткак это:

Семь последовательных временных интервалов для трансляции, пронумерованных в хронологическом порядке от I до 7, будут заполнены шестью лентами песен - G, H, L, O, P, Sи ровно одна лента новостей.Каждая лента должна быть назначена на другой временной интервал, и ни одна лента не длиннее, чем любая другая лента.Трансляция подчиняется следующим ограничениям:
L должен воспроизводиться непосредственно перед O.
Лента новостей должна воспроизводиться через некоторое время после L.
Должно быть ровно два временных интервала между G и P,независимо от того, идет ли G до P или G идет после P.

Я заинтересован в создании списка перестановок, которые удовлетворяют условиям как способ обучения для теста и каквызов программирования.Тем не менее, я не уверен, что это за класс проблемы перестановок.Я обобщил проблему типов следующим образом:

Учитывая массив n-длины A:

1. Сколько способов можно разместить набор из n уникальных элементов в пределах A?Например.Сколько существует способов перестановки ABCDEFG?
2. Если длина набора уникальных элементов меньше, чем длина A, сколько способов можно разместить в пределах A, если элементов в наборе может быть больше?чем один раз?Например.ABCDEF => AABCDEF;ABBCDEF и т. Д.
3. Сколько способов можно разместить набор уникальных элементов в пределах А, если элементы набора находятся в «условиях блокирования»?

Моя мысль состоит в том, чтобызакодируйте ограничения и затем используйте что-то вроде itertools Python для генерации перестановок.Мысли и предложения приветствуются.

Answer 1

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

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

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

Определение:

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

Минимизировать сумму вектора 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 для ограничений и посмотрите, что получится.

Answer 2

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

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

Я не проверял это, но это общее представление о том, как бы я занялся кодированием такого вопроса.

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