Интересная задачка: как автоматизировать выборку

[Nataly-Mak]

Нет у меня пока никакого, ручками выбираю

[caxap]

Nataly-Mak в сообщении #364301 писал(а):

Можно брать строки и столбцы в любом месте

Можно сделать так: "отсортировать" массив сначала по строкам, потом по столбцам. Максимальный квадрат будет в угле. На Ruby это легко реализуется: вот. Возможно есть какой-нибудь крутой алгоритм, но и так работает быстро -- ок. 100 мс, причем бОльшая часть этого времени тратится на вывод матрицы на экран . Также сразу виден размер максимального квадрата. Для приведённой матрицы это 10x10.

(Результат)

Хоть квадрата 13х13 нет, но 10х10 есть. Вот он.

$ ./37468-2.rb
Maximal square: 10x10

1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  0  0  1  1  1  1  1  1  0  1  1  0  0  0  0  0
1* 0  0  1* 1* 1* 1* 1* 1* 0  0  1* 1  0  1  1* 1*
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  0  0  1  1  1  1  1  1  0  0  0  0  0  0  1  0
1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  1  1
1  0  1  1  1  1  1  1  1  1  0  1  1  0  1  1  0
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  1
1* 1  1  1* 1* 1* 1* 1* 1* 1  0  1* 0  1  1  1* 1*
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  1  0  1  1  1  1  1  1  0  1  1  1  0  1  1  0
1  1  1  1  1  1  1  1  1  1  1  0  0  0  0  1  1
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  0  1  1  1  1  1  1  1  0  0  1  1  0  0  0  0
1  0  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  1  0  1  1  1  1  1  1  0  1  0  1  0  1  0  0
1  0  0  1  1  1  1  1  1  0  0  1  1  0  0  1  1
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  0  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0
1* 1  1  1* 1* 1* 1* 1* 1* 1  1  1* 1  1  1  1* 1*
1  0  0  1  1  1  1  1  1  0  1  0  0  0  1  1  0
1  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0
1  0  0  1  1  1  1  1  1  0  0  1  0  0  0  1  1
1  0  1  1  1  1  1  1  1  1  0  1  0  0  0  0  0
1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  0  0
1  1  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0
1  0  0  1  1  1  1  1  1  1  1  0  0  1  0  0  0
1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  0
1  0  0  1  1  1  1  1  1  1  0  0  1  0  0  0  1
1  0  0  1  1  1  1  1  1  1  0  0  0  0  0  0  0
1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0
1  1  0  1  1  1  1  1  1  1  0  0  0  0  1  0  0
1  0  0  1  1  1  1  1  1  0  0  1  0  0  1  0  0
1  1  0  1  1  1  1  1  1  1  0  1  0  0  0  0  0
1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0
1  1  0  1  1  1  1  1  1  0  0  1  0  0  0  0  0

[Nataly-Mak]

Спасибо большое. Буду разбираться.
У меня 11х11 уже легко вручную получаются, а вот 13х13 никак не получается пока

-- Чт окт 21, 2010 19:00:51 --

Посмотрела вашу программу. Теперь она стала намного длинее первой версии
Увы! Я в ней абсолютно ничего не понимаю. Придётся всё равно самой писать программу. Программа нужна такая, чтобы ввести в неё матрицу (в виде двумерного массива), и она проверила бы его на выборку максимального квадрата.
Но теперь есть пример решения, это уже хорошо.

[Yu_K]

Можно в Excel отсортировать столбцы и потом транспонировать и еще раз отсортировать столбцы и обратно транспонировать.

[Nataly-Mak]

сахар
спасибо за программу. Сохранила. Пытаюсь установить интерпретатор языка.
Если получится, то можно будет попробовать делать выборку максимального квадрата по вашей программе.
Сейчас получила большую матрицу 29х147. Единичек в ней мало, прямо глаза разбегаются. Кроме того, матрица большая для охвата глазами. Тут уже без программы трудно справиться. А надо выделить в этой матрице всего квадрат 7х7. При этом 4 столбца и три строки в матрице уже полностью состоят из единиц. Кажется, можно выделить квадрат, а вручную... хорошая игра, но времени нет играть

-- Пт окт 22, 2010 13:23:19 --

Предлагаю ещё одну интересную задачку, она тоже возникла при построении примитивных квадратов из простых чисел.

Найден такой примитивный прямоугольник 7х23, полностью состоящий из простых чисел:

199  239  1879  2069  2789  3529  4349 
 823  863  2503  2693  3413  4153  4973 
 1321  1361  3001  3191  3911  4651  5471 
 5857  5897  7537  7727  8447  9187  10007 
 7753  7793  9433  9623  10343  11083  11903 
 8389  8429  10069  10259  10979  11719  12539 
 9187  9227  10867  11057  11777  12517  13337 
 9649  9689  11329  11519  12239  12979  13799 
 11617  11657  13297  13487  14207  14947  15767 
 20599  20639  22279  22469  23189  23929  24749 
 25057  25097  26737  26927  27647  28387  29207 
 29383  29423  31063  31253  31973  32713  33533 
 30931  30971  32611  32801  33521  34261  35081 
 31729  31769  33409  33599  34319  35059  35879 
 51679  51719  53359  53549  54269  55009  55829 
 53239  53279  54919  55109  55829  56569  57389 
 63241  63281  64921  65111  65831  66571  67391 
 73141  73181  74821  75011  75731  76471  77291 
 78307  78347  79987  80177  80897  81637  82457 
 80167  80207  81847  82037  82757  83497  84317 
 106291  106331  107971  108161  108881  109621  110441 
 116539  116579  118219  118409  119129  119869  120689 
 130267  130307  131947  132137  132857  133597  134417

Выбирая любые 7 строк, мы будем получать примитивные квадраты 7х7 (которые легко превращаются в пандиагональные магические квадраты).

Задача такая. Надо сформировать из этой матрицы все квадраты 7х7 (понятно, что их количество равно числу сочетаний из 23 по 7), посчитать сумму чисел на главной диагонали каждого квадрата 7х7, далее проверить последовательность этих сумм - нет ли чётырёх одинаковых сумм.
Если есть, это значит, что мы имеем готовый пандиагональный квадрат 14-го порядка из простых чисел.
Примитивные квадраты, соответствующие одинаковым суммам, надо вывести, это результат работы программы. Может быть, хотя бы три одинаковые суммы найдутся, тоже можно вывести три квадрата. Четвёртый квадрат потом можно будет по-другому попытаться построить.

Задачка несложная в смысле алгоритма, но объёмная - комбинаций много будет.
В общем, для тех, кому хочется запрограммировать какую-нибудь задачу.

Например, вот первый примитивный квадрат 7х7:

199  239  1879  2069  2789  3529  4349 
 823  863  2503  2693  3413  4153  4973 
 1321  1361  3001  3191  3911  4651  5471 
 5857  5897  7537  7727  8447  9187  10007 
 7753  7793  9433  9623  10343  11083  11903 
 8389  8429  10069  10259  10979  11719  12539 
 9187  9227  10867  11057  11777  12517  13337

Сумма чисел на главной диагонали этого квадрата равна:

199 + 863 + 3001 + 7727 + 10343 + 11719 + 13337 = 47189

Как оценить вероятность появления в последовательности сумм хотя бы трёх одинаковых?

Замечу, что пандиагональный квадрат 14-го порядка из простых чисел ещё ни один не построен. Решение предложенной задачи позволит построить первый такой квадрат.

Да, конечно, есть тривиальное решение задачи: 4 одинаковых примитивных квадрата.
Полученные 4 квадрата должны быть хотя бы не полностью совпадающими (квадраты с переставленными строками и\или столбцами считаем одинаковыми). В идеале все 4 квадрата должны состоять из различных чисел.

[Nataly-Mak]

Получила в процессе поиска примитивного квадрата 13х13 ещё один примитивный прямоугольник 7х28. В нём на 5 строк больше. Тоже годится для сформулированной выше задачи, из этого прямоугольника можно получить ещё больше примитивных квадратов 7х7.

Вот только объединить эти два прямоугольника в один 7х51, к сожалению, нельзя (нарушится свойство примитивного прямоугольника).

(Оффтоп)

487 1777 2713 3373 3637 3673 3709
1187 2477 3413 4073 4337 4373 4409
3167 4457 5393 6053 6317 6353 6389
3677 4967 5903 6563 6827 6863 6899
7681 8971 9907 10567 10831 10867 10903
8747 10037 10973 11633 11897 11933 11969
10427 11717 12653 13313 13577 13613 13649
10691 11981 12917 13577 13841 13877 13913
16087 17377 18313 18973 19237 19273 19309
18097 19387 20323 20983 21247 21283 21319
21221 22511 23447 24107 24371 24407 24443
22717 24007 24943 25603 25867 25903 25939
24551 25841 26777 27437 27701 27737 27773
26251 27541 28477 29137 29401 29437 29473
29347 30637 31573 32233 32497 32533 32569
33091 34381 35317 35977 36241 36277 36313
33377 34667 35603 36263 36527 36563 36599
34897 36187 37123 37783 38047 38083 38119
39551 40841 41777 42437 42701 42737 42773
40867 42157 43093 43753 44017 44053 44089
46447 47737 48673 49333 49597 49633 49669
47237 48527 49463 50123 50387 50423 50459
48497 49787 50723 51383 51647 51683 51719
49927 51217 52153 52813 53077 53113 53149
61441 62731 63667 64327 64591 64627 64663
76471 77761 78697 79357 79621 79657 79693
101161 102451 103387 104047 104311 104347 104383
142537 143827 144763 145423 145687 145723 145759

[Nataly-Mak]

сахар
Процитирую ваш ответ в личке, поскольку он представляет общий интерес:

Цитата:

Суть алгоритма в сортировке матрицы по строкам и по столбацам таким образом, чтобы все единички съезжали в один угол. Потом просто из угла выбирается макс. квадрат. Посмотрите в файле: там нули отодвинуты в верхний левый угол, а единицы в правый нижний. Но, как видно, многие единицы, которые могли бы быть частью максимального квадрата остаются в серидине (т.к. сортировка происходит лексикографически: т.е. как слова в словаре) и окончательная выборка их не учитывает.

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

Я пробовал добавить немного "эвристики", изменяя сам алгоритм сортировки (сортируя не лексиграфически, а например, по числу единиц или по максимальному числу последовательных единиц), но ничего не вышло.

________

Итак, задачка автоматизации выборки из матрицы nxm максимального квадрата из единиц на самом деле не такая простая, как показалось на первый взгляд

Программа сахар'а работает для очень маленьких матриц, не более 50 строк и столбцов.
Для матриц большего размера уже ничего не получается, программа начинает врать, выделяет квадратик 3х3 там, где уже при беглом взгляде на матрицу виден квадрат 6х6.
Ну и работа у меня опять встала - нечем проверять матрицы на содержание в них квадратов из единиц.

Поэтому снова прошу всех принять участие в решении этой отнюдь не простенькой задачки.

Ну, мне хотя бы для матриц 150 строк х 50 столбцов сделать программу, чтобы она правильно работала. Я понимаю, что для очень больших матриц задача становится вообще нерешаемой (слишком много вариантов для перебора). Надо придумывать какой-то оригинальный алгоритм, чтобы преодолеть экспоненциальный взрыв.

[Nataly-Mak]

Приведу пример небольшой матрицы 28х28, в ней я сделала выборку квадрата 11х11 вручную. Программа выделяет из этой матрицы квадрат 10х10.
Получается, что даже в маленьких матрицах программа делает неверную выборку, то есть выделяет не максимальный квадрат.

В матрице звёздочками помечены единички, вошедшие в выбранный квадрат 11х11. В исходной матрице уже имеется 7 строк и 7 столбцов, полностью состоящих из единиц (так задано при построении матрицы).

(Оффтоп)

1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1
1* 1* 1* 1* 1* 1* 1* 1 0 1* 1* 1 1* 0 0 0 0 0 0 0 1* 0 1 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0
1 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1
1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0
1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0
1* 1* 1* 1* 1* 1* 1* 1 1 1* 1* 1 1* 1 1 1 1 1 1 1 1* 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
1* 1* 1* 1* 1* 1* 1* 0 0 1* 1* 0 1* 1 0 1 1 0 0 0 1* 1 0 1 0 1 0 0
1* 1* 1* 1* 1* 1* 1* 0 1 1* 1* 0 1* 0 1 1 1 1 0 0 1* 0 0 1 1 0 0 0
1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0
1* 1* 1* 1* 1* 1* 1* 1 0 1* 1* 1 1* 1 1 0 0 1 1 1 1* 0 1 1 1 1 0 1

[Nataly-Mak]

Существенное замечание.

Поскольку мне надо найти квадрат 13х13, размер выделяемого квадрата нам известен. Это, по-моему, намного облегчает решение задачи: выделять надо не максимальный квадрат, а квадрат заданного размера (собственно, я и говорила о выделении квадрата 13х13 в самом первом посте).

Алгоритм примерно такой представляется возможным реализовать:

1 этап. Считаем в исходной матрице единички в каждой строке и оставляем только те строки, в которых количество единичек не меньше 13. Сохраняем матрицу из полученных строк.
2 этап. То же самое проделываем в столбцах полученной новой матрицы.

В результате выполнения этих пунктов получаем некоторую новую матрицу размером mxn. Если количество строк и/или столбцов в этой матрице меньше 13, то искать в ней нечего - квадрата 13х13 из единичек в ней точно не будет.

В противном случае надо придумать, как завершить выборку квадрата из этой новой матрицы.

Да, забыла сказать: если на первом этапе получится матрица, в которой меньше 13 строк, то уже всё заканчивается, в этой матрице нечего искать.

[maxal]

Nataly-Mak в сообщении #364068 писал(а):

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

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

[Nataly-Mak]

Да, этот поиск собственно и будет завершающий этап предложенного мной алгоритма.
А многие матрицы будут отсеиваться уже на первых двух этапах. Проверять придётся небольшое количество потенциальных матриц.

[Nataly-Mak]

Уже есть одно решение задачи - программа участника EtCetera.

Мы сейчас работаем, я строю матрицы, а он их проверяет на предмет выделения квадрата 13х13 из единиц.
Пока, увы, максимальные квадраты 12х12 только получаются.

Для всех, кто заинтересовался задачей и ещё заинтересуется, предлагаю 5 матриц из нулей и единиц.

Как сообщил EtCetera, в его программе реализован алгоритм ветвей и границ.

[Nataly-Mak]

Решение задачи найдено, квадрат 13х13 выделен по программе EtCetera из матрицы 45х83 (матрица №10 в выложенном архиве с матрицами).

EtCetera
спасибо за помощь.

Пока компьютер трудился над составлением матриц, я думала над алгоритмом выделения квадрата из матрицы. Как мне кажется, тот алгоритм, которым пользуюсь при ручном выделении квадрата, совсем несложно реализовать. Наверное, это и есть алгоритм ветвей и границ.

Будем выделять квадрат заданного размера $n$. В решаемой задаче мне надо было выделить квадрат для n = 13.
Известно, что в исходной матрице есть 7 строк и 7 столбцов полностью состоящие из единиц. Удалим эти строки и столбцы из матрицы. В полученной матрице надо выделять квадрат 6х6. Далее удалим из матрицы все строки и столбцы, содержащие меньше 6 единиц. Теперь матрица готова для выделения квадрата. Подготовительные процедуры очень простые.

Рассмотрим теперь первую строку матрицы. Пусть в ней имеется $m$ единичек, m>=6; любая комбинация из 6 единичек может войти в искомый квадрат, значит, надо рассмотреть все комбинации, то есть все сочетания из $m$ по 6. Надо перебрать все эти варианты. Выбираем первую комбинацию из 6 единичек. Для всех следующих строк проверяем элементы, расположенные в соответствующих столбцах. Вводим переменную для счёта строк, в которых в соответствующих столбцах расположены единички. Проверяем последовательно каждую строку, как только переменная для счёта строк приняла значение 6, нужный квадрат найден. Если проверили все строки до конца матрицы и значение переменной меньше 6, значит, для данной комбинации единиц в первой строке квадрат не найден. Точно так же проверяем все остальные комбинации по 6 единиц в первой строке.
Завершив проверку всех комбинаций первой строки, переходим ко второй строке. Теперь будем проверять для каждой комбинации из 6 единиц во второй строке все следующие строки, начиная с третьей. Проверку прекращаем, как только в матрице остались 5 непроверенных строк.

Вот такая реализация алгоритма мне представляется. Программу пока не писала, можно попробовать.

Сейчас строю примитивные квадраты 7-го порядка из смитов, выделяю квадраты 7х7 из матриц вручную, это небольшие квадраты, поэтому справляюсь без программы. После удаления 4 готовых строк и 4 готовых столбцов надо выделить всего квадрат 3х3.

[Nataly-Mak]

Ещё одна задачка, она тоже связана с построением примитивного квадрата 13х13. Один квадрат я построила, но в нём есть недостаток: два числа повторились.
Теперь пытаюсь построить ещё один примитивный квадрат - без повторения чисел.

Это примитивный прямоугольник 13х10 (13 строк, 10 столбцов):

823 3203 5003 5623 6793 9209 11399 37123 192979 305849
1237 3617 5417 6037 7207 9623 11813 37537 193393 306263
5857 8237 10037 10657 11827 14243 16433 42157 198013 310883
7753 10133 11933 12553 13723 16139 18329 44053 199909 312779
8713 11093 12893 13513 14683 17099 19289 45013 200869 313739
12241 14621 16421 17041 18211 20627 22817 48541 204397 317267
13627 16007 17807 18427 19597 22013 24203 49927 205783 318653
17203 19583 21383 22003 23173 25589 27779 53503 209359 322229
30931 33311 35111 35731 36901 39317 41507 67231 223087 335957
36313 38693 40493 41113 42283 44699 46889 72613 228469 341339
59581 61961 63761 64381 65551 67967 70157 95881 251737 364607
67273 69653 71453 72073 73243 75659 77849 103573 259429 372299
207877 210257 212057 212677 213847 216263 218453 244177 400033 512903

Он получен в процессе поиска примитивного квадрата 13х13. В нём все числа простые и различные.
Требуется достроить этот прямоугольник до примитивного квадрата 13х13, то есть надо достроить всего три столбца.
Задача несложная, но решить её не могу по техническим причинам: язык, на котором я пишу программы, имеет очень ограниченную память, максимальный массив он берёт из 16000 чисел. Для решения предложенной задачи этого очень мало.

Переформулирую задачу.
Имеем последовательность из 13 простых чисел:

305849, 306263, 310883, 312779, 313739, 317267, 318653, 322229, 335957, 341339, 364607, 372299, 512903

Разности между соседними числами этой последовательности:

414, 4620, 1896, 960, 3528, 1386, 3576, 13728, 5382, 23268, 7692, 140604

Требуется найти три последовательности из простых чисел такой же длины с такими же разностями между соседними членами. Числа в новых последовательностях должны быть больше первого числа заданной последовательности - 305849. Кроме того, во всех четырёх последовательностях числа должны быть различные.

Решая задачу со своими маленькими массивами простых чисел, я получила только одну последовательность всего из 11 членов:

683699, 684113, 688733, 690629, 691589, 695117, 696503, 700079, 713807, 719189, 742457

Тоже неплохо, получила ещё один примитивный квадрат 11х11. Но мне надо получить квадрат 13х13. А для этого надо найти три последовательности длины 13.

Буду очень благодарна за помощь в решении задачи.

[Nataly-Mak]

В теме "Магические квадраты" опубликовала другой примитивный прямоугольник 13х12, в котором надо достроить всего один столбец.