Программирование для молодых таблиц

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

Таблица Юнга представляет собой диаграмму Феррера из N блоков, заполненных целыми числами от 1 до N. Пример:
young tableaux
(источник: olimpiadiproblemsolving.it)

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


ПРОБЛЕМА

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

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

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

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

Ответы

Ответ 1

Вот пример решения с использованием 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, #<).

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

?- 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.

Ответ 2

Чтобы решить эту проблему, я бы использовал Программу ограничения (CP). Таблицы Young - фактически одна из стандартных проблем, которые я пытаюсь решить при изучении новой системы 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" ) обрабатывается в соответствии с структурой Young/Ferrer (подробности см. В модели).

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

  • определенное число должно быть в 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 решений

Ответ 3

Без использования программы я считаю, что ответ на 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

- или -

12 14

13

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

Ответ 4

Это проблема программирования логического ограничения. Используйте язык программирования Prolog. Пролог 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

Ответ 5

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