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

Возникла задача получить все возможные перестановки из группы символов. Данную задачу я решал давно, еще на 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

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

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

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

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

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

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

Спасибо.

AntiTopMan 10.04.2018 11:40:21

Как мне передать не массив, а другую коллекцию содержимым которой является записи из бд ????

Андрей 10.04.2018 12:18:16

Используйте вместо строки, например, список. А вместо символов строки элементы списка.

Константин 30.07.2019 10:32:55

Логично использовать Generic, как-то так

    public class Permutations<T> where T : IComparable<T>
    {
        //Список перестановок
        private readonly List<T> _permutationsListGeneric;
        private List<List<T>> _result = new List<List<T>>();

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

        /// <summary>
        /// Рекурсивный поиск всех перестановок
        /// </summary>
        /// <param name="a">
        /// <param name="n">
        /// <param name="repeat">Содержать повторы
        private void RecPermutationGeneric(T[] 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) AddToListGeneric(a, repeat);
                if (n > 0) RecPermutationGeneric(a, n - 1, repeat);
            }
        }

        public Permutations(List<T> PermutationsListInt)
        {
            _permutationsListGeneric = PermutationsListInt;
        }

        /// <summary>
        /// Получает список всех перестановок
        /// </summary>
        /// <param name="repeat">Содержать повторения
        /// <returns></returns>
        public List<List<T>> GetPermutationsListGeneric(bool repeat = true)
        {
            RecPermutationGeneric(_permutationsListGeneric.ToArray(),
_permutationsListGeneric.Count, repeat);
            return _result;
        }
    }

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