Перестановки: каждая следующая получается из предыдущей перестановкой двух соседних чисел - C#
Формулировка задачи:
Расскажите пожалуйста как это сделать в СИ#:
Напечатать все перестановки чисел 1....n, чтобы каждая следующая получалась из предыдущей перестановкой двух соседних чисел. Например, при n=3 следует переставлять:
3.21 → 23.1 → 2.13 → 12.3 →1.32 →3.12.
Понимаю логически, но в программе не выходит.
Заранее спасибо
Решение задачи: «Перестановки: каждая следующая получается из предыдущей перестановкой двух соседних чисел»
textual
Листинг программы
using System; using System.Collections.Generic; using System.Linq; namespace TestConsole { class Permutation { // Размер перестановки int n; /* Индексы * idx[i, 0] - содержит элемент i перестановки * idx[i, 1] - содержит направление i'го элемента перестановки, как 0 или 1 * {0, 1} * 2 - 1 = {-1, 1} - смещение влево/вправо * 1 - {0, 1} = {1, 0} - замена на обратное значение */ int[,] idx; // Индексы текущего наименьшего мобильного и следующего за ним int m, m2; public Permutation(int N) { n = N; idx = new int[n, 2]; // Заполняем индексы в порядке возрастания // Направления направления "вправо" 1> 2> 3> while (N-- > 0) { idx[N, 0] = N; idx[N, 1] = 1; } InvalidateMobile(); } // Поиск индекса наименьшего мобильного элемента private void InvalidateMobile() { m = m2 = -1; for (int i = 0; i < n; i++) { // Проверка на мобильность int i2 = i + idx[i, 1] * 2 - 1; if (i2 > -1 && i2 < n && idx[i, 0] < idx[i2, 0]) { // Сравнение по значению if (m == -1 || idx[i, 0] < idx[m, 0]) { m = i; m2 = i2; } } } LastSwapIndex = m < m2 ? m : m2; } /// <summary> /// Вычисление следующей перестановки /// </summary> public bool Next() { // Если мобильных элементов нет - завершение алгоритма if (m == -1) return false; // Находим все элементы меньше текущего мобильного и меняем их направление for (int i = 0; i < n; i++) { if (idx[i, 0] < idx[m, 0]) { idx[i, 1] = 1 - idx[i, 1]; } } // Меняем местами наименьший мобильный элемент и его соседа Swap(ref idx[m, 0], ref idx[m2, 0]); Swap(ref idx[m, 1], ref idx[m2, 1]); InvalidateMobile(); return true; } /// <summary> /// Индекс пары элементов коотрые будет обменяны на следющей итерации /// </summary> public int LastSwapIndex { get; private set; } private void Swap(ref int a, ref int b) { a = b + 0 * (b = a); } /// <summary> /// Возвращает элеметы массива в порядке перестановки /// </summary> public IEnumerable<T> Apply<T>(T[] Array) { for (int i = 0; i < n; i++) { yield return Array[idx[i, 0]]; } } public static IEnumerable<Permutation> AllOf(int N) { Permutation p = new Permutation(N); do yield return p; while (p.Next()); } } static class Task { static void Main() { int[] A = { 3, 2, 1 }; List<string> result = new List<string>(); foreach (var p in Permutation.AllOf(A.Length)) { result.Add( String.Join("", p.Apply(A)) .Insert(p.LastSwapIndex + 1, ".")); } Console.WriteLine(String.Join(" \u2192 ", result)); Console.ReadLine(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д