|
Название: Уникальные перестановки Отправлено: square от Июнь 05, 2012, 03:41:47 Вот эти 12 перестановок из чисел 1,2,3,4 назовём уникальными в таком смысле: ни в каких двух перестановках в одинаковых позициях нет одинаковой пары чисел:
Код: 1 2 3 4 Задача такая: составить 56 уникальных перестановок из чисел 1,2,3,4,5,6,7,8 (ещё 72 перестановки из чисел 1,2,3,...,9 и 240 перестановок из чисел 1,2,3,...,16). Вот начала писать перестановки из чисел 1,2,...,8. Первые семь штук: Код: 1,2,3,4,5,6,7,8 Дальше не знаю, как писать. По-хорошему, конечно, надо программку написать. Но для 16 чисел, наверное, очень долго работать будет :( Слишком много перестановок. Может быть, тут какая-то хорошая есть закономерность, или хорошая оптимизирующая тупой перебор идея. Помогите, пожалуйста :help: Название: Re: Уникальные перестановки Отправлено: moonlight от Июнь 05, 2012, 09:27:47 Название: Re: Уникальные перестановки Отправлено: square от Июнь 05, 2012, 09:48:07 Спасибо, но мало :)
Я сама начала программку писать, но что-то со скрипом она у меня идёт. Никак не могу совладать со всеми проверками всех пар чисел во всех перестановках. Да, начать нужно с приведённой выше группы уникальных перестановок, начинающихся с числа 1, следующие перестановки уже с этими сравнивать. Если вы посмотрите на пример с числами 1,2,3,4, то увидите, что есть ровно 4 группы перестановок, первая начинается с числа 1, вторая - с числа 2 и т.д., в каждой группе 3 перестановки, всего 12. Думаю, что для чисел 1,2, ..., 8 будет полная аналогия. В каждой группе будет 7 перестановок, всего 8 групп. Я начала искать вторую группу - перестановки, начинающиеся с числа 2. Пока предположительно у меня такая перестановка получилась с числа 2: 2,1,8,7,6,5,4,3 Вроде ни с какой перестановкой первой группы не пересекается (в смысле определения). Но это пока предположительно. Программу ещё не дописала. И пишу её только для второй группы. Хоть бы эту группу составить. Там, может быть, какие-то закономерности проявятся. Если у меня программа с числа 2 составит перестановки норамально, 7 штук, тогда можно будет проанализировть их. Название: Re: Уникальные перестановки Отправлено: square от Июнь 05, 2012, 10:21:12 Вот, например, такая вторая группа у меня получилась (с числа 2 начинаются перестановки):
Код: 2,1,8,7,6,5,4,3 Кто видит тут какие-то закономерности? Чтобы можно было следующую группу написать, с числа 3 начинаются перестановки. Вот интересно: если все 56 перестановок найти, они, наверное, чётко получатся. Смотрю в приведённых выше перестановках много всяких. Но вот если до 56 перестановок дойти, наверное многие перестановки не впишутся, будут пересекаться. И останутся действительно уникальные. И будет их, вероятно, ровно 56. Но это пока предположения. Ничего определённого не знаю сама. Можно на перестановках для чисел 1,2,3,4 проверить. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 07, 2012, 21:46:09 Название: Re: Уникальные перестановки Отправлено: square от Июнь 08, 2012, 01:34:43 Здорово!
Правда, на уникальность не проверила, только бегло просмотрела визуально. А как искали? Программу писали? Я как раз собиралась сообщить, что задачу помогли решить на форуме dxdy.ru http://dxdy.ru/topic59550.html Всё оказалось очень просто. Надо взять полный комплект попарно ортогональных латинских квадратов и выписать из этих квадратов столбцы. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 08, 2012, 16:48:27 Здорово! Правда, на уникальность не проверила, только бегло просмотрела визуально. А как искали? Программу писали? Я как раз собиралась сообщить, что задачу помогли решить на форуме dxdy.ru http://dxdy.ru/topic59550.html Всё оказалось очень просто. Надо взять полный комплект попарно ортогональных латинских квадратов и выписать из этих квадратов столбцы. Я немного изменил поиск. Искал не 56 перестановок, а 8 наборов по 7 чисел в каждой (в каждом наборе отсутствуют разные числа). При этом чтобы в каждой паре наборов не было одинаковой пары рядомстоящих чисел (одинаковоориентированых). А дальше вся комбинация получается путём сдвига этих наборов и приписывания слева недостающее число Название: Re: Уникальные перестановки Отправлено: square от Июнь 08, 2012, 20:43:33 Отличное решение!
А вы смотрели по ссылке, как просто, оказывается, находятся эти уникальные перестановки? Просто выписываются столбцы из полного комплекта попарно ортогональных латинских квадратов. Кстати, вы не хотите в международном конкурсе программистов поучаствовать? http://infinitesearchspace.dyndns.org/monosquares Это ведь задачка у меня вспомогательная была для решения конкурсной задачи. Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 13:33:32 zhekas
а из чисел 1,2,3,4,5,6 есть комплект из 30 уникальных перестановок? Весьма интересно! Если у вас есть программа, прикиньте, пожалуйста. Ну, две группы по 5 штук написать просто. Например, такие: Код: 1 2 3 4 5 6 Думаю, что первую группу изменять не стоит, а вторую, конечно, можно изменить. Впрочем, программа сама разберётся. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 09, 2012, 16:49:47 zhekas а из чисел 1,2,3,4,5,6 есть комплект из 30 уникальных перестановок? Весьма интересно! Если у вас есть программа, прикиньте, пожалуйста. Ну, две группы по 5 штук написать просто. Например, такие: Код: 1 2 3 4 5 6 Думаю, что первую группу изменять не стоит, а вторую, конечно, можно изменить. Впрочем, программа сама разберётся. 2 3 4 5 6 1 4 6 5 3 1 5 2 6 4 1 6 3 2 5 1 2 4 3 6 1 3 5 4 2 Относительно первой группы, остальные группы единственны с точностью до сдвига Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 17:38:41 Если я правильно поняла, первая группа будет такая:
Код: 1 1 1 1 1 2 Если читать перестановки как у вас написано, то они получаются из 5 чисел. Как писать следующую группу, не соображу. Написала так: Код: 2 2 2 2 2 3 Не получились уникальные, пара (4,3) совпадает. Думаю дальше... Если так, как вы написали, то будет 6 групп по 6 штук... Да? Наверное, так...То есть к вашей группе надо приписать ещё 5 групп. Вторая группа такая будет? Код: 3 4 5 6 2 Кажется, нет пересечений с первой группой. И третья группа вроде получилась :) Неужели и из чисел 1,2,3,...,10 тоже существуют уникальные перестановки? Вот дела... Не попробуте для этого случая? Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 09, 2012, 17:48:17 Если я правильно поняла, первая группа будет такая: Код: 1 1 1 1 1 2 Как писать следующую группу, не соображу. Написала так: Код: 2 2 2 2 2 3 Первая группа составляется из первого набора чисел:2 3 4 5 6 путём их сдвига и прибавления слева недостающего числа 1 1 2 3 4 5 6 1 3 4 5 6 2 1 4 5 6 2 3 1 5 6 2 3 4 1 6 2 3 4 5 Вторая группа из второго набора:1 4 6 5 3 путём сдвига и приставления слева недостающего числа 2 2 1 4 6 5 3 2 4 6 5 3 1 2 6 5 3 1 4 2 5 3 1 4 6 2 3 1 4 6 5 И так далее. В итоге получается Показать скрытый текст Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 18:12:31 А-а-а...поняла.
Спасибо большое! Классная закономерность получается. А с числами 1,2,3,...,10 попробуете? Жутко интересно. В этом случает такая же будет схема составления? Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 09, 2012, 18:21:15 для n=10 программа справляется за 5часов. А записать я не записал. Так что скоро не ждите. Время растёт экспоненциально
Для n=9 программа отработала меньше секунды Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 18:27:15 Ну, я подожду :) У меня времени много.
Спасибо вам огромное. Весьма интересные получаются перестановки! Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 19:14:43 Увы! Перестановки для чисел 1,2,3,4,5,6 не уникальные.
Начала строить квадрат 36х36 и он не получился. Тогда внимательно посмотрела перестановки. Пара (2,4) повторяется: 1 2 3 4 5 6 3 2 6 4 1 5 Существуют ли они вообще для этих чисел? Вот в чём вопрос :) Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 09, 2012, 21:14:41 да, я немного не правильно понял задачу, Я думал только рядомстоящие числа сравнивать.
Кстати, для n=6 простой перебор показывает, что нет такой комбинации. Так что, вполне возможно, что между "уникальными" комбинациями и латинскими квадратами есть однозначная взаимосвязь Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 21:33:06 Эх, значит, всё-таки не существует. Жаль!
Впрочем, ожидаемый результат. А что если попробовать разрешить повторение чисел в перестановках? То есть это уже не перестановки будут в обычном понимании, а просто некоторые комбинации из 6 чисел. Но требование к повторениям в одинаковых позициях остаётся то же самое. Тут уже, может быть, надо сочинять не 30, а 36 комбинаций. Скорее всего. Но можно попробовать сначала 30 сочинить. Попробуйте, пожалуйста такой вариант. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 09, 2012, 21:59:19 Для 30 например так
Показать скрытый текст Название: Re: Уникальные перестановки Отправлено: square от Июнь 09, 2012, 22:12:13 Неповторяемость гарантирована?
Тогда надо ещё 6 штук, из 30 у меня квадрат 36х36 не построится. В случае 30 перестановок я добавляла ещё такие комбинации: 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 В данном случае с повторением чисел в строках эти комбинации добавлять уже нельзя, нарушится условие непересекаемости комбинаций. Может, добавятся ещё 6 штучек комбинаций? :) Я просмотрела 30 штук комбинаций, вроде нет пересечений (визуально не замечено), всё отлично пока. Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 06:45:51 Zhekas
я написала программку для добавления к вашему замечательному набору комбинаций 31-ой комбинации. Вот такая у меня получилась комбинация по программе: Код: 1 1 6 6 6 5 Вроде правильно. Да? Очень медленно я двигаюсь. Сейчас буду писать программку для добавления следующей комбинации. По-хорошему, это должна быть одна программа, но у меня не получается, в циклах запуталась. Поэтому пишу вот так примитивно, по одному шагу. Буду благодарна, если вы поможете найти оставшиеся 5 комбинаций. Пока я пишу свои примитивные программки, вы можете за одну минуту найти эти комбинации по своей программе. Думаю, что все 36 комбинаций можно найти. А мне ещё надо такую же задачу решить для n = 10, 12, 14, 15, 18, 20, 21. За 30 комбинаций спасибо большое. Всё же мне не с нуля пришлось начинать поиск. Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 07:20:45 Эх! Приехали! :)
32-ая комбинация у меня не формируется, программа выдаёт только два числа в этой комбинации, третье число добавить уже невозможно. Значит, надо изменять первые 30 комбинаций, они найдены не совсем удачно, к ним можно добавить только одну комбинацию. Если я не ошибаюсь в программе. Zhekas помогите, пожалуйста. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 10, 2012, 09:06:34 со вчера я запустил программу на поиск 36, Пока выолняется.
Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 09:10:55 А-а-а...
Отлично! Очень интересно, сколько максимально будет таких комбинаций в комплекте. Хотелось бы, чтобы было 36, но если вдруг меньше получится (от 32 до 35), мне и это сгодится. Вы, пожалуйста, сохраните как-нибудь самый большой комплект, чтобы он не был потерян. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 10, 2012, 10:05:14 Она не ищет максимум. Она ищет либо 36 либо её отсутствие
Предлагаю вам запустить мою программу у себя. В ней у каждого набора уже записаны первые 2 числа и поиск начинается с третьего. Чтобы можно было искать несколько вариантов сразу я сделал 3 число первой строки аргументом программы. Для лучшего отслеживания хода программы, на вывод подаются изменения первой строки. Запускать в cmd: programa.exe 6 (или 5,4,3,2,1) У меня идёт с начала. Так что вы начинайте с конца отправил по почте Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 10:13:37 Идея хорошая.
Но надо сначала точно определиться, что искать. Мы выяснили, что набор из 31 комбинации точно существует. Есть подозрение, что из 32 комбинаций набора уже нет. Поэтому предлагаю сначала сделать программу так, чтобы она искала набор из 32 комбинаций. Это будет быстрее, чем для 36 комбинаций. К тому же, если программа не найдёт набор из 32 комбинаций, дальше и искать нечего. Я готова запустить программу у себя. Но сделайте её, пожалуйста, на поиск 32 комбинаций. Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 10:16:23 Программа пришла.
Я могу попробовать, как она будет работать у меня. Так что мне задать в качестве параметра? 6? Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 10:34:52 У вас программа-то какая?
Она у меня не запускается. Выдаётся сообщение, что она не является exe-программой. И не выглядит она у меня, как Приложение (exe-программа). Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 10, 2012, 12:54:17 Попробуйте следующую программу. Она ещё выводит максимум строк на текущий момент
отослал по почте Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 13:11:21 Программу получила и попробовала. Спасибо.
Первые 30 комбинаций она находит мгновенно, а потом надолго задумывается. Даже с 31-ой комбинацией сложности. А у вас хоть раз находила 31 комбинацию? А 32? Я ввела параметр 6. Первые два числа 1,1. То есть у меня программа начинает с комбинации 1,1,6,1,1 и пошла искать дальше. Как я понимаю, программа к найденным 30 комбинациям ищет добавление. Вот не ожидала, что тут такой упёртый будет перебор. Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 14:33:31 Zhekas
я что-то пока не поняла логику программы. Вот запустила я программу с параметром 6. Она первые 30 комбинаций сразу нашла. Что она делает дальше? Целый час уже работает и всё на одном месте. Неужели она так долго ищет 31-ую комбинацию? Что-то тут не так... Тут перебор-то вроде не очень большой. Я делала программку для добавления только одной комбинации. Беру набор из M комбинаций и по программе пытаюсь добавить (M+1)-ую комбинацию. Так программа моментально это определяет: можно добавить или нельзя. А ваша программа целый час думала над 31-ой комбинацией и так ничего и не придумала. Нет ли у вас где-то ошибки? Может, где-то в циклах ошиблись, не туда сделали переход. Это часто у меня бывает. И тогда программа просто зацикливается. Короче, я пока прервала программу. Тут ничего не светит, не только 32-ой, но даже и 31-комбинации не находит программа. Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 14:49:03 Вот смотрите пример.
Запускаю вашу программу с параметром 1. Она мгновенно выдаёт 30 комбинаций: Pervaia stroka: 1 1 1 1 1 1 Maximum=30 1 1 1 1 1 1 1 2 2 2 2 2 1 3 3 3 3 3 1 4 4 4 4 4 1 5 5 5 5 5 1 6 6 6 6 6 2 1 2 3 4 5 2 2 1 4 3 6 2 3 4 5 6 1 2 4 3 6 5 2 2 5 6 1 2 3 2 6 5 2 1 4 3 1 3 5 2 4 3 2 4 6 1 3 3 3 5 1 4 6 3 4 6 2 3 5 3 5 1 3 6 2 3 6 2 4 5 1 4 1 4 2 5 6 4 2 3 1 6 5 4 3 6 4 1 2 4 4 5 3 2 1 4 5 2 6 3 4 4 6 1 5 4 3 5 1 5 4 6 3 5 2 6 3 5 4 5 3 1 6 2 5 5 4 2 5 1 6 5 5 3 2 4 1 5 6 4 1 3 2 Дальше беру эти 30 комбинаций и скармливаю своей программе, она моментально отрабатывает и говорит, что добавить 31-ую комбинацию тут нельзя. Всё! Над чем думает ваша программа целый час? А может, она тоже уже всё обдумала и решила, но тогда как-то должно это показаться в окне программы, что она закончила работу. А то впечатление такое, что она всё работает, работает... Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 10, 2012, 15:05:28 Я поставил значение max=29. Программа перебирает все варианты с нуля. Как только строк стало 30 она присвоила max=30 и вывела эти строки. Дальше, следующую строку она не нашла и стала перебирать следующие комбинации. А так как max=30 то новые комбинации из 30 строк она не выводит. А будет выводить теперь только если появится 31 строка и больше
Название: Re: Уникальные перестановки Отправлено: square от Июнь 10, 2012, 15:41:12 А, теперь понятно.
То есть она перебирает дальше. Ну, какой-нибудь индикатор вывели бы, чтобы видеть, что она перебирает. А так ничего не понятно, что она там делает, или, может, просто висит. Получается, что мне с 31-ой комбинацией в самом первом вашем наборе крупно повезло :) Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 04:58:22 Zhekas
оставим пока комбинации из чисел 1,2,3,4,5,6. Что-то программа у меня не выдала ни одного набора даже из 31 комбинации. Подумаем о комбинициях из чисел 1,2,3,...,10. Я посмотрела на набор из 30 комбинаций, полученный по вашей программе (чуть выше он выложен) с первой строкой 1,1,1,1,1,1. По-моему, обалденная закономерность! Ровно 5 групп по 6 штук в каждой группе, первая группа начинается с числа 1, вторая - с числа 2 и т.д. У меня есть предположение, что аналогичную группу комбинаций можно получить из чисел 1,2,3,...,10. Будет 9 групп по 10 штук в каждой, первая группа будет начинаться с числа 1, вторая - с числа 2. и т.д. Ну, например, вот первая группа, пишу по аналогии с первой группой комбинаций из чисел 1,2,3,4,5,6: Код: 1 1 1 1 1 1 1 1 1 1 Если вам не трудно, проверьте, пожалуйста, мою гипотезу. Получится ли набор из 90 комбинаций? Очень интересно! У вас программа-то уже готовая, несложно проверить. Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 05:51:53 Пытаюсь составить вторую группу комбинаций по аналогии, пока вот что получилось:
Код: 2 1 2 3 4 5 6 7 8 9 Кто заполнит группу? Спасибо! (авансом :)) Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 10:41:54 Написала программку для добавления к имеющемуся набору по одной комбинации. Удалось получить такой набор комбинаций:
Код: 1 1 1 1 1 1 1 1 1 1 Увы, плохо! Во второй группе (комбинации начинаются с числа 2) не удалось добавить ещё одну комбинацию, их должно быть 10 штук. Всё неправильно тогда. Надо писать программу полного перебора. Почти уверена, что аналогия с комбинациями из чисел 1,2,3,4,5,6 имеет место. И помощник мой пропал :( :help: Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 10:58:40 С шестёрками всё глухо. Почти за сутки первая строка не изменила ни одного числа. А для того чтобы сделать полный перебор спараметром нужно 6^3 комбинаций первой строки.
Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 11:17:32 Бросьте шестёрки!
Посмотрите, пожалуйста, на задачку про числа 1,2,3,...,10. Мне кажется, что набор из 90 комбинаций из этих чисел составится мгновенно, так же, как составился набор из 30 комбинаций чисел 1,2,3,4,5,6. У вас программа, как я понимаю, есть для n=10, вы писали её для поиска уникальных перестановок. Надо теперь только разрешить повторение чисел в комбинациях. Если будет долго работать программа, шлите её мне, я покручу. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 11:42:04 а толку крутить. Она на 20-й строке уже тупит.
Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 11:44:26 А первые 19 комбинаций покажите, пожалуйста.
Я вот по своей программке тоже пыталась вторую группу сделать, 9 комбинаций в ней получилось, а десятой нету! Не добавляется. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 11:48:32 1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 3 3 3 1 4 4 4 4 4 4 4 4 4 1 5 5 5 5 5 5 5 5 5 1 6 6 6 6 6 6 6 6 6 1 7 7 7 7 7 7 7 7 7 1 8 8 8 8 8 8 8 8 8 1 9 9 9 9 9 9 9 9 9 1 10 10 10 10 10 10 10 10 10 2 1 2 3 4 5 6 7 8 9 2 2 1 4 3 6 5 8 7 10 2 3 4 1 2 7 8 5 9 6 2 4 3 2 1 8 7 6 10 5 2 5 6 7 8 1 2 9 3 4 2 6 5 8 7 2 1 10 4 3 2 7 8 5 6 9 10 3 1 2 2 8 7 9 10 3 4 2 5 1 2 9 10 6 5 4 3 1 2 7 Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 11:58:30 Нет, у меня не такая вторая группа получилась, а первая такая же.
Но, чёрт подери, должна быть аналогия! Может, как-нибудь без программы в эту аналогию проникнуть? Всё равно пришлите программу, попробую покрутить. Только, пожалуйста, сделайте вывод на экран чего-нибудь перебираемого, чтобы можно было видеть динамику работы программы. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 12:01:16 Для аналогии. Вот вам для n=8
Показать скрытый текст Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 12:04:14 O!!!
Спасибо. Буду думать. Вот, значит, для n=8 быстро получилось. А для n=10 тупит. А для n=9 что имеем? Для аналогии пригодится :) Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 12:09:24 для 9 также тупит на 18 строке
Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 12:13:18 Вот ведь!
Ладно, пожалуйста, пришлите мне программу для n=10. Попробую покрутить, авось получится. А сама тем временем буду думать над аналогией. Приглашаю всех подумать вместе со мной :) Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 14:07:51 Хорошая головоломка! Я уже всю голову сломала :)
(http://www.natalimak1.narod.ru/monohr13.jpg) Числа во второй группе (комбинации, начинающиеся с числа 2) я могла расставить неправильно, можно изменить. Это для аналогии n=8: Код: 1 1 1 1 1 1 1 1 Неужели аналогия не пройдёт? :( Да, напомню: должны получиться непересекающиеся комбинации. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 11, 2012, 14:35:54 Есть задумка попробовать реализовать переход от n до n+1 следующим образом. Взять вторую группу из n=8. В ней прослеживаются две главные диагонали. Это диагональ едениц и диагональ восьмерок.
Взять например диагональ едениц и относительно её раздвинуть треугольники прилегающие к этой диагонали на одну позицию вправо для верхнего треугольника и на одну позицию вниз для нижнего треугольника. При этом числа в треугольниках увеличить на еденицу. А затем искать числа н позициях около этой диагонали Название: Re: Уникальные перестановки Отправлено: square от Июнь 11, 2012, 14:39:46 Хорошая задумка! Попробуйте.
У меня уже голова лопается. Вроде всё должно быть аналогично, но не получается никак. И для n=6 есть, и для n=8 есть. Ну не может быть, чтобы для n=10 не было! Название: Re: Уникальные перестановки Отправлено: square от Июнь 13, 2012, 04:41:38 Zhekas
ну что там с десятками? Тоже глухо? :) А что дадут комбинации из чисел 1,2,3,...,12? Может, тут повезёт... Или тоже сразу программа будет тупить? Задачка оказалась крепким орешком :) Кстати, вы когда крутили программу для шестёрок, отслеживали появление 32 комбинаций? Мне бы и 32 комбинации очень сгодились! Тот вариант, который вы мне прислали, как я понимаю, это отслеживает. То есть он выдаст и 31 комбинацию, если будет найдено 31 штук, и 32 комбинации тоже выдаст. Правильно понимаю? Я крутила несколько часов с параметром 6. Не выдалось даже ни одного набора из 31 комбинации, так и остался максимум=30. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 13, 2012, 06:13:36 с 12 тоже глухо. Полный перебор и, соответственно, експоненциальный рост времени неумолимо приводят к ожидаемому результату (отсутствию резултата.)
Название: Re: Уникальные перестановки Отправлено: square от Июнь 13, 2012, 08:39:39 Да-а-а... Вот ситуация...
А вот такая идея: воспользоваться случайной генерацией комбинаций. Берём, например, несколько первых комбинаций, скажем, таких: 1 1 1 1 1 1 1 2 2 2 2 2 1 3 3 3 3 3 1 4 4 4 4 4 1 5 5 5 5 5 1 6 6 6 6 6 Дальше включаем рэндом, генерируем следующую комбинацию, проверяем, если годится, записываем в набор, если не годится, отбрасываем; генерируем следующую комбинацию и т. д. Можно вообще начать с одной комбинации, любой. Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 12:50:56 Да-а-а... Вот ситуация... А вот такая идея: воспользоваться случайной генерацией комбинаций. Берём, например, несколько первых комбинаций, скажем, таких: 1 1 1 1 1 1 1 2 2 2 2 2 1 3 3 3 3 3 1 4 4 4 4 4 1 5 5 5 5 5 1 6 6 6 6 6 Дальше включаем рэндом, генерируем следующую комбинацию, проверяем, если годится, записываем в набор, если не годится, отбрасываем; генерируем следующую комбинацию и т. д. Можно вообще начать с одной комбинации, любой. 111111 212345 313624 414263 515432 616253 122222 223456 324135 425314 526543 621364 133333 234561 335246 436425 531654 632415 144444 245612 346351 441536 542165 643526 155555 256123 351462 452641 553216 654631 166666 261234 362513 463152 564321 665142 зы: а что такое рэндом? ??? :-\ :yesgirl: Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 13:01:21 square, а почему вы решили, что для n=8 всего 56 возможных перестановок на указанных условиях?
зы: т.е., может оно и так, но интересно - почему Вы так считаете? Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 13:13:02 С 36 комбинациями из чисел 1,2,3,4,5,6 у вас здорово получилось!
А мы с zhekas бились, бились, так ничего и не нашли. А они у вас точно непересекающиеся? Я ещё не проверила. Как вы их нашли? Расскажите, пожалуйста, интересно :) Насчёт уникальных перестановок для n=8 всё просто: существует ровно 7 попарно ортогональных ЛК 8-го порядка. Перестановки эти из этих самых квадратов берутся, вот и будет их ровно 56. А вот непересекающихся комбинаций для n=8 получается ровно 64, zhekas их нашёл. Ах, да, про рэндом не ответила. Ну, это я на форуме dxdy.ru подцепила, там один товарищ так написал. Вообще-то это функция такая - случайная величина :) А с десяточками вы тоже можете выдать непересекающиеся комбинации? Мне надо мно-о-о-г-о :) Не меньше 90. Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 13:18:59 я вообще не очень понимаю предмета обсуждения, хотя мне и было интересно повозиться. например, полагаю, что существует несколько (много) различных вариантов сложения 36 из 6. все они уникальны, но нельзя заменить в одном решениии никакое из звеньев на звено из другого решения.
что касается проверки: там первые две значащие цифры вообще не нуждаются в проверке как между собой, так и в сочетании с иными, и это очевидно. в остальном проверка легко осуществляется по принципу создания, например. проверяем 3 и 4 значащие цифры. у нас в первом столбце 11, 2-12, 3-13, 4-14,5-15,6-16. аналогично везде и все вплоть до 66. Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 13:23:37 А что именно вы не понимаете? Есть задача:
а) для уникальных перестановок; б) для непересекающихся комбинаций. Вот и решаем. У меня, например, это плохо получается :) Ну, с уникальными перестановками кое-как разобралась. А вот с непересекающимися комбинациями никак не разберусь. Из "десяточек" (т.е. из чисел 1,2,3,...10) нашла всего 19 непересекающихся комбинаций. И дальше ни тпру, ни ну :) Так значит, говорите, что "шестёрки" у вас не пересекаются? Сейчас проверим... Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 13:25:13 другое дело - как доказать, что 36 - максимально возможное решение? вариант с квадратами предлагает способ решения для некоторых "квадратно" устроенных n. доказательства максимальности я пока не встречал. имхо, понимая природу "максимальности" можно вывести универсальную формулу для определения максимального количества вариантов перестановок.
другой интересный аспект (полагаю тесносвязаный с первым) - это возможное количество вариантов перестановок 36 из 6. Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 13:30:15 Я ушла проверять ваше решение :)
Да, вы ничего не сказали о "десяточках". Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 13:32:07 Так значит, говорите, что "шестёрки" у вас не пересекаются? Сейчас проверим... для простоты считайте не строки, а столбцы. все столбцы устроены по принципу очередности. т.о., если любая пара чисел проверена по своим местам (я показывал на примере 11-16), то нет смысла проверять остальные пять. Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 13:53:54 Комбинации у вас пересекаются!
Вот так их выписала: Код: 1 1 1 1 1 1 А теперь смотрите: в строках 7-ой и 23-ей (считаем сверху) повторяется пара чисел (2,4) - третья и пятая позиции в строках. Вы, может, тоже сравниваете только рядом стоящие числа? Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 14:00:28 7: 2 и 4
23: 2 и 6 Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 14:03:22 7: 2 и 4 23: 2 и 6 нет, вы правы - неверно я посчитал строку, действительно повтор. я проверю, спасибо. Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 14:05:18 Не поняла...
Цитировать 111111 212345 313624 414263 515432 616253 122222 223456 324135 425314 526543 621364 133333 234561 335246 436425 531654 632415 144444 245612 346351 441536 542165 643526 155555 256123 351462 452641 553216 654631 166666 261234 362513 463152 564321 665142 7-ая комбинация: 212345 23-ья комбинация: 452641 Сравните числа в третьей и пятой позиции, и там, и там стоят числа 2,4. Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 14:10:05 Не поняла... Цитировать 111111 212345 313624 414263 515432 616253 122222 223456 324135 425314 526543 621364 133333 234561 335246 436425 531654 632415 144444 245612 346351 441536 542165 643526 155555 256123 351462 452641 553216 654631 166666 261234 362513 463152 564321 665142 7-ая комбинация: 212345 23-ья комбинация: 452641 Сравните числа в третьей и пятой позиции, и там, и там стоят числа 2,4. посмотрите уже до конца тогда, если не трудно Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 14:35:48 Визуально это трудно.
У меня есть программка, которая добавляет к исходному набору из n комбинаций (n+1)-ую комбинацию. Но это долго тоже проверять по одной комбинации. Общей программы у меня нет. А у вас разве нет программы? Вы вручную что ли составили эти комбинации? Далее, ещё есть один метод для проверки (которым я сразу и воспользовалась), но этот метод долго рассказывать. Для этого вам надо вникнуть в конкурсную задачу текущего международного конкурса программитстов (здесь тему открыла "Monochromatic squares"). В этом конкурсе приложена программа, которая проверяет правильность построенного на базе 36 комбинаций квадрата 36х36. Квадрат я строю по программе, сразу загоняю в неё набор из 36 комбинаций и квадрат готов. Потом загоняю его в программу проверки правильности и вижу, что там куча ошибок. Это значит, что исходный набор из 36 комбинаций неправильный. Вот для построения квадрата 36х36 мне и нужен базовый набор из 36 непересекающихся комбинаций. Мне удалось построить с помощью zhekas только набор из 31 комбинации. Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 14:48:32 нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают. но это говорит лишь о том, что я где-тоне верно сдвинул прокрутку.
подумаю на досуге, а пока работаю. зы: нет, программы у меня нет, а что такое программа? :D Название: Re: Уникальные перестановки Отправлено: square от Июнь 14, 2012, 15:08:00 нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают. И опять не поняла. Какие все шесть позиций совпадают? Ну, к примеру, вижу ещё одну совпадающую пару (4,6), но это в других комбинациях, хотя, да, в тех же позициях.Программа - это... код на каком-то языке программирования для исполнения этого кода машиной, то бишь компьютером :) Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 15:29:33 нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают. И опять не поняла. Какие все шесть позиций совпадают? Ну, к примеру, вижу ещё одну совпадающую пару (4,6), но это в других комбинациях, хотя, да, в тех же позициях.Программа - это... код на каком-то языке программирования для исполнения этого кода машиной, то бишь компьютером :) смотрите столбцы 2 и 4-й, позиции 3 и 5: они ВСЕ в указанных столбцах не совпадают, поскольку использовалась кольцевая прокрутка сверху-в-низ чисел от 1 до 6 (в каждом столбике каждого столбца). я покручу чуть позже Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 14, 2012, 15:37:56 т.е. следующим шагом я прокручу столбик 4 во всех столбцах по одной цифре сдвигая вниз или вверх для того, чтобы избежать указанных недочетов, и, если не будет противоречий с предыдущими столбиками, тогда аналогично 5 и 6 столбики.
ps^ а программкой мне служит EXCEL :peace: Название: Re: Уникальные перестановки Отправлено: square от Июнь 15, 2012, 15:48:52 Wesson
ну как, покрутили? Не получилось? А я вот сочинила 54 комбинации из 1,2,3,4,5,6 с пропусками чисел: Код: 1 2 5 6 4 4 Можно ли этот набор из 54 неполных комбинаций свести полным перебором к набору из 36 (или хотя бы из 32, 33, 34, 35) непересекающихся комбинаций? В комбинациях те числа, которые уже стоят на месте, пересечений не дают (искала комбинации по программе). zhekas не попробуете эту идею реализовать? У меня от 36-градусной жары уже совсем мозги расплавились :( Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 16, 2012, 08:59:15 Wesson не докрутил. просто времени не хватает пока, потом футбол и жара, конечно.. ну как, покрутили? Не получилось? на чем остановился. в моей расстановке чисел в шесть столбцов по шесть столбиков, первые 3 столбика в каждом столбце расставлены верно. во всяком случае, из этого исходим. тогда что неправильно в четвертой позиции в одном из столбцов. не правильно то, что в 5-ти последних столбцах в 5-й позиции должны стоять разные числа, т.е. все от 2 до 6. а у меня дублируются. расставить числа нужно с учетом того, что, если, к примеру, рассматривать число в 4-й позиции как число единиц к числу десятков, обозначенному в 3 позиции, то в любой связке должен получиться полный комплект. к примеру, в 1-м столбце позиции 3 и 4 образуют цифру 11. тогда в пяти следующих столбцах должны получиться цифры 12, 13, 14, 15 и 16. возможных комбинаций перестановок без повторения для 2, 3, 4, 5 и 6 всего 120. в переборе учавствуют и того меньше, т.к. например, для первых трех позиций 212 цифра 2 в четвертой позиции невозможна, поэтому в переборе не учавствует, и так все цифры, т.е. реально будет меньше 100 переборов. вот, теперь нужно перебрать, но лень. руками - точно лень, поэтому вяло думаю - как написать перебор в екселе (программки я не умею составлять). пока че-то вяло думается... если окажется, что нужный вариант существует и он будет найден (один из сотни для 5 чисел) тогда останется две позиции, потом одна. и нет необходимости сверять совпадения - их не будет по определению. тогда можно писАть программку для 10, 20 и 1000 чисел. а пока... пока :yesgirl: зы: если непонятно написАл - могу подробнее рассказать в скайпе, заходите. свои позывные сбросил к Вам в личку Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 16, 2012, 20:00:58 По методу Wesson все 6 групп по 6 столбцов (то есть 36 строк) не выходят. Максимум это 5 групп по 6 столбцов. (30 строк).
Для n=10 уже 5 групп тобишь 50 строк и перебор ещё идет Название: Re: Уникальные перестановки Отправлено: square от Июнь 16, 2012, 20:41:22 По методу Wesson все 6 групп по 6 столбцов (то есть 36 строк) не выходят. Максимум это 5 групп по 6 столбцов. (30 строк). Да, я тоже это подозревала. Не получится. А 30 комбинаций по вашей программе запросто получается. Мне даже удалось 31-ую найти. Цитировать Для n=10 уже 5 групп тобишь 50 строк и перебор ещё идет O-о-о!!!Это уже отлично. Ещё немного, ещё чуть-чуть :) Вы нашли больше половины. Мне надо от 83 и выше. Если будет 9 групп, то бишь 90 комбинаций, будет классно. В этих 50 комбинациях никакой закономерности не видно? Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 16, 2012, 22:48:37 для n=10 по методу Wesson не больше 50 строк
Название: Re: Уникальные перестановки Отправлено: square от Июнь 17, 2012, 00:43:56 А вот посмотрите, какой набор из 32 непересекающихся комбинаций из чисел 1,2,3,...,10 выложили на форуме dxdy.ru
Код: 3,3,7,3,10,3,9,6,4,3, Кажется, совершенно хаотично числа берутся. Правда? Никакой закономерности нету, я не вижу, во всяком случае. Попробовала добавить к этому набору ещё комбинации, добавляла по одной (не полный перебор!), удалось добавить всего 3 штуки, больше не добавляется. Конечно, если делать полный перебор, может быть, и больше удастся добавить. Название: Re: Уникальные перестановки Отправлено: square от Июнь 17, 2012, 05:00:11 Вычитала в статье...
Комбинации можно составлять другие, с пересечениями. Но пересечения разрешаются только для чисел 1 и 2. При этом во всех 4 пересекающихся позициях не могут стоять одинаковые числа - все 2 или все 1. Пример: Код: 1 1 2 2 3 6 Но в этом примере комбинации длины 6 (6 чисел в строке), а нам надо тогда составлять комбинации длины 12 (12 чисел в строке). И таких комбинаций тоже надо 36 штук. Возможно ли такую задачу решить? Название: Re: Уникальные перестановки Отправлено: square от Июнь 17, 2012, 06:48:04 Вот пытаюсь вручную такие длинные комбинации сочинить, чтобы разрешалось повторяться только числам 1 и 2. Комбинации надо составлять из чисел 1,2,3,4,5,6, в каждой комбинации 12 чисел. И таких комбинаций надо 36 штук.
1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 1 1 1 1 2 2 1 3 3 1 1 1 2 3 3 3 . . . . . . . . . . . . . Я могла тут ошибиться, трудно визуально всё проверить, надо по программе проверять. Смотрите, пара (1,2) повторяется в первой и второй строках (1-ая и 7-ая позиции), а также в первой и третьей строках (6-ая и 9-ая позиции). Числам 1,2 разрешается повторяться в люьых строках и в любых позициях. Я так поняла. Ну, выше пример есть из статьи. Название: Re: Уникальные перестановки Отправлено: square от Июнь 17, 2012, 08:14:53 Вижу ошибку, пара (1,1) повторяется, получается во всех четырёх позициях стоят 1.
Вот трудно визуально все ошибки сразу увидеть :) Тогда так попробуем написать: 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 1 1 1 1 2 2 1 3 3 3 1 1 2 3 3 3 . . . . . . . . Так получается? Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 17, 2012, 16:27:34 да. у меня получается только 30. больше таким способом не получается пока, увы.
Название: Re: Уникальные перестановки Отправлено: square от Июнь 19, 2012, 23:13:43 zhekas
как у вас дела с десятками? Сколько комбинаций нашли? 50 комбинаций покажите, пожалуйста, которые уже нашли. Просьба такая: можете сделать набор непересекающихся комбинаций из чисел 1,2,3,4,5? Это, наверное, быстро получится. Их должно быть 25 штук. Уникальные перестановки для n=5 у меня есть, а вот непересекающихся комбинаций нет. Заранее спасибо. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 19, 2012, 23:21:19 с десятками на 50-и всё остановилось. Больше нет (по методу Wesson)
Показать скрытый текст для n=5 Показать скрытый текст Название: Re: Уникальные перестановки Отправлено: square от Июнь 20, 2012, 03:27:29 Спасибо большое.
Вот посмотрите, что мне удалось найти по своей простенькой программке (она только добавляет одну строку): Код: 1 1 1 1 1 1 1 5 5 5 5 3 Это комбинации длины 12 из чисел 1,2,3,4,5,6. Вообще-то я хотела разрешить повторение только пары чисел 1,2, но ошиблась в программе, и у меня повторяются ещё числа 2,3. Однако лемму к этому прямоугольнику мне применить удалось (лемма делает из прямоугольника nxm прямоугольник nxkm). Обсуждали мой пример на dxdy.ru http://dxdy.ru/topic54283.html Пришли к выводу, что и числа 2,3 могут повторяться, если 3 взять по модулю 2 и при этом не получится прямоугольник со весеми 4 одинаковыми вершинами. То есть в приведённом примере 3 2 3 2 по модулю 2 будет 1 2 1 2 и всё нормально. В любых двух строках пересечение допускается только одно. Например, в последних двух строках имеем пересечение 1 2 1 2 и больше пересечений нет. Вот такая задача у меня :) Хочу попросить вас, если есть время, продолжить этот набор по описанным правилам. Надо 36 таких комбинаций. Комбинации с разрешением повторений ведь искать проще, чем непересекающиеся комбинации. Правда, комбинации теперь в два раза длиннее. А я что-то никак не разберусь с циклами в программе полного перебора; вот сделала программу только для добавления одной строки к набору из n строк. Это простая программка, но она много строк не находит. Если программа долго будет работать, то мне её пришлёте тогда, я сама буду крутить, у меня времени много свободного и машина свободна всегда :) Wesson и вас приглашаю порешать мою задачку, а также и всех других форумчан. В Экселе тоже вроде можно простенькие программки писать, но я не умею, никогда не пользовалась Экселем. Название: Re: Уникальные перестановки Отправлено: square от Июнь 20, 2012, 11:07:15 zhekas
начала строить квадрат на основе непересекающихся перестановок из чисел 1,2,3,...,10, он у меня не получился. Стала смотртеть комбинации... Что-то вы напутали. Смотрите вот на эту строку: 4 4 3 2 10 7 1 1 7 7 и на первую строку 1 1 1 1 1 1 1 1 1 1 Здесь есть пересечение 1 1 1 1 И ещё есть пересечения в других строках. Или метод не сработал, или вы ошиблись. Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 20, 2012, 11:27:16 вечером взгляну
Название: Re: Уникальные перестановки Отправлено: zhekas от Июнь 20, 2012, 11:36:05 С перебором всё так. Это с построением вышла маленькая заминка.
Попробуйте вот это Показать скрытый текст Название: Re: Уникальные перестановки Отправлено: square от Июнь 20, 2012, 11:56:42 Да, из этого набора получилось.
Спасибо. Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 22, 2012, 16:15:31 с десятками на 50-и всё остановилось. Больше нет (по методу Wesson) Показать скрытый текст для n=5 Показать скрытый текст я не понимаю, почему с н=5 можно 25, а с н=6 только 30 (по программе) и еще +1 (не проверял) по ТС... ??? и почему с 10 только 50??? оч. хотелось бы хотя бы намеки теории в базу.. :yesgirl: Название: Re: Уникальные перестановки Отправлено: Smith от Июнь 22, 2012, 16:27:13 и еще прямой вопрос: 36 из 6 - возможно? ???
зы: ежли кто-нить знает это наверное... :yesgirl: Название: Re: Уникальные перестановки Отправлено: square от Июнь 23, 2012, 03:38:28 я не понимаю, почему с н=5 можно 25, а с н=6 только 30 (по программе) и еще +1 (не проверял) по ТС... ??? и почему с 10 только 50??? оч. хотелось бы хотя бы намеки теории в базу.. :yesgirl: Даю вам ссылку на форум dxdy.ru http://dxdy.ru/topic59550.html В этой теме я пыталась найти ответы на ваши вопросы (и у меня такие же вопросы). Увы, никто ответов, похоже, не знает. Новая теория, нет ещё базовых знаний. Так что большой простор для творчества! Исследуйте вопрос, найдите ответы, не забудьте сообщить свои результаты. :) |