Перечисление всех перестановок строки/целого
Общая задача в опросах по программированию (не из моего опыта интервью) - взять строку или целое число и перечислить все возможные перестановки.
Есть ли пример того, как это делается, и логику решения этой проблемы?
Я видел несколько фрагментов кода, но они не были хорошо прокомментированы/объяснены и поэтому трудно следовать.
Ответы
Ответ 1
Прежде всего: он, конечно, пахнет рекурсией!
Поскольку вы также хотели знать принцип, я сделал все возможное, чтобы объяснить его человеческий язык. Я думаю, что рекурсия очень проста в большинстве случаев. Вам нужно всего лишь выполнить два шага:
- Первый шаг
- Все остальные шаги (все с одинаковой логикой)
В человеческом языке:
Короче:
1. Перестановка 1 элемента - это один элемент.
2. Перестановка набора элементов - это список каждого из элементов, объединенный с каждой перестановкой других элементов.
Пример:
Если набор имеет только один элемент →
верните его.
perm (a) → a
Если набор имеет два символа: для каждый элемент в нем: вернуть элемент с перестановкой Остальные элементы добавлены так:
perm (ab) →
a + perm (b) → ab
b + perm (a) → ba
Далее: для каждого символа в наборе: вернуть символ, связанный с переходом > остальной части набора
perm (abc) →
a + perm (bc) → abc, acb
b + perm (ac) → bac, bca
c + perm (ab) → cab, cba
perm (abc... z) →
a + perm (...), b + perm (....)
....
Я нашел псевдокод на http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:
makePermutations(permutation) {
if (length permutation < required length) {
for (i = min digit to max digit) {
if (i not in permutation) {
makePermutations(permutation+i)
}
}
}
else {
add permutation to list
}
}
С#
ОК, и что-то более сложное (и поскольку оно помечено С#), из http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html:
Довольно длинный, но я все равно решил его скопировать, поэтому сообщение не зависит от оригинала.
Функция принимает строку символов и записывает все возможные перестановки этой точной строки, поэтому, например, если "ABC" была предоставлена, она должна разливаться:
ABC, ACB, BAC, BCA, CAB, CBA.
код:
class Program
{
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
public static void GetPer(char[] list)
{
int x = list.Length - 1;
GetPer(list, 0, x);
}
private static void GetPer(char[] list, int k, int m)
{
if (k == m)
{
Console.Write(list);
}
else
for (int i = k; i <= m; i++)
{
Swap(ref list[k], ref list[i]);
GetPer(list, k + 1, m);
Swap(ref list[k], ref list[i]);
}
}
static void Main()
{
string str = "sagiv";
char[] arr = str.ToCharArray();
GetPer(arr);
}
}
Ответ 2
Это только две строки кода, если LINQ разрешено использовать. См. Мой ответ здесь.
ИЗМЕНИТЬ
Вот моя общая функция, которая может возвращать все перестановки (не комбинации) из списка T:
static IEnumerable<IEnumerable<T>>
GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
Пример:
IEnumerable<IEnumerable<int>> result =
GetPermutations(Enumerable.Range(1, 3), 3);
Вывод - список целых списков:
{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
Поскольку эта функция использует LINQ, для этого требуется .net 3.5 или выше.
Ответ 3
Здесь я нашел решение. Он был написан на Java, но я преобразовал его в С#. Надеюсь, это поможет вам.
![Enter image description here]()
Здесь код в С#:
static void Main(string[] args)
{
string str = "ABC";
char[] charArry = str.ToCharArray();
permute(charArry, 0, 2);
Console.ReadKey();
}
static void permute(char[] arry, int i, int n)
{
int j;
if (i==n)
Console.WriteLine(arry);
else
{
for(j = i; j <=n; j++)
{
swap(ref arry[i],ref arry[j]);
permute(arry,i+1,n);
swap(ref arry[i], ref arry[j]); //backtrack
}
}
}
static void swap(ref char a, ref char b)
{
char tmp;
tmp = a;
a=b;
b = tmp;
}
Ответ 4
Рекурсия не требуется, здесь является хорошей информацией об этом решении.
var values1 = new[] { 1, 2, 3, 4, 5 };
foreach (var permutation in values1.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}
var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };
foreach (var permutation in values2.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}
Console.ReadLine();
Я использовал этот алгоритм в течение многих лет, он имеет O (N) сложность времени и пространства для расчета каждой перестановки .
public static class SomeExtensions
{
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
{
var array = enumerable as T[] ?? enumerable.ToArray();
var factorials = Enumerable.Range(0, array.Length + 1)
.Select(Factorial)
.ToArray();
for (var i = 0L; i < factorials[array.Length]; i++)
{
var sequence = GenerateSequence(i, array.Length - 1, factorials);
yield return GeneratePermutation(array, sequence);
}
}
private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
{
var clone = (T[]) array.Clone();
for (int i = 0; i < clone.Length - 1; i++)
{
Swap(ref clone[i], ref clone[i + sequence[i]]);
}
return clone;
}
private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
{
var sequence = new int[size];
for (var j = 0; j < sequence.Length; j++)
{
var facto = factorials[sequence.Length - j];
sequence[j] = (int)(number / facto);
number = (int)(number % facto);
}
return sequence;
}
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
private static long Factorial(int n)
{
long result = n;
for (int i = 1; i < n; i++)
{
result = result * i;
}
return result;
}
}
Ответ 5
void permute (char *str, int ptr) {
int i, len;
len = strlen(str);
if (ptr == len) {
printf ("%s\n", str);
return;
}
for (i = ptr ; i < len ; i++) {
swap (&str[ptr], &str[i]);
permute (str, ptr + 1);
swap (&str[ptr], &str[i]);
}
}
Вы можете написать свою функцию свопинга для замены символов.
Это должно вызываться как permute (string, 0);
Ответ 6
Прежде всего, у наборов есть перестановки, а не строки или целые числа, поэтому я просто предполагаю, что вы имеете в виду "набор символов в строке".
Заметим, что набор размеров n имеет n! п-перестановки.
Следующий псевдокод (из Википедии), называемый с k = 1... n! даст все перестановки:
function permutation(k, s) {
for j = 2 to length(s) {
swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
k := k / j; // integer division cuts off the remainder
}
return s;
}
Здесь эквивалентный код Python (для индексов массива 0):
def permutation(k, s):
r = s[:]
for j in range(2, len(s)+1):
r[j-1], r[k%j] = r[k%j], r[j-1]
k = k/j+1
return r
Ответ 7
Немного измененная версия на С#, которая дает необходимые перестановки в массиве любого типа.
// USAGE: create an array of any type, and call Permutations()
var vals = new[] {"a", "bb", "ccc"};
foreach (var v in Permutations(vals))
Console.WriteLine(string.Join(",", v)); // Print values separated by comma
public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
if (fromInd + 1 == values.Length)
yield return values;
else
{
foreach (var v in Permutations(values, fromInd + 1))
yield return v;
for (var i = fromInd + 1; i < values.Length; i++)
{
SwapValues(values, fromInd, i);
foreach (var v in Permutations(values, fromInd + 1))
yield return v;
SwapValues(values, fromInd, i);
}
}
}
private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
if (pos1 != pos2)
{
T tmp = values[pos1];
values[pos1] = values[pos2];
values[pos2] = tmp;
}
}
Ответ 8
Мне понравился подход FBryant87, поскольку он прост. К сожалению, это похоже на то, что многие другие "решения" не предлагают всех перестановок или, например, целое число, если оно содержит одну и ту же цифру более одного раза. Например, возьмите 656123. Строка:
var tail = chars.Except(new List<char>(){c});
using Except приведет к удалению всех вхождений, т.е. при c = 6, две цифры будут удалены, и мы останемся, например. 5123. Поскольку ни одно из решений, которые я пробовал, не решило это, я решил попробовать и сам решить, используя код FBryant87 в качестве базы. Вот что я придумал:
private static List<string> FindPermutations(string set)
{
var output = new List<string>();
if (set.Length == 1)
{
output.Add(set);
}
else
{
foreach (var c in set)
{
// Remove one occurrence of the char (not all)
var tail = set.Remove(set.IndexOf(c), 1);
foreach (var tailPerms in FindPermutations(tail))
{
output.Add(c + tailPerms);
}
}
}
return output;
}
Я просто удаляю первое обнаруженное появление, используя .Remove и .IndexOf. Кажется, работает как минимум для моего использования. Я уверен, что это можно сделать умнее.
Следует отметить одно: в результате список может содержать дубликаты, поэтому убедитесь, что вы либо возвращаете метод, например. вместо HashSet или удалить дубликаты после возврата, используя любой способ, который вам нравится.
Ответ 9
Вот хорошая статья, охватывающая три алгоритма для нахождения всех перестановок, в том числе для поиска следующей перестановки.
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
С++ и Python имеют встроенный next_permutation и itertools.permutations соответственно.
Ответ 10
Здесь чисто функциональная реализация F #:
let factorial i =
let rec fact n x =
match n with
| 0 -> 1
| 1 -> x
| _ -> fact (n-1) (x*n)
fact i 1
let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]
let rec permutation (k:int,j:int) (r:'a array) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))
let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }
Производительность может быть значительно улучшена путем изменения swap, чтобы воспользоваться изменчивой природой массивов CLR, но эта реализация является потокобезопасной в отношении исходного массива и может быть желательной в некоторых контекстах.
Кроме того, для массивов с более чем 16 элементами int должен быть заменен типами с большей/произвольной точностью, поскольку factorial 17 приводит к переполнению int32.
Ответ 11
Вот функция, которая будет печатать всю перестановку.
Эта функция реализует логику Объяснение peter.
public class Permutation
{
//http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm
public static void permuteString(String beginningString, String endingString)
{
if (endingString.Length <= 1)
Console.WriteLine(beginningString + endingString);
else
for (int i = 0; i < endingString.Length; i++)
{
String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);
permuteString(beginningString + endingString.ElementAt(i), newString);
}
}
}
static void Main(string[] args)
{
Permutation.permuteString(String.Empty, "abc");
Console.ReadLine();
}
Ответ 12
Ниже приведена моя реализация перестановки. Не обращайте внимания на имена переменных, поскольку я делал это для удовольствия:)
class combinations
{
static void Main()
{
string choice = "y";
do
{
try
{
Console.WriteLine("Enter word :");
string abc = Console.ReadLine().ToString();
Console.WriteLine("Combinatins for word :");
List<string> final = comb(abc);
int count = 1;
foreach (string s in final)
{
Console.WriteLine("{0} --> {1}", count++, s);
}
Console.WriteLine("Do you wish to continue(y/n)?");
choice = Console.ReadLine().ToString();
}
catch (Exception exc)
{
Console.WriteLine(exc);
}
} while (choice == "y" || choice == "Y");
}
static string swap(string test)
{
return swap(0, 1, test);
}
static List<string> comb(string test)
{
List<string> sec = new List<string>();
List<string> first = new List<string>();
if (test.Length == 1) first.Add(test);
else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
else if (test.Length > 2)
{
sec = generateWords(test);
foreach (string s in sec)
{
string init = s.Substring(0, 1);
string restOfbody = s.Substring(1, s.Length - 1);
List<string> third = comb(restOfbody);
foreach (string s1 in third)
{
if (!first.Contains(init + s1)) first.Add(init + s1);
}
}
}
return first;
}
static string ShiftBack(string abc)
{
char[] arr = abc.ToCharArray();
char temp = arr[0];
string wrd = string.Empty;
for (int i = 1; i < arr.Length; i++)
{
wrd += arr[i];
}
wrd += temp;
return wrd;
}
static List<string> generateWords(string test)
{
List<string> final = new List<string>();
if (test.Length == 1)
final.Add(test);
else
{
final.Add(test);
string holdString = test;
while (final.Count < test.Length)
{
holdString = ShiftBack(holdString);
final.Add(holdString);
}
}
return final;
}
static string swap(int currentPosition, int targetPosition, string temp)
{
char[] arr = temp.ToCharArray();
char t = arr[currentPosition];
arr[currentPosition] = arr[targetPosition];
arr[targetPosition] = t;
string word = string.Empty;
for (int i = 0; i < arr.Length; i++)
{
word += arr[i];
}
return word;
}
}
Ответ 13
Вот пример высокого уровня, который я написал, который иллюстрирует объяснение человеческого языка. Питер дал:
public List<string> FindPermutations(string input)
{
if (input.Length == 1)
return new List<string> { input };
var perms = new List<string>();
foreach (var c in input)
{
var others = input.Remove(input.IndexOf(c), 1);
perms.AddRange(FindPermutations(others).Select(perm => c + perm));
}
return perms;
}
Ответ 14
Здесь легко понять функцию перестановки для строки и целого в качестве входных данных. С помощью вы можете даже установить длину вывода (которая в нормальном случае равна входной длине)
Строка
static ICollection<string> result;
public static ICollection<string> GetAllPermutations(string str, int outputLength)
{
result = new List<string>();
MakePermutations(str.ToCharArray(), string.Empty, outputLength);
return result;
}
private static void MakePermutations(
char[] possibleArray,//all chars extracted from input
string permutation,
int outputLength//the length of output)
{
if (permutation.Length < outputLength)
{
for (int i = 0; i < possibleArray.Length; i++)
{
var tempList = possibleArray.ToList<char>();
tempList.RemoveAt(i);
MakePermutations(tempList.ToArray(),
string.Concat(permutation, possibleArray[i]), outputLength);
}
}
else if (!result.Contains(permutation))
result.Add(permutation);
}
а для Integer просто измените метод вызова, а MakePermutations() останется нетронутым:
public static ICollection<int> GetAllPermutations(int input, int outputLength)
{
result = new List<string>();
MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
return result.Select(m => int.Parse(m)).ToList<int>();
}
пример 1: GetAllPermutations ( "abc", 3);
"abc" "acb" "bac" "bca" "cab" "cba"
пример 2: GetAllPermutations ( "abcd", 2);
"ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"
пример 3: GetAllPermutations (486,2);
48 46 84 86 64 68
Ответ 15
Вот простое решение в С# с использованием рекурсии,
void Main()
{
string word = "abc";
WordPermuatation("",word);
}
void WordPermuatation(string prefix, string word)
{
int n = word.Length;
if (n == 0) { Console.WriteLine(prefix); }
else
{
for (int i = 0; i < n; i++)
{
WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
}
}
}
Ответ 16
Здесь мое решение в JavaScript (NodeJS). Основная идея заключается в том, что мы берем один элемент за раз, "удаляем его" из строки, меняем остальные символы и вставляем элемент спереди.
function perms (string) {
if (string.length == 0) {
return [];
}
if (string.length == 1) {
return [string];
}
var list = [];
for(var i = 0; i < string.length; i++) {
var invariant = string[i];
var rest = string.substr(0, i) + string.substr(i + 1);
var newPerms = perms(rest);
for (var j = 0; j < newPerms.length; j++) {
list.push(invariant + newPerms[j]);
}
}
return list;
}
module.exports = perms;
И вот тесты:
require('should');
var permutations = require('../src/perms');
describe('permutations', function () {
it('should permute ""', function () {
permutations('').should.eql([]);
})
it('should permute "1"', function () {
permutations('1').should.eql(['1']);
})
it('should permute "12"', function () {
permutations('12').should.eql(['12', '21']);
})
it('should permute "123"', function () {
var expected = ['123', '132', '321', '213', '231', '312'];
var actual = permutations('123');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})
it('should permute "1234"', function () {
// Wolfram Alpha FTW!
var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
var actual = permutations('1234');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})
})
Ответ 17
Вот самое простое решение, о котором я могу думать:
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs
Функция distribute принимает новый элемент e и список n -element и возвращает список из n+1 списков, каждый из которых имеет e, вставленный в другое место. Например, вставив 10 в каждое из четырех возможных мест в списке [1;2;3]:
> distribute 10 [1..3];;
val it : int list list =
[[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]
Функция permute складывается по каждому элементу, в свою очередь распределяя по накопленным до сих пор перестановкам, достигая высшей точки во всех перестановках. Например, 6 перестановок списка [1;2;3]:
> permute [1;2;3];;
val it : int list list =
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]
Изменение fold на a scan, чтобы промежуточные накопители проливали некоторый свет на то, как сгенерированы перестановки, элемент за раз:
> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
seq
[[[]]; [[1]]; [[2; 1]; [1; 2]];
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]
Ответ 18
Вот функция, которая будет рекурсивно печатать все перестановки.
public void Permutations(string input, StringBuilder sb)
{
if (sb.Length == input.Length)
{
Console.WriteLine(sb.ToString());
return;
}
char[] inChar = input.ToCharArray();
for (int i = 0; i < input.Length; i++)
{
if (!sb.ToString().Contains(inChar[i]))
{
sb.Append(inChar[i]);
Permutations(input, sb);
RemoveChar(sb, inChar[i]);
}
}
}
private bool RemoveChar(StringBuilder input, char toRemove)
{
int index = input.ToString().IndexOf(toRemove);
if (index >= 0)
{
input.Remove(index, 1);
return true;
}
return false;
}
Ответ 19
Вот ответ на С#, который немного упрощен.
public static void StringPermutationsDemo()
{
strBldr = new StringBuilder();
string result = Permute("ABCD".ToCharArray(), 0);
MessageBox.Show(result);
}
static string Permute(char[] elementsList, int startIndex)
{
if (startIndex == elementsList.Length)
{
foreach (char element in elementsList)
{
strBldr.Append(" " + element);
}
strBldr.AppendLine("");
}
else
{
for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
{
Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
Permute(elementsList, (startIndex + 1));
Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
}
}
return strBldr.ToString();
}
static void Swap(ref char Char1, ref char Char2)
{
char tempElement = Char1;
Char1 = Char2;
Char2 = tempElement;
}
Вывод:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Ответ 20
Это мое решение, которое мне легко понять
class ClassicPermutationProblem
{
ClassicPermutationProblem() { }
private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
{
foreach (T element in list)
{
List<T> currentTemp = temp.ToList();
if (!currentTemp.Contains(element))
currentTemp.Add(element);
else
continue;
if (position == list.Count)
finalList.Add(currentTemp);
else
PopulatePosition(finalList, list, currentTemp, position + 1);
}
}
public static List<List<int>> GetPermutations(List<int> list)
{
List<List<int>> results = new List<List<int>>();
PopulatePosition(results, list, new List<int>(), 1);
return results;
}
}
static void Main(string[] args)
{
List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}
Ответ 21
Если производительность и память являются проблемой, я предлагаю эту очень эффективную реализацию. Согласно алгоритм кучи в Википедии, он должен быть самым быстрым. Надеюсь, это будет соответствовать вашим потребностям:-)!
Как сравнение этого с реализацией Linq за 10! (включая код):
- Это: 36288000 элементов в 235 миллисекундах
-
Linq: 36288000 элементов в 50051 миллисекундах
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
namespace WpfPermutations
{
/// <summary>
/// EO: 2016-04-14
/// Generator of all permutations of an array of anything.
/// Base on Heap Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
/// </summary>
public static class Permutations
{
/// <summary>
/// Heap algorithm to find all pmermutations. Non recursive, more efficient.
/// </summary>
/// <param name="items">Items to permute in each possible ways</param>
/// <param name="funcExecuteAndTellIfShouldStop"></param>
/// <returns>Return true if cancelled</returns>
public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
{
int countOfItem = items.Length;
if (countOfItem <= 1)
{
return funcExecuteAndTellIfShouldStop(items);
}
var indexes = new int[countOfItem];
for (int i = 0; i < countOfItem; i++)
{
indexes[i] = 0;
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
for (int i = 1; i < countOfItem;)
{
if (indexes[i] < i)
{ // On the web there is an implementation with a multiplication which should be less efficient.
if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same.
{
Swap(ref items[i], ref items[indexes[i]]);
}
else
{
Swap(ref items[i], ref items[0]);
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
indexes[i]++;
i = 1;
}
else
{
indexes[i++] = 0;
}
}
return false;
}
/// <summary>
/// This function is to show a linq way but is far less efficient
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="length"></param>
/// <returns></returns>
static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
/// <summary>
/// Swap 2 elements of same type
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
/// <summary>
/// Func to show how to call. It does a little test for an array of 4 items.
/// </summary>
public static void Test()
{
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Debug.Print(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
Debug.Print("Non Linq");
ForAllPermutation(values, (vals) =>
{
Debug.Print(String.Join("", vals));
return false;
});
Debug.Print("Linq");
foreach(var v in GetPermutations(values, values.Length))
{
Debug.Print(String.Join("", v));
}
// Performance
int count = 0;
values = new int[10];
for(int n = 0; n < values.Length; n++)
{
values[n] = n;
}
Stopwatch stopWatch = new Stopwatch();
stopWatch.Reset();
stopWatch.Start();
ForAllPermutation(values, (vals) =>
{
foreach(var v in vals)
{
count++;
}
return false;
});
stopWatch.Stop();
Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
count = 0;
stopWatch.Reset();
stopWatch.Start();
foreach (var vals in GetPermutations(values, values.Length))
{
foreach (var v in vals)
{
count++;
}
}
stopWatch.Stop();
Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
}
}
}
Ответ 22
Вот еще одна реализация упомянутого алго.
public class Program
{
public static void Main(string[] args)
{
string str = "abcefgh";
var astr = new Permutation().GenerateFor(str);
Console.WriteLine(astr.Length);
foreach(var a in astr)
{
Console.WriteLine(a);
}
//a.ForEach(Console.WriteLine);
}
}
class Permutation
{
public string[] GenerateFor(string s)
{
if(s.Length == 1)
{
return new []{s};
}
else if(s.Length == 2)
{
return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};
}
var comb = new List<string>();
foreach(var c in s)
{
string cStr = c.ToString();
var sToProcess = s.Replace(cStr,"");
if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
{
var conCatStr = GenerateFor(sToProcess);
foreach(var a in conCatStr)
{
comb.Add(c.ToString()+a);
}
}
}
return comb.ToArray();
}
}
Ответ 23
Перечисляет перестановки строки. Избегает дублирования при повторении символов:
using System;
using System.Collections;
class Permutation{
static IEnumerable Permutations(string word){
if (word == null || word.Length <= 1) {
yield return word;
yield break;
}
char firstChar = word[0];
foreach( string subPermute in Permutations (word.Substring (1)) ) {
int indexOfFirstChar = subPermute.IndexOf (firstChar);
if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;
for( int index = 0; index <= indexOfFirstChar; index++ )
yield return subPermute.Insert (index, new string (firstChar, 1));
}
}
static void Main(){
foreach( var permutation in Permutations ("aab") )
Console.WriteLine (permutation);
}
}
Ответ 24
class Permutation
{
public static List<string> Permutate(string seed, List<string> lstsList)
{
loopCounter = 0;
// string s="\w{0,2}";
var lstStrs = PermuateRecursive(seed);
Trace.WriteLine("Loop counter :" + loopCounter);
return lstStrs;
}
// Recursive function to find permutation
private static List<string> PermuateRecursive(string seed)
{
List<string> lstStrs = new List<string>();
if (seed.Length > 2)
{
for (int i = 0; i < seed.Length; i++)
{
str = Swap(seed, 0, i);
PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
s =>
{
lstStrs.Add(str[0] + s);
loopCounter++;
});
;
}
}
else
{
lstStrs.Add(seed);
lstStrs.Add(Swap(seed, 0, 1));
}
return lstStrs;
}
//Loop counter variable to count total number of loop execution in various functions
private static int loopCounter = 0;
//Non recursive version of permuation function
public static List<string> Permutate(string seed)
{
loopCounter = 0;
List<string> strList = new List<string>();
strList.Add(seed);
for (int i = 0; i < seed.Length; i++)
{
int count = strList.Count;
for (int j = i + 1; j < seed.Length; j++)
{
for (int k = 0; k < count; k++)
{
strList.Add(Swap(strList[k], i, j));
loopCounter++;
}
}
}
Trace.WriteLine("Loop counter :" + loopCounter);
return strList;
}
private static string Swap(string seed, int p, int p2)
{
Char[] chars = seed.ToCharArray();
char temp = chars[p2];
chars[p2] = chars[p];
chars[p] = temp;
return new string(chars);
}
}
Ответ 25
/// <summary>
/// Print All the Permutations.
/// </summary>
/// <param name="inputStr">input string</param>
/// <param name="strLength">length of the string</param>
/// <param name="outputStr">output string</param>
private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars)
{
//Means you have completed a permutation.
if (outputStr.Length == NumberOfChars)
{
Console.WriteLine(outputStr);
return;
}
//For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc.
for(int i=0 ; i< strLength; i++)
{
// Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc.
PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4);
}
}
