Цитата(Pawl @ 11.2.2014, 08:00  ) |
| первое, что приходит в голову, это (nxn)!, но ведь будут встречаться и одинаковые комбинации элементов. |
Тогда первое, что приходит в голову - это (n*n!)/П((ni*ni)!)
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > число перестановок элементов матрицы |
| Автор: Pawl 11.2.2014, 07:00 |
| Как рассчитать сабж? Понятно, первое, что приходит в голову, это (nxn)!, но ведь будут встречаться и одинаковые комбинации элементов. Добавлено @ 07:03 Да, с условием того, что элементы из одной строки матрицы такие же, как и в остальных, т. е., к примеру, (1 2 3) (1 2 3) (1 2 3) И как эти перестановки эффективнее всего найти? |
| Автор: Akina 11.2.2014, 07:26 | ||
Сформулируй ТОЧНО понятие "перестановка". Могут ли элементы перемещаться по всей матрице, или например только в пределах строки? От этого зависит ответ.
Тогда первое, что приходит в голову - это (n*n!)/П((ni*ni)!) |
| Автор: Pawl 11.2.2014, 08:20 | ||
Согласен, не уточнил. По всей матрице |
| Автор: Akina 11.2.2014, 08:27 | ||||
UPD: погорячился, на автомате залепил второе умножение. Правильно так: (n*n)!/П(ni!) Т.е. для приведённой выше матрицы это будет 9! / (3! * 3! * 3!) = 1680 |
| Автор: Pawl 11.2.2014, 15:36 |
| Спасибо. А с реализацией алогритма не поможете? |
| Автор: Akina 11.2.2014, 16:25 |
| А что не получается? я даже представить не могу, где тут можно найти проблему (если не считать переполнения типа или потери точности - но это уже не алгоритм)... |
| Автор: Pawl 11.2.2014, 19:08 | ||
Ну, как полный перебор сделать я представляю, ваша подсказка с разворачиванием в 1-мерный массив меня навела на мысль. Моя идея в следующем: развернуть массив, сохранить его в некий объект-список, сделать одну перестановку, сравнить полученный массив с теми, что есть в списке, если такого нет, сохранить его, сделать новую перестановку. Затем все сохраненные массивы снова свернуть и вывести на печать. Но сложность полного перебора тут таки будет (n*n)! В то время, как реально, как вы сказали, должна быть (n*n)!/П(ni!). Вот я и хочу узнать, может, это можно как-нибудь оптимизировать? |
| Автор: Akina 11.2.2014, 21:18 |
| Так... забыли, что написано выше. Сформулируй задачу. ПОЛНОСТЬЮ. От начала до конца. Без малейших как недоговорённостей, так и излишков. |
| Автор: Pawl 12.2.2014, 19:13 | ||
имеется массв nxn: (1 2 3 4 ... n) (1 2 3 4 ... n) (1 2 3 4 ... n) (1 2 3 4 ... n) ... (1 2 3 4 ... n) Определить все возможные перестановки (permutations) элементов в нем. Один из вариантов: (1 3 3 4 ... n) (1 2 2 4 ... n) (1 2 3 4 ... n) (1 2 3 4 ... n) ... (1 2 3 4 ... n) |
| Автор: Akina 12.2.2014, 20:27 |
| Блин... тебе что, надо сгенерировать все перестановки, что ли? Тогда просто строй рекурсивную процедуру заполнения пустого массива элементами из набора неиспользованных... в неё передаётся текущий заполненный частично массив, текущий указатель заполнения, список нераспределённых элементов (значение - количество).Если список пуст - выводишь очередную генерацию и выход, иначе ставишь на очередное место каждый из доступных элементов и вызываешь себя, скорректировав перердаваемые параметры. |
| Автор: Pawl 12.2.2014, 21:39 | ||
А как избавиться от генерации одинаковых массивов? Вот, к примеру, единицы из первой и второй строки поменяются, генерация - новая, а массив такой, как был. Я сразу спрашивал, есть ли алгоритм, оптимальнее полного перебора? |
| Автор: Akina 13.2.2014, 07:28 | ||
Вы не разобрались в описании. Алгоритм не генерирует дубликатов. |
| Автор: Pawl 13.2.2014, 19:27 | ||
Возможно... Что же, буду разбираться. Пока тему закрываю. |