Auflisten aller Permutationen einer Zeichenkette / integer
https://stackoverflow.com/questions/756055
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Eine gemeinsame Aufgabe in der Programmierung Interviews (nicht aus meiner Erfahrung von Interviews obwohl) ist eine Zeichenfolge oder eine ganze Zahl zu nehmen und jede mögliche Permutation Liste.
Gibt es ein Beispiel dafür, wie dies geschehen ist und die Logik hinter ein solches Problem zu lösen?
Ich habe ein paar Code-Schnipsel zu sehen, aber sie waren nicht gut kommentiert / erklärt und somit schwer zu folgen.
Lösung
Zu allererst: es riecht wie Rekursion natürlich
!Da Sie auch das Prinzip wissen wollte, tat ich mein Bestes, es ist die menschliche Sprache zu erklären. Ich denke, Rekursion ist sehr einfach, die meisten der Zeit. Sie haben nur zwei Schritte ergreifen:
- Der erste Schritt
- Alle anderen Schritte (alle mit der gleichen Logik)
In die menschliche Sprache :
Kurz gesagt:
1. Die Permutation von 1-Element ist ein Element.
2. Die Permutation eines Satzes von Elementen ist eine Liste jedes der Elemente, mit jeder Permutation der anderen Elemente verkettet.
Beispiel:
Wenn der Satz hat nur ein Element ->
gibt es zurück.
perm (a) -> aWenn das Set besteht aus zwei Zeichen: für jedes Element in dem: die Rück Element, mit der Permutation der Rest der Elemente hinzugefügt, etwa so:
perm (ab) ->
a + zul (b) -> ab
b + zul (a) -> ba
Weitere: für jedes Zeichen in dem Satz: return einen Charakter, mit einem perumation von> dem Rest des Satzes verketteten
perm (abc) ->
a + zul (bc) -> abc , acb
b + zul (ac) -> bac , RND
c + zul (ab) -> Taxi , cba
perm (abc ... z) ->
a + zul (...), b + zul (....)
....
Ich fand den Pseudo-Code auf http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Ziemlich lang, aber ich beschloss, es trotzdem zu kopieren, so dass die Post nicht abhängig von der Vorlage ist.
Die Funktion eine Reihe von Zeichen nimmt und schreibt jede mögliche Permutation dieser exakten Zeichenfolge nach unten, so zum Beispiel, wenn „ABC“ geliefert wurde, sollen ergießen:
ABC, ACB, BAC, BCA, CAB, CBA.
Code:
class Program
{
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
var temp = a;
a = b;
b = temp;
}
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);
}
}
Andere Tipps
Es ist nur zwei Zeilen Code, wenn LINQ verwenden darf. Bitte beachten Sie meine Antwort hier .
Bearbeiten
Hier ist meine generische Funktion, die alle Permutationen zurückkehren kann (nicht-Kombinationen) aus einer Liste von 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 }));
}
Beispiel:
IEnumerable<IEnumerable<int>> result =
GetPermutations(Enumerable.Range(1, 3), 3);
Ausgabe - eine Liste von Integer-Listen:
{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
Da diese Funktion verwendet LINQ so es .net 3.5 oder höher benötigt.
Hier habe ich die Lösung gefunden. Es wurde in Java geschrieben, aber ich habe es in C # konvertiert. Ich hoffe, es wird Ihnen helfen.
Hier ist der Code in C #:
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;
}
Rekursion ist nicht notwendig, hier ist gute Informationen über diese Lösung.
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();
Ich habe diesen Algorithmus seit Jahren verwendet, es hat O (N) Zeit und Raum Komplexität jeder Permutation zu berechnen .
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;
}
}
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]);
}
}
Sie können Ihre Swap-Funktion zu tauschen Zeichen schreiben.
Dies ist genannt werden als permute (string, 0);
Zu allererst Sets Permutationen haben, keine Strings oder ganze Zahlen, also werde ich einfach davon ausgehen, du meinst „um die Menge von Zeichen in einer Zeichenkette.“
Hinweis, dass eine Reihe von Größe n hat n! n-Permutationen.
Der folgende Pseudo-Code (aus Wikipedia), mit k = 1 ... n genannt! geben alle Permutationen:
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;
}
Hier ist das Äquivalent Python-Code (für 0-basierten Array-Indizes):
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
leicht modifizierte Version in C #, die Ausbeuten Permutationen in einem Array von jeder Art benötigt werden.
// 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;
}
}
Ich möchte FBryant87 Ansatz, da es einfach ist. Leider ist es wie viele andere „Lösungen“ nicht alle Permutationen bieten oder von z.B. eine ganze Zahl, wenn es enthält die gleiche Ziffer mehr als einmal. Nehmen 656.123 als Beispiel. Die Zeile:
var tail = chars.Except(new List<char>(){c});
Mit Ausnahme verwendet, wird alle Vorkommen verursachen entfernt werden, das heißt, wenn c = 6, zwei Stellen werden entfernt, und wir werden mit beispielsweise links 5123 Da keine der Lösungen, die ich dieses Problem gelöst versuchte, habe ich mich entschlossen, es zu versuchen und zu lösen mich von FBryant87 's-Code als Basis. Das ist, was ich kam mit:
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;
}
ich einfach entfernen Sie einfach die ersten gefundenen Vorkommen mit .Remove und .IndexOf. Scheint für meine Verwendung zumindest wie beabsichtigt zu arbeiten. Ich bin sicher, könnte es klüger gemacht werden.
Eine Sache allerdings zu beachten: Die resultierende Liste kann Duplikate enthalten, so stellen Sie sicher, dass Sie entweder die Methode Rückkehr machen z.B. ein HashSet statt oder die Duplikate nach der Rückkehr entfernen jede Methode, die Sie mögen.
Hier ist ein guter Artikel über drei Algorithmen für alle Permutationen zu finden, darunter eine, die nächste Permutation zu finden.
http://www.cut-the-knot.org/do_you_know/ AllPerm.shtml
C ++ und Python haben eingebaute in next_permutation und itertools.permutations Funktionen jeweils
Hier ist eine rein funktionale F # -Implementierung:
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 }
Die Leistung kann erheblich Swap verbessert werden, indem die Vorteile der wandelbaren Natur des CLR-Arrays zu nehmen, aber diese Implementierung ist die Threadsicherheit in Bezug auf das Source-Array und das kann in manchen Kontexten wünschenswert sein. Auch bei Arrays mit mehr als 16 Elementen int müssen Typen mit mehr / beliebig genau wie faktorielle 17 führt zu einem Überlauf int32 ersetzt werden.
Hier ist eine einfache Lösung in c # Rekursion verwenden,
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)));
}
}
}
Hier ist ein einfaches permutaion Funktion sowohl für String und Integer als Eingabe zu verstehen. Mit diesem Sie können sogar Ihre Ausgangslänge eingestellt (die im Normalfall ist es gleich Eingabelänge)
String
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);
}
und Integer nur die Anrufer Methode ändern und MakePermutations () bleibt unberührt:
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>();
}
Beispiel 1: GetAllPermutations ( "abc", 3); "Abc" "acb" "bac" "BCA" "cab" "cba"
Beispiel 2: GetAllPermutations ( "ABCD", 2); "Ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"
Beispiel 3: GetAllPermutations (486,2); 48 46 84 86 64 68
class Program
{
public static void Main(string[] args)
{
Permutation("abc");
}
static void Permutation(string rest, string prefix = "")
{
if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);
// Each letter has a chance to be permutated
for (int i = 0; i < rest.Length; i++)
{
Permutation(rest.Remove(i, 1), prefix + rest[i]);
}
}
}
Hier ist die Funktion, die alle permutaion gedruckt wird. Diese Funktion implementiert Logik Erläutert von 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();
}
Die unten ist meine Umsetzung der Permutation. Sie nicht die Variablennamen kümmern, wie ich es für Spaß zu tun war :)
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;
}
}
Hier ist ein hohes Maß Beispiel, das ich schrieb, die die die menschliche Sprache zeigt Erklärung Peter gab:
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;
}
Wenn die Leistung und Speicher ein Problem ist, schlage ich diese sehr effiziente Implementierung. Nach Heap-Algorithmus in Wikipedia , sollte es die schnellste sein. Hoffe, es wird passt Ihren Bedarf :-)!
Wie Vergleich dieser mit einer Linq-Implementierung für 10! (Code enthalten):
- Dieses: 36288000 Artikel in 235 millisecs
-
Linq: 36288000 Artikel in 50051 millisecs
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's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 /// </summary> public static class Permutations { /// <summary> /// Heap's 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"); } } }
Hier ist meine Lösung in JavaScript (NodeJS). Die Hauptidee ist, dass wir ein Element in einer Zeit nehmen „entfernen Sie sie“ aus der Zeichenfolge, variieren den Rest der Charaktere, und fügen Sie das Element an der Front.
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;
Und hier sind die Tests:
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);
})
})
})
Hier ist die einfachste Lösung, die ich denken kann:
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
Die distribute Funktion nimmt ein neues Element und ein e n-Elementliste und gibt eine Liste von n+1 Listen, von denen jede an einer anderen Stelle eingefügt e hat. Zum Beispiel 10 an jedem der vier möglichen Plätze in der Liste [1;2;3] einfügen:
> 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]]
Die permute Funktion faltet sich über jedes Element wiederum die Permutationen der Verteilung über so weit angesammelt hat, in allen Permutationen gipfelte. Zum Beispiel kann die 6 Permutationen der Liste [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]]
Ändern die fold zu einem scan, um die Zwischenspeicher zu halten, werfen ein Licht auf, wie die Permutationen ein Element zu einem Zeitpunkt erzeugt werden:
> 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]]]
Listen Permutationen einer Zeichenkette. Vermeidet Vervielfältigung, wenn Zeichen wiederholt werden:
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);
}
}
Hier ist die Funktion, die alle Permutationen rekursiv gedruckt werden.
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;
}
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);
}
}
Hier ist eine C # Antwort, die ein wenig vereinfacht wird.
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;
}
Ausgabe:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Das ist meine Lösung, die es einfach für mich zu verstehen,
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 });
}
Hier ist eine weitere Umsetzung der algo erwähnt.
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();
}
}
//Generic C# Method
private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
{
var perms = new List<T[]>();
var l = input.Length - 1;
if (l == startIndex)
perms.Add(input);
else
{
for (int i = startIndex; i <= l; i++)
{
var copy = input.ToArray(); //make copy
var temp = copy[startIndex];
copy[startIndex] = copy[i];
copy[i] = temp;
perms.AddRange(GetPerms(copy, startIndex + 1));
}
}
return perms;
}
//usages
char[] charArray = new char[] { 'A', 'B', 'C' };
var charPerms = GetPerms(charArray);
string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
var stringPerms = GetPerms(stringArray);
int[] intArray = new int[] { 1, 2, 3 };
var intPerms = GetPerms(intArray);
/// <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);
}
}
