Erzeugen Sie eine Liste aller möglichen Permutationen einer Zeichenfolge
https://stackoverflow.com/questions/361
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie würde ich vorgehen, um eine Liste aller möglichen Permutationen einer Zeichenfolge mit einer Länge zwischen x und y Zeichen zu erstellen, die eine variable Liste von Zeichen enthält?
Jede Sprache würde funktionieren, aber sie sollte portierbar sein.
Lösung
Dafür gibt es mehrere Möglichkeiten.Gängige Methoden verwenden Rekursion, Memoisierung oder dynamische Programmierung.Die Grundidee besteht darin, dass Sie eine Liste aller Zeichenfolgen der Länge 1 erstellen und dann in jeder Iteration für alle in der letzten Iteration erstellten Zeichenfolgen diese Zeichenfolge hinzufügen, die mit jedem Zeichen in der Zeichenfolge einzeln verkettet ist.(Der Variablenindex im folgenden Code verfolgt den Beginn der letzten und der nächsten Iteration.)
Etwas Pseudocode:
list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
index = (index[1], len(list))
for string s in list.subset(index[0] to end):
for character c in originalString:
list.add(s + c)
Sie müssten dann alle Zeichenfolgen mit einer Länge von weniger als x entfernen. Dies sind die ersten (x-1) * len(originalString)-Einträge in der Liste.
Andere Tipps
Es ist besser, Backtracking zu verwenden
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}
Du wirst viele Saiten bekommen, das ist sicher ...
\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
Wobei x und y die Art sind, wie Sie sie definieren, und r die Anzahl der Zeichen ist, aus denen wir auswählen – wenn ich Sie richtig verstehe.Sie sollten diese auf jeden Fall nach Bedarf generieren und nicht nachlässig werden und beispielsweise ein Powerset generieren und dann die Länge der Strings filtern.
Das Folgende ist definitiv nicht der beste Weg, diese zu generieren, aber es ist dennoch ein interessanter Nebenbemerkung.
Knuth (Band 4, Faszikel 2, 7.2.1.3) sagt uns, dass die (s,t)-Kombination äquivalent zu s+1 Dingen ist, die t auf einmal mit Wiederholung aufgenommen werden – eine (s,t)-Kombination ist die Notation, die von verwendet wird Knuth, das ist gleich {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Wir können dies herausfinden, indem wir zunächst jede (s,t)-Kombination in binärer Form (also mit der Länge (s+t)) erzeugen und die Anzahl der Nullen links von jeder Eins zählen.
10001000011101 --> wird zur Permutation:{0, 3, 4, 4, 4, 1}
Nicht rekursive Lösung nach Knuth, Python-Beispiel:
def nextPermutation(perm):
k0 = None
for i in range(len(perm)-1):
if perm[i]<perm[i+1]:
k0=i
if k0 == None:
return None
l0 = k0+1
for i in range(k0+1, len(perm)):
if perm[k0] < perm[i]:
l0 = i
perm[k0], perm[l0] = perm[l0], perm[k0]
perm[k0+1:] = reversed(perm[k0+1:])
return perm
perm=list("12345")
while perm:
print perm
perm = nextPermutation(perm)
Vielleicht schauen Sie sich „Effizientes Aufzählen der Teilmengen einer Menge", der einen Algorithmus beschreibt, der einen Teil Ihrer Wünsche erfüllt – schnell alle Teilmengen von N Zeichen von der Länge x bis y generieren.Es enthält eine Implementierung in C.
Für jede Teilmenge müssten Sie immer noch alle Permutationen generieren.Wenn Sie beispielsweise 3 Zeichen von „abcde“ benötigen, erhalten Sie mit diesem Algorithmus „abc“, „abd“, „abe“ ...aber Sie müssten jedes einzelne permutieren, um „acb“, „bac“, „bca“ usw. zu erhalten.
Einige funktionierende Java-Codes basieren auf Sarps Antwort:
public class permute {
static void permute(int level, String permuted,
boolean used[], String original) {
int length = original.length();
if (level == length) {
System.out.println(permuted);
} else {
for (int i = 0; i < length; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i),
used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "hello";
boolean used[] = {false, false, false, false, false};
permute(0, "", used, s);
}
}
Hier ist eine einfache Lösung in C#.
Es generiert nur die unterschiedlichen Permutationen einer bestimmten Zeichenfolge.
static public IEnumerable<string> permute(string word)
{
if (word.Length > 1)
{
char character = word[0];
foreach (string subPermute in permute(word.Substring(1)))
{
for (int index = 0; index <= subPermute.Length; index++)
{
string pre = subPermute.Substring(0, index);
string post = subPermute.Substring(index);
if (post.Contains(character))
continue;
yield return pre + character + post;
}
}
}
else
{
yield return word;
}
}
Hier gibt es viele gute Antworten.Ich schlage auch eine sehr einfache rekursive Lösung in C++ vor.
#include <string>
#include <iostream>
template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
if (start == s.length()) consume(s);
for (std::size_t i = start; i < s.length(); i++) {
std::swap(s[start], s[i]);
permutations(s, consume, start + 1);
}
}
int main(void) {
std::string s = "abcd";
permutations(s, [](std::string s) {
std::cout << s << std::endl;
});
}
Notiz:Zeichenfolgen mit wiederholten Zeichen erzeugen keine eindeutigen Permutationen.
Ich habe mir das gerade schnell in Ruby ausgedacht:
def perms(x, y, possible_characters)
all = [""]
current_array = all.clone
1.upto(y) { |iteration|
next_array = []
current_array.each { |string|
possible_characters.each { |c|
value = string + c
next_array.insert next_array.length, value
all.insert all.length, value
}
}
current_array = next_array
}
all.delete_if { |string| string.length < x }
end
Sie könnten in der Sprach-API nach integrierten Permutationstypfunktionen suchen und möglicherweise optimierteren Code schreiben, aber wenn die Zahlen so hoch sind, bin ich mir nicht sicher, ob es einen großen Weg gibt, viele Ergebnisse zu erzielen .
Wie auch immer, die Idee hinter dem Code besteht darin, mit einer Zeichenfolge der Länge 0 zu beginnen und dann alle Zeichenfolgen der Länge Z im Auge zu behalten, wobei Z die aktuelle Größe in der Iteration ist.Gehen Sie dann jede Zeichenfolge durch und hängen Sie jedes Zeichen an jede Zeichenfolge an.Entfernen Sie am Ende alle Werte, die unter dem x-Schwellenwert lagen, und geben Sie das Ergebnis zurück.
Ich habe es nicht mit potenziell bedeutungslosen Eingaben getestet (Liste mit Nullzeichen, seltsame Werte von x und y usw.).
Dies ist eine Übersetzung von Mikes Ruby-Version in Common Lisp:
(defun perms (x y original-string)
(loop with all = (list "")
with current-array = (list "")
for iteration from 1 to y
do (loop with next-array = nil
for string in current-array
do (loop for c across original-string
for value = (concatenate 'string string (string c))
do (push value next-array)
(push value all))
(setf current-array (reverse next-array)))
finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))
Und eine weitere Version, etwas kürzer und mit mehr Loop-Funktionen:
(defun perms (x y original-string)
(loop repeat y
collect (loop for string in (or (car (last sets)) (list ""))
append (loop for c across original-string
collect (concatenate 'string string (string c)))) into sets
finally (return (loop for set in sets
append (loop for el in set when (>= (length el) x) collect el)))))
Hier ist eine einfache rekursive C#-Wortlösung:
Methode:
public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
{
bool finished = true;
ArrayList newWords = new ArrayList();
if (words.Count == 0)
{
foreach (string letter in letters)
{
words.Add(letter);
}
}
for(int j=index; j<words.Count; j++)
{
string word = (string)words[j];
for(int i =0; i<letters.Length; i++)
{
if(!word.Contains(letters[i]))
{
finished = false;
string newWord = (string)word.Clone();
newWord += letters[i];
newWords.Add(newWord);
}
}
}
foreach (string newWord in newWords)
{
words.Add(newWord);
}
if(finished == false)
{
CalculateWordPermutations(letters, words, words.Count - newWords.Count);
}
return words;
}
Berufung:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Wenn Sie sich in Perl auf die Kleinschreibung beschränken möchten, können Sie Folgendes tun:
my @result = ("a" .. "zzzz");
Dies ergibt alle möglichen Zeichenfolgen zwischen 1 und 4 Zeichen mit Kleinbuchstaben.Für Großbuchstaben ändern "a" Zu "A" Und "zzzz" Zu "ZZZZ".
Für gemischte Groß- und Kleinschreibung wird es viel schwieriger und mit einem der in Perl integrierten Operatoren wie diesem wahrscheinlich nicht machbar.
...und hier ist die C-Version:
void permute(const char *s, char *out, int *used, int len, int lev)
{
if (len == lev) {
out[lev] = '\0';
puts(out);
return;
}
int i;
for (i = 0; i < len; ++i) {
if (! used[i])
continue;
used[i] = 1;
out[lev] = s[i];
permute(s, out, used, len, lev + 1);
used[i] = 0;
}
return;
}
permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*AChr.), (BAC), (v. ChrA*), (*ACB), (CAB), (CBA*)] Um Duplikate zu entfernen, wenn jedes Alphabet -Überprüfung einfügt, um festzustellen, ob die vorherige Zeichenfolge mit demselben Alphabet endet (warum?-Übung)
public static void main(String[] args) {
for (String str : permStr("ABBB")){
System.out.println(str);
}
}
static Vector<String> permStr(String str){
if (str.length() == 1){
Vector<String> ret = new Vector<String>();
ret.add(str);
return ret;
}
char start = str.charAt(0);
Vector<String> endStrs = permStr(str.substring(1));
Vector<String> newEndStrs = new Vector<String>();
for (String endStr : endStrs){
for (int j = 0; j <= endStr.length(); j++){
if (endStr.substring(0, j).endsWith(String.valueOf(start)))
break;
newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
}
}
return newEndStrs;
}
Druckt alle Permutationen ohne Duplikate
Ruby-Antwort, die funktioniert:
class String
def each_char_with_index
0.upto(size - 1) do |index|
yield(self[index..index], index)
end
end
def remove_char_at(index)
return self[1..-1] if index == 0
self[0..(index-1)] + self[(index+1)..-1]
end
end
def permute(str, prefix = '')
if str.size == 0
puts prefix
return
end
str.each_char_with_index do |char, index|
permute(str.remove_char_at(index), prefix + char)
end
end
# example
# permute("abc")
Rekursive Lösung in C++
int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}
Die folgende Java-Rekursion gibt alle Permutationen einer bestimmten Zeichenfolge aus:
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() != 0){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
System.out.println(str1);
}
}
Es folgt die aktualisierte Version der oben genannten „permut“-Methode, die n!(n faktoriell) weniger rekursive Aufrufe im Vergleich zur obigen Methode
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() > 1){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
System.out.println(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}
}
import java.util.*;
public class all_subsets {
public static void main(String[] args) {
String a = "abcd";
for(String s: all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
HashSet<String> ret_set = new HashSet<String>();
for(String s: lst) {
ret_set.add(c+s);
}
return ret_set;
}
public static HashSet<String> all_perm(String a) {
HashSet<String> set = new HashSet<String>();
if(a.length() == 1) {
set.add(a);
} else {
for(int i=0; i<a.length(); i++) {
set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
}
}
return set;
}
}
Hier ist eine nicht rekursive Version, die ich mir ausgedacht habe, in Javascript.Es basiert nicht auf Knuths nicht-rekursivem oben, obwohl es einige Ähnlichkeiten beim Elementaustausch aufweist.Ich habe die Richtigkeit für Eingabearrays mit bis zu 8 Elementen überprüft.
Eine schnelle Optimierung wäre das Preflighting out Array und Vermeiden push().
Die Grundidee ist:
Generieren Sie anhand eines einzelnen Quellarrays einen ersten neuen Satz von Arrays, die nacheinander das erste Element mit jedem nachfolgenden Element austauschen und dabei die anderen Elemente jedes Mal unberührt lassen.z.B:gegeben 1234, generieren 1234, 2134, 3214, 4231.
Verwenden Sie jedes Array aus dem vorherigen Durchgang als Samen für einen neuen Pass, aber anstatt das erste Element auszutauschen, tauschen Sie das zweite Element mit jedem nachfolgenden Element aus.Fügen Sie dieses Mal außerdem nicht das ursprüngliche Array in die Ausgabe ein.
Wiederholen Sie Schritt 2, bis Sie fertig sind.
Hier ist das Codebeispiel:
function oxe_perm(src, depth, index)
{
var perm = src.slice(); // duplicates src.
perm = perm.split("");
perm[depth] = src[index];
perm[index] = src[depth];
perm = perm.join("");
return perm;
}
function oxe_permutations(src)
{
out = new Array();
out.push(src);
for (depth = 0; depth < src.length; depth++) {
var numInPreviousPass = out.length;
for (var m = 0; m < numInPreviousPass; ++m) {
for (var n = depth + 1; n < src.length; ++n) {
out.push(oxe_perm(out[m], depth, n));
}
}
}
return out;
}
Ich bin mir nicht sicher, warum Sie das überhaupt tun möchten.Die resultierende Menge für alle mäßig großen Werte von x und y wird riesig sein und exponentiell wachsen, wenn x und/oder y größer werden.
Nehmen wir an, Ihr Satz möglicher Zeichen besteht aus den 26 Kleinbuchstaben des Alphabets und Sie bitten Ihre Anwendung, alle Permutationen mit der Länge = 5 zu generieren.Vorausgesetzt, dass Ihnen der Speicher nicht ausgeht, erhalten Sie 11.881.376 (d. h.26 hoch 5) Saiten zurück.Wenn Sie die Länge auf 6 erhöhen, erhalten Sie 308.915.776 Saiten zurück.Diese Zahlen werden sehr schnell schmerzhaft groß.
Hier ist eine Lösung, die ich in Java zusammengestellt habe.Sie müssen zwei Laufzeitargumente angeben (entsprechend x und y).Viel Spaß.
public class GeneratePermutations {
public static void main(String[] args) {
int lower = Integer.parseInt(args[0]);
int upper = Integer.parseInt(args[1]);
if (upper < lower || upper == 0 || lower == 0) {
System.exit(0);
}
for (int length = lower; length <= upper; length++) {
generate(length, "");
}
}
private static void generate(int length, String partial) {
if (length <= 0) {
System.out.println(partial);
} else {
for (char c = 'a'; c <= 'z'; c++) {
generate(length - 1, partial + c);
}
}
}
}
Ich brauchte das heute, und obwohl die bereits gegebenen Antworten mich in die richtige Richtung wiesen, waren sie nicht ganz das, was ich wollte.
Hier ist eine Implementierung mit der Heap-Methode.Die Länge des Arrays muss mindestens 3 betragen und darf aus praktischen Gründen nicht größer als etwa 10 sein, je nachdem, was Sie tun möchten, Geduld und Taktrate.
Bevor Sie Ihre Schleife betreten, initialisieren Sie sie Perm(1 To N) mit der ersten Permutation, Stack(3 To N) mit Nullen* und Level mit 2**.Am Ende des Schleifenaufrufs NextPerm, was false zurückgibt, wenn wir fertig sind.
* VB erledigt das für Sie.
** Sie können NextPerm ein wenig ändern, um dies unnötig zu machen, aber so ist es klarer.
Option Explicit
Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
Swap Perm(1), Perm(2)
Level = 3
Else
While Stack(Level) = Level - 1
Stack(Level) = 0
If Level = UBound(Stack) Then Exit Function
Level = Level + 1
Wend
Stack(Level) = Stack(Level) + 1
If Level And 1 Then N = 1 Else N = Stack(Level)
Swap Perm(N), Perm(Level)
Level = 2
End If
NextPerm = True
End Function
Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub
'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
If CurrentY + TextHeight("0") > ScaleHeight Then
ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
CurrentY = 0
CurrentX = 0
End If
T = vbNullString
For I = 1 To UBound(A)
Print A(I);
T = T & Hex(A(I))
Next
Print
Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
J = J * I
Next
If J <> Test.Count Then Stop
End Sub
Andere Methoden werden von verschiedenen Autoren beschrieben.Knuth beschreibt zwei, eines gibt lexikalische Ordnung vor, ist aber komplex und langsam, das andere ist als Methode der einfachen Änderungen bekannt.Jie Gao und Dianjun Wang haben ebenfalls einen interessanten Artikel geschrieben.
In Rubin:
str = "a"
100_000_000.times {puts str.next!}
Es geht ziemlich schnell, aber es wird einige Zeit dauern =).Natürlich können Sie auch mit „aaaaaaaa“ beginnen, wenn Sie die kurzen Zeichenfolgen nicht interessieren.
Möglicherweise habe ich die eigentliche Frage jedoch falsch interpretiert – in einem der Beiträge klang es so, als ob Sie nur eine Brute-Force-Bibliothek mit Zeichenfolgen benötigen würden, aber in der Hauptfrage hört es sich so an, als müssten Sie eine bestimmte Zeichenfolge permutieren.
Ihr Problem ähnelt in gewisser Weise diesem: http://beust.com/weblog/archives/000491.html (Listen Sie alle ganzen Zahlen auf, bei denen sich keine der Ziffern wiederholt, was dazu führte, dass eine ganze Reihe von Sprachen das Problem lösten, wobei der Ocaml-Typ Permutationen verwendete und ein Java-Typ noch eine andere Lösung verwendete.)
Dieser Code in Python, wenn er mit aufgerufen wird allowed_characters einstellen [0,1] und maximal 4 Zeichen würden 2^4 Ergebnisse generieren:
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
def generate_permutations(chars = 4) :
#modify if in need!
allowed_chars = [
'0',
'1',
]
status = []
for tmp in range(chars) :
status.append(0)
last_char = len(allowed_chars)
rows = []
for x in xrange(last_char ** chars) :
rows.append("")
for y in range(chars - 1 , -1, -1) :
key = status[y]
rows[x] = allowed_chars[key] + rows[x]
for pos in range(chars - 1, -1, -1) :
if(status[pos] == last_char - 1) :
status[pos] = 0
else :
status[pos] += 1
break;
return rows
import sys
print generate_permutations()
Ich hoffe, das ist für Sie von Nutzen.Funktioniert mit jedem Zeichen, nicht nur mit Zahlen
Hier ist ein Link, der beschreibt, wie Permutationen einer Zeichenfolge gedruckt werden.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Obwohl dies Ihre Frage nicht genau beantwortet, gibt es hier eine Möglichkeit, jede Permutation der Buchstaben aus einer Reihe von Zeichenfolgen gleicher Länge zu generieren:Wenn Ihre Wörter beispielsweise „Kaffee“, „Joomla“ und „Moodle“ lauten, können Sie eine Ausgabe wie „Coodle“, „Joodee“, „Joffle“ usw. erwarten.
Grundsätzlich beträgt die Anzahl der Kombinationen (Anzahl der Wörter) hoch (Anzahl der Buchstaben pro Wort).Wählen Sie also eine Zufallszahl zwischen 0 und der Anzahl der Kombinationen - 1, wandeln Sie diese Zahl in eine Basiszahl (Anzahl der Wörter) um und verwenden Sie dann jede Ziffer dieser Zahl als Indikator dafür, aus welchem Wort der nächste Buchstabe entnommen werden soll.
z.B:im obigen Beispiel.3 Wörter, 6 Buchstaben = 729 Kombinationen.Wählen Sie eine Zufallszahl:465.In Basis 3 umrechnen:122020.Nehmen Sie den ersten Buchstaben von Wort 1, den 2. von Wort 2, den 3. von Wort 2, den 4. von Wort 0 ...und du bekommst...„joofle“.
Wenn Sie alle Permutationen möchten, durchlaufen Sie einfach eine Schleife von 0 bis 728.Wenn Sie nur einen zufälligen Wert auswählen, ist das natürlich sehr viel einfacher Eine weniger verwirrende Möglichkeit wäre, die Buchstaben in einer Schleife zu durchlaufen.Mit dieser Methode können Sie eine Rekursion vermeiden, wenn Sie alle Permutationen haben möchten, und es sieht so aus, als ob Sie sich mit Mathematik auskennen(tm)!
Wenn die Anzahl der Kombinationen zu groß ist, können Sie sie in eine Reihe kleinerer Wörter aufteilen und diese am Ende verketten.
c# iterativ:
public List<string> Permutations(char[] chars)
{
List<string> words = new List<string>();
words.Add(chars[0].ToString());
for (int i = 1; i < chars.Length; ++i)
{
int currLen = words.Count;
for (int j = 0; j < currLen; ++j)
{
var w = words[j];
for (int k = 0; k <= w.Length; ++k)
{
var nstr = w.Insert(k, chars[i].ToString());
if (k == 0)
words[j] = nstr;
else
words.Add(nstr);
}
}
}
return words;
}
Es gibt eine iterative Java-Implementierung in GelegentlichMathe (funktioniert für eine Liste von Objekten):
/**
* Generate the indices into the elements array for the next permutation. The
* algorithm is from Kenneth H. Rosen, Discrete Mathematics and its
* Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
*/
private void generateNextPermutationIndices()
{
if (remainingPermutations == 0)
{
throw new IllegalStateException("There are no permutations " +
"remaining. Generator must be reset to continue using.");
}
else if (remainingPermutations < totalPermutations)
{
// Find largest index j with
// permutationIndices[j] < permutationIndices[j + 1]
int j = permutationIndices.length - 2;
while (permutationIndices[j] > permutationIndices[j + 1])
{
j--;
}
// Find index k such that permutationIndices[k] is smallest integer
// greater than permutationIndices[j] to the right
// of permutationIndices[j].
int k = permutationIndices.length - 1;
while (permutationIndices[j] > permutationIndices[k])
{
k--;
}
// Interchange permutation indices.
int temp = permutationIndices[k];
permutationIndices[k] = permutationIndices[j];
permutationIndices[j] = temp;
// Put tail end of permutation after jth position in increasing order.
int r = permutationIndices.length - 1;
int s = j + 1;
while (r > s)
{
temp = permutationIndices[s];
permutationIndices[s] = permutationIndices[r];
permutationIndices[r] = temp;
r--;
s++;
}
}
--remainingPermutations;
}
/**
* Generate the next permutation and return a list containing
* the elements in the appropriate order. This overloaded method
* allows the caller to provide a list that will be used and returned.
* The purpose of this is to improve performance when iterating over
* permutations. If the {@link #nextPermutationAsList()} method is
* used it will create a new list every time. When iterating over
* permutations this will result in lots of short-lived objects that
* have to be garbage collected. This method allows a single list
* instance to be reused in such circumstances.
* @param destination Provides a list to use to create the
* permutation. This is the list that will be returned, once
* it has been filled with the elements in the appropriate order.
* @return The next permutation as a list.
*/
public List<T> nextPermutationAsList(List<T> destination)
{
generateNextPermutationIndices();
// Generate actual permutation.
destination.clear();
for (int i : permutationIndices)
{
destination.add(elements[i]);
}
return destination;
}
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list
def func( x,i,j ): #returns x[i..j]
z = ''
for i in range(i,j+1):
z = z+x[i]
return z
def perm( x , length , list ): #perm function
if length == 1 : # base case
list.append( x[len(x)-1] )
return list
else:
lists = perm( x , length-1 ,list )
lists_temp = lists #temporarily storing the list
lists = []
for i in range( len(lists_temp) ) :
list_temp = gen(lists_temp[i],x[length-2],lists)
lists += list_temp
return lists
def permutation(str)
posibilities = []
str.split('').each do |char|
if posibilities.size == 0
posibilities[0] = char.downcase
posibilities[1] = char.upcase
else
posibilities_count = posibilities.length
posibilities = posibilities + posibilities
posibilities_count.times do |i|
posibilities[i] += char.downcase
posibilities[i+posibilities_count] += char.upcase
end
end
end
posibilities
end
Hier ist meine Meinung zu einer nicht rekursiven Version
Die Python-Lösung:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
