Поиск всех перестановок из набора символов

Возникла задача получить все возможные перестановки из группы символов. Данную задачу я решал давно, еще на Pascal, сейчас решил освежить память и сделать реализацию на C#.

Набросал класс Permutations, который может получить список всех перестановок, отсортированный список всех перестановок, список перестановок без повторений.

Исходный код класса:

 public class Permutations
    {
        //Список перестановок
        private List _permutationsList;
        private String _str;

        /// 
        /// Добавляет новую перестановку в список
        /// 
        /// Массив символов
        /// Содержать повторы
        private void AddToList(char[] a, bool repeat = true)
        {
            var bufer = new StringBuilder("");
            for (int i = 0; i < a.Count(); i++)
            {
                bufer.Append(a[i]);
            }
            if (repeat || !_permutationsList.Contains(bufer.ToString()))
            {
                _permutationsList.Add(bufer.ToString());
            }

        }

        /// 
        /// Рекурсивный поиск всех перестановок
        /// 
        /// 
        /// 
        /// Содержать повторы
        private void RecPermutation(char[] a, int n, bool repeat = true)
        {
            for (var i = 0; i < n; i++)
            {
                var temp = a[n - 1];
                for (var j = n - 1; j > 0; j--)
                {
                    a[j] = a[j - 1];
                }
                a[0] = temp;
                if (i < n - 1) AddToList(a, repeat);
                if (n > 0) RecPermutation(a, n - 1, repeat);
            }
        }

        public Permutations()
        {
            _str = "";
        }

        public Permutations(String str)
        {
            _str = str;
        }
        /// 
        /// Строка, на основе которой строятся перестановки
        /// 
        public String PermutationStr
        {
            get
            {
                return _str;
            }
            set
            {
                _str = value;
            }
        }
        /// 
        /// Получает список всех перестановок
        /// 
        /// Содержать повторения
        /// 
        public List GetPermutationsList(bool repeat = true)
        {
            _permutationsList = new List { _str };
            RecPermutation(_str.ToArray(), _str.Length, repeat);
            return _permutationsList;
        }
        /// 
        /// Получает отсортированный список всех перестановок
        /// 
        /// Содержать повторения
        /// 
        public List GetPermutationsSortList(bool repeat = true)
        {
            GetPermutationsList(repeat).Sort();
            return _permutationsList;
        }

    }

Пример использования:

Получить список перестановок из 1234

const string str = "1234";
            var per = new Permutations(str);
            var list = per.GetPermutationsList();

            foreach (var l in list)
            {
                Console.WriteLine(l);
            }
Все перестановки

Чтобы получить отсортированный список, надо использовать строку

var list = per.GetPermutationsSortList();
Все перестановки отсортированные

Если нужно получить перестановки без повторений, например из 1231 то нужно использовать строку

var list = per.GetPermutationsSortList(false);

тоесть добавить false

Все перестановки без посторений

Комментарии (3) -

PermutationStr нигде не используется и зачем по несколько раз писать один и тот же комментарии.

Андрей 16.03.2015 9:39:59

PermutationStr не используется в текущем примере использования. Данное свойство было добавлено с расчетом на то, что потребуется изменение строки для перестоновок без создания нового класса.

Максим 18.04.2016 20:30:08

Спасибо.

Добавить комментарий