Программирование для картин Янга

Далее следует странный вопрос:
Я участвую в соревновании по решению задач в моей школе, и нам разрешают пользоваться компьютером. Поскольку я единственный среди конкурентов, кто умеет программировать, я использую программы на C и Pascal для более быстрого решения задач. Я сделал это с помощью упражнений псевдокода в код, алгоритмов, проверки гипотезы Коллатца и тому подобного.
Вчера я тренировался перед следующим испытанием (18 апреля) и увидел упражнение по картинам Юнга. Это было сформулировано так (я постараюсь перевести с итальянского):
"Диаграммы Феррера представляют собой конфигурацию из N блоков, распределенных в один или несколько горизонтальных рядов, выровненных по левому краю и сконфигурированных таким образом, что каждый ряд содержит равное или количество ящиков меньше, чем ряд над ним. Эти конфигурации также могут быть описаны списком номеров ящиков, как на этом изображении:
диаграммы Ferrers
( источник: olimpiadiproblemsolving.it)

Молодой таблица представляет собой диаграмму Феррера из N ячеек, заполненных целыми числами от 1 до N. Пример:
< img src="https://i.stack.imgur.com/eOY6I.jpg" alt="молодые картины">
(источник: olimpiadiproblemsolving.it)

Если числа в ячейках отсортированы по возрастанию порядок по строке и по столбцу, таблица является «стандартной» (пример: первая, третья и пятая таблицы). В стандартных таблицах первое поле первой строки всегда содержит 1. N всегда находится в крайнем левом поле в одной из строк диаграммы.


ПРОБЛЕМА

Рассмотрим диаграмму [6,3,2,1,1,1] Феррера:
1) Если 6 зафиксировано на 6-м поле 1-й строки, а 11 зафиксировано на последнем поле 1-го столбца, как сколькими способами можно заполнить диаграмму стандартным способом?

2) Если 7 зафиксировано в 6-м квадрате 1-й строки, а 11 — в последнем квадрате 1-го столбца, сколькими способами можно вы заполните диаграмму стандартным способом?

3) Если 8 зафиксировано в 6-м квадрате 1-й строки, а 11 зафиксировано в последнем квадрате 1-го столбца, сколькими способами вы можете заполнить диаграмме стандартным способом?"

Я пытался закодировать решение с матрицей, заполненной этими числами и с "-1" в качестве "символа конца строки", но я застрял. Как Я кодирую «заполнить его всеми возможными способами, чтобы таблица была стандартной?».


c constraint-programming diagram prolog clpfd
person user2179983    schedule 29.03.2013    source источник
comment
Я думаю, что для этого Prolog был бы лучшим выбором инструмента, чем C.   -  person ppeterka    schedule 29.03.2013
comment
Давно я не видел здесь такого хорошо сформулированного вопроса. Вот, примите мой последний голос сегодня.   -  person    schedule 29.03.2013
comment
Эм... что такое Пролог?   -  person user2179983    schedule 29.03.2013
comment
Подумайте о том, как вы могли бы подсчитать количество способов его заполнения, фактически не создавая решения. Динамическое программирование, запоминание и рекурсия будут вашими друзьями. Поскольку другие конкуренты не используют программы, должно быть решение, не требующее большого объема вычислений. Отличный вопрос!   -  person japreiss    schedule 29.03.2013
comment
Нарисовав таблицу, я заметил, что она выглядит так же, если я поверну лист бумаги в том месте, где я его нарисовал, на 90° по часовой стрелке. Кроме того, в первом столбце может быть любое число от 1 до 11, кроме 1,6 и 11, а в первой строке любое число от 1 до 6, кроме 1 и 6. Всего ящиков 14, поэтому N=14. Хм.   -  person user2179983    schedule 29.03.2013
comment
Последнее требование стандартной таблицы Юнга подразумевает, что последняя строка может иметь только один столбец. Это то, что вы намеревались?   -  person jxh    schedule 29.03.2013
comment
Таким образом, у вас уже есть преимущество перед другими конкурентами, поскольку вы единственный, кто использует компьютер, и этого недостаточно. Вы также хотите, чтобы пользователи SO помогли вам победить их. Бой честный. ;-)   -  person Randy Howard    schedule 29.03.2013
comment
Эй, мы даже не самые лучшие. В смысле, я единственный в школе, кто умеет программировать, но моя команда заняла 15-е место в регионе (я живу в Италии). Мы собираемся на региональный вызов 18 апреля, и нам нужно решить еще как минимум 2 упражнения, чтобы победить в первом. Один из них, для другого я работаю с моим учителем информатики, чтобы написать алгоритм Дейкстры. программа.   -  person user2179983    schedule 30.03.2013

Ответы (5)


arrow_upward
6
arrow_downward

Вот пример решения с использованием SWI-Prolog для первой задачи:

:- use_module(library(clpfd)).

tableau(Ts) :-
        Ts = [[A,B,C,_,_,F],
              [G,H,I],
              [J,K],
              [L],
              [M],
              [N]],
        A = 1,
        maplist(ascending, Ts),
        ascending([A,G,J,L,M,N]),
        ascending([B,H,K]),
        C #< I,
        append(Ts, Vs),
        all_different(Vs),
        Vs ins 1..14,
        F = 6,
        N = 11,
        label(Vs).

ascending(Vs) :- chain(Vs, #<).

Ответ заключается в том, что есть 2 способа заполнить таблицу:

?- tableau(Ts), maplist(writeln, Ts).
[1,2,3,4,5,6]
[7,12,13]
[8,14]
[9]
[10]
[11]
    Ts = [[1, 2, 3, 4, 5, 6], [7, 12, 13], [8, 14], [9], [10], [11]] ;
[1,2,3,4,5,6]
[7,12,14]
[8,13]
[9]
[10]
[11]
    Ts = [[1, 2, 3, 4, 5, 6], [7, 12, 14], [8, 13], [9], [10], [11]] ;
false.
person mat    schedule 31.03.2013
comment
Большое спасибо! Этот работает, консультируя его с SWIProlog, и я научился манипулировать им для любой проблемы с таблицами Юнга! Спасибо еще раз! - person user2179983; 04.04.2013

arrow_upward
4
arrow_downward

Чтобы решить эту проблему, я бы использовал программирование с ограничениями (CP). Таблицы Юнга на самом деле являются одной из стандартных задач, которые я пытаюсь решить при изучении новой системы CP. Вот список реализаций на данный момент: http://hakank.org/common_cp_models/#youngtableaux .

Я изменил «простую» модель MiniZinc с некоторыми дополнительными ограничениями для ваших конкретных вопросов. См. полную модель здесь: http://www.hakank.org/minizinc/young_tableaux_stack_overflow.mzn

(MiniZinc очень высокого уровня и с ним легко экспериментировать для подобных проблем.)

Кратко о представлении в модели: для задачи размера n (раздел n) блоки представлены в виде сетки («x», размером n, умноженной на n) со значениями от 1 до n+1, где каждая строка и столбец сортируются по возрастанию; поэтому n+1 сортируется последним и действует как пустое значение. Затем структура раздела («p») обрабатывается для соответствия структуре Юнга/Феррера (подробности см. в модели).

Каждый из трех вопросов имеет два дополнительных ограничения (по сравнению со стандартной постановкой задачи):

  • определенное число должно быть в 6-м поле первой строки Добавленное ограничение: x[1,6] = 6 % или 7 или 8

  • и 11 должно быть в последнем поле первого столбца. Это немного сложнее, но мой способ таков, то есть в первом столбце 11 должно быть последним из значений меньше, чем n+1, то есть все значения, следующие в столбце n+1:

     exists(j in 1..n) (
      x[j,1] = 11 /\ forall(k in j+1..n) (x[k,1] = n+1)
 )

Итак, если я правильно понял вопросы, ответы такие: 1) 2 решения 2) 10 решений 3) 30 решений

person hakank    schedule 01.04.2013
comment
Очень интересная ссылка! Я никогда не слышал ни об одной из систем CP, упомянутых там, или о самой CP, но выглядит интересно. Я посмотрю на это. Спасибо. - person user2179983; 04.04.2013
comment
Распространение ограничений полезно знать для многих классов головоломок или задач. Когда я изучаю новый язык, я обычно переношу решатель судоку на Python Питера Норвига. Стоит прочитать, и это небольшое введение в распространение ограничений. - person Dave Newman; 04.04.2013

arrow_upward
1
arrow_downward

Я считаю, что без использования программы ответ на 1) равен 2. Получение этого вручную может привести кого-то к алгоритмическому решению.

Первая строка начинается с 1 и заканчивается на 6. Следовательно, числа, которые могут попасть в строку 1, должны удовлетворять следующему условию: 1 ‹ x ‹ 6. Из 14 цифр, которые могут войти в эту таблицу, только 4 удовлетворяют этому условию, и они составляют: 2 3 4 5. Это означает, что строка 1 должна быть: 1 2 3 4 5 6.

Первый столбец начинается с 1 и заканчивается на 11. Числа, которые могут попасть в первый столбец, должны удовлетворять аналогичному условию: 1 ‹ y ‹ 11. Из оставшихся не присвоенных чисел только 4 удовлетворяют этому условию: 7 8 9 10. Это приводит к тому, что первый столбец будет: 1 7 8 9 10 11.

Теперь осталось только 3 числа: 12 13 14. Есть только два способа расположить их в оставшихся 3 ячейках таблицы. Их можно оформить:

12 13

14

-- or --

12 14

13

Пытаясь решить эту проблему в коде, можно пойти путем грубой силы или изучить методы распространения ограничений и возврата. Вот почему кто-то ранее предложил Пролог. Еще один язык, на который стоит обратить внимание, — это Python.

person Dave Newman    schedule 29.03.2013
comment
Я только что заметил, что также обновлял страницу, чтобы добавить это к вопросу. 1-я строка должна быть 1 2 3 4 5 6. 1-я колонка должна быть 1 ? ? 9 10 11, потому что 4 и 5 ряд выполнены из 1 коробки. Это также верно для 2) и 3), которые просто добавляют больше возможных чисел в 1-ю строку. Решение, которое вы только что написали, имеет проблему: в 2) и 3) вы не можете записать 1-й столбец как 1 7 8 9 10 11, потому что 7 назначено в 2) и 8 назначено в 3). Если вы инвертируете 7 и 6 в 2) и 6 и 8 в 3) (инвертируя также 6 и 7 так, чтобы 1-й столбец был 1 6 7 9 10 11), ответ на 2) и 3) тоже будет 2. - person user2179983; 29.03.2013
comment
Означает ли это, что в таблице [6,3,2,1,1,1], где 11 зафиксировано в последней ячейке 1-го столбца и где любое число ‹11 зафиксировано в последней ячейке 1-й строки, имеет 2 стандартные решения? - person user2179983; 29.03.2013
comment
Я уже нашел 6 решений для таблиц, которые соответствуют вашим первоначальным ограничениям. Таблицы, которые я пытаюсь: 8 в последней ячейке первой строки и 11 в последней ячейке первого столбца. Вероятно, есть более 6 решений, но я подошел к концу своего перерыва на работе. :) - person Dave Newman; 29.03.2013
comment
Хорошо, то, что я написал в качестве комментария к этому, неверно. Спасибо ;) Кроме того, чтобы сделать это на C, мне пришлось бы написать много функций, и я думаю, что это было бы очень неэффективно. - person user2179983; 04.04.2013

arrow_upward
0
arrow_downward

Это проблема программирования логики ограничений. Используйте язык программирования Пролог. Пролог Sicstus с библиотекой clpfd.

Учитывая компоновку как таковую:

ABCDEF
GHI
JK
L
M
N

--Код--

use_module(library(clpfd)).

all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N]),
domain([A,B,C,D,E,F,G,H,I,J,K,L,M,N],1,14),
B #> A, C #> B, D #> C, E #> D, F #> E,
G #> A, H #> B, H #> G, I #> G, I #> H,  I #> C,
J #> A, J #> G, 
L #> A, L #> G, L #> J,
M #> A, M #> G, M #> J, M #> L,
N #> A, N #> G, N #> J, N #> L, N #> M.

A=1
F=6
N=11
person Lefteris E    schedule 29.03.2013
comment
Я попытался скопировать это в файл и проконсультироваться с SWIProlog, но это дает мне непредвиденную ошибку конца файла. Что я должен делать? Я пробовал гуглить, но ничего. :( - person user2179983; 30.03.2013

arrow_upward
0
arrow_downward

Это упражнение из знаменитой книги Кормена. Я считаю этот ресурс полезным для изучения этой проблемы, и создайте такую ​​структуру, извлеките минимальный элемент и сохраните структуру данных как есть.

person Gorav Singal    schedule 23.07.2019