Перестановки: каждая следующая получается из предыдущей перестановкой двух соседних чисел - 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();
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.818 из 5
Похожие ответы