| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [C] Генерация циклических перестановок |
| Автор: tux32 21.11.2007, 08:35 |
| Помогите мне пожалуйста составить процедуру генерации всех циклических перестановок чисел от 1 до n в виде k циклов на Си |
| Автор: GIK 21.11.2007, 10:01 | ||
По подробнее, не пойму, можно пример привести  |
| Автор: tux32 16.12.2007, 00:09 |
| GIK, Алгоритм: в ходе генерации всех n! перестановок проверяем каждую перестановку на кол-во циклов, где каждый шаг осуществляется путём взятия значения элемента с текущей позиции до тех пор пока не придём в начальную позицию. Пример: перестановка {5,2,1,4,3} 1. Извлекаем значение на первой позиции равное 5, идём в пятную позицию, там видим число 3, идём в третью позицию, видим число 1, переходим в первую позицию, пришли туда откуда начинали, попутно отметив первую, третью и пятую позиции. Начинать поиск циклов с этих позиций уже не будем. 2. Извлекаем значение 2 на второй позиции, переходим во вторую позицию, получился цикл в себя. 3. Извлекаем значение 4 на четвёртой позиции, получаем цикл в себя. В итоге, все вершины были пройдены за 3 цикла. Вот. Значение n, чисел 1...n задаётся пользователем как и кол-во циклов k. Есть у кого-нибудь идеи? |