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