Как рассчитать сабж? Понятно, первое, что приходит в голову, это (nxn)!, но ведь будут встречаться и одинаковые комбинации элементов.

Добавлено @ 07:03
Да, с условием того, что элементы из одной строки матрицы такие же, как и в остальных, т. е., к примеру,
(1 2 3)
(1 2 3)
(1 2 3)
И как эти перестановки эффективнее всего найти?

Это сообщение отредактировал(а) Pawl - 11.2.2014, 07:04

Сформулируй ТОЧНО понятие "перестановка". Могут ли элементы перемещаться по всей матрице, или например только в пределах строки? От этого зависит ответ.


Тогда первое, что приходит в голову - это (n*n!)/П((ni*ni)!)

Согласен, не уточнил. По всей матрице

Это сообщение отредактировал(а) Pawl - 11.2.2014, 08:21

UPD: погорячился, на автомате залепил второе умножение. Правильно так:
(n*n)!/П(ni!)

Т.е. для приведённой выше матрицы это будет 9! / (3! * 3! * 3!) = 1680


Это сообщение отредактировал(а) Akina - 11.2.2014, 08:34

Спасибо. А с реализацией алогритма не поможете?

А что не получается? я даже представить не могу, где тут можно найти проблему (если не считать переполнения типа или потери точности - но это уже не алгоритм)...

Ну, как полный перебор сделать я представляю, ваша подсказка с разворачиванием в 1-мерный массив меня навела на мысль. Моя идея в следующем: развернуть массив, сохранить его в некий объект-список, сделать одну перестановку, сравнить полученный массив с теми, что есть в списке, если такого нет, сохранить его, сделать новую перестановку. Затем все сохраненные массивы снова свернуть и вывести на печать. Но сложность полного перебора тут таки будет (n*n)! В то время, как реально, как вы сказали, должна быть (n*n)!/П(ni!). Вот я и хочу узнать, может, это можно как-нибудь оптимизировать?

Так... забыли, что написано выше. Сформулируй задачу. ПОЛНОСТЬЮ. От начала до конца. Без малейших как недоговорённостей, так и излишков.

имеется массв 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)

Это сообщение отредактировал(а) Pawl - 12.2.2014, 19:14

Блин... тебе что, надо сгенерировать все перестановки, что ли? Тогда просто строй рекурсивную процедуру заполнения пустого массива элементами из набора неиспользованных... в неё передаётся текущий заполненный частично массив, текущий указатель заполнения, список нераспределённых элементов (значение - количество).Если список пуст - выводишь очередную генерацию и выход, иначе ставишь на очередное место каждый из доступных элементов и вызываешь себя, скорректировав перердаваемые параметры.

А как избавиться от генерации одинаковых массивов?
Вот, к примеру, единицы из первой и второй строки поменяются, генерация - новая, а массив такой, как был. Я сразу спрашивал, есть ли алгоритм, оптимальнее полного перебора?

Вы не разобрались в описании. Алгоритм не генерирует дубликатов.

Возможно... Что же, буду разбираться. Пока тему закрываю.