Generieren Liste aller möglichen Permutationen einer Zeichenkette

stimmen
143

Wie würde ich mich über eine Liste aller möglichen Permutationen einer Zeichenkette zwischen x und y Zeichen Länge zu erzeugen, eine variable Liste von Zeichen enthält.

Jede Sprache funktionieren würde, aber es sollte tragbar sein.

Veröffentlicht am 02/08/2008 um 07:57
quelle vom benutzer
In anderen Sprachen...                            


35 antworten

stimmen
67

Es gibt mehrere Möglichkeiten, dies zu tun. Gängige Methoden verwenden Rekursion, memoization oder dynamische Programmierung. Die Grundidee ist, dass Sie eine Liste aller Strings der Länge 1, dann in jeder Iteration erzeugen, für alle Strings in der letzten Iteration erzeugt wird, die Zeichenfolge hinzufügen individuell mit jedem Zeichen in der Zeichenfolge verkettet. (Die Variable Index in der nachfolgenden Code verfolgt den Beginn der letzten und der nächsten Iteration)

Einige Pseudo-Code:

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 würden dann alle Saiten weniger als x Länge entfernen müssen, werden Sie sich die ersten (x-1) * len (originalString) Einträge in der Liste.

Beantwortet am 02/08/2008 um 08:48
quelle vom benutzer

stimmen
35

Es ist besser Rückzieher 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;
}
Beantwortet am 10/01/2012 um 19:00
quelle vom benutzer

stimmen
24

Sie werden eine Menge von Zeichenketten bekommen, das ist sicher ...

\ sum_ {i = x ^ y} {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7BR% 7D% 7B% 7B (ri)% 7D% 7D% 20% 7D!
Wo, x und y , wie definieren Sie sie und r ist die Anzahl der Zeichen wir sind der Auswahl - -Wenn ich verstehe Sie richtig. Sie sollten auf jeden Fall diese nach Bedarf erzeugen und nicht schlampig und sagen, eine Powerset erzeugen und dann die Länge von Strings filtern.

Das folgende ist definitiv nicht der beste Weg, diese zu erzeugen, aber es ist eine interessante Seite, none-the-less.

Knuth (Band 4, Faszikel 2, 7.2.1.3) sagt uns , dass (s, t) zu -combination s + 1 Dinge entsprechen t zu einem Zeitpunkt mit Wiederholung genommen - ein (s, t) -combination Notation wird verwendet , um Knuth , die gleich {t \ wählen {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Das können wir herausfinden , indem zuerst jede (s, t) -combination in binärer Form zu erzeugen (also der Länge (s + t)) und durch Zählen der Anzahl von 0 links von je 1.

10001000011101 -> wird die Vertauschung: {0, 3, 4, 4, 4, 1}

Beantwortet am 05/08/2008 um 05:57
quelle vom benutzer

stimmen
14

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)
Beantwortet am 09/11/2010 um 14:58
quelle vom benutzer

stimmen
12

Es gibt hier viele gute Antworten. Ich schlage vor, auch eine sehr einfache rekursive Lösung in C ++.

#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;
    });
}

Hinweis : Strings mit wiederholten Zeichen nicht eindeutige Permutationen erzeugen.

Beantwortet am 08/01/2014 um 12:00
quelle vom benutzer

stimmen
12

Hier ist eine einfache Lösung in C #.

Es erzeugt nur die unterschiedlichen Permutationen einer gegebenen Zeichenkette.

    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;
        }
    }
Beantwortet am 05/07/2010 um 10:06
quelle vom benutzer

stimmen
12

Einige arbeiten Java - Code auf Basis von Sarp 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);
    }
}
Beantwortet am 04/04/2010 um 19:18
quelle vom benutzer

stimmen
12

Sie könnten sehen „ Effizientes die Teilmengen einer Menge Auflisten “, die einen Algorithmus Teil zu tun , beschreibt , was Sie wollen - erzeugen schnell alle Teilmengen von N Zeichen aus Länge x bis y. Es enthält eine Implementierung in C.

Für jede Teilmenge, dann würden Sie noch alle Permutationen zu generieren. Zum Beispiel, wenn Sie wollten 3 Zeichen „ABCDE“, dieser Algorithmus würde Ihnen „abc“, „abd“, „abe“ ... aber Sie würden jeder permutieren haben zu bekommen „acb“, „bac“, „BCA“ usw.

Beantwortet am 14/11/2008 um 20:36
quelle vom benutzer

stimmen
8

Ich peitschte nur das oben schnell in Ruby:

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 Sprache API suchen in Permutation Typ Funktionen eingebaut, und Sie könnten mehr optimiertem Code schreiben können, aber wenn die Zahlen allzu hoch sind, ich bin nicht sicher, dass es viel von einer Art und Weise ist um eine Menge von Ergebnissen mit .

Wie auch immer, die Idee hinter dem Code ist mit String der Länge 0 beginnen, dann behalten den Überblick über alle Strings der Länge Z, wobei Z die aktuelle Größe in der Iteration ist. Dann gehen Sie durch jede Zeichenfolge und fügen Sie jedes Zeichen auf jeden String. Schließlich am Ende, entfernen Sie alle, die unterhalb der Schwelle x waren und das Ergebnis zurück.

Ich habe es nicht getestet mit potentiell bedeutungslosem Eingang (Nullzeichen Liste, seltsamen Werte von x und y, etc).

Beantwortet am 02/08/2008 um 08:56
quelle vom benutzer

stimmen
7

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")
Beantwortet am 20/04/2012 um 01:21
quelle vom benutzer

stimmen
7

permute (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (C B * )] -> [( * A BC ), (B A C), (BC A * ), ( * A CB), (C A B), (CB A * )] Duplikate zu entfernen , wenn jedes Alphabet Rückschlag Einsetzen mit dem gleichen Alphabet zu sehen , ob vorheriger Zeichenfolge 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 sans Duplikate

Beantwortet am 22/02/2011 um 19:45
quelle vom benutzer

stimmen
7

... 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;
}
Beantwortet am 07/02/2011 um 22:56
quelle vom benutzer

stimmen
7

In Perl, wenn Sie sich auf die Kleinbuchstaben beschränken möchten, können Sie dies tun:

my @result = ("a" .. "zzzz");

Dies gibt alle möglichen Zeichenketten zwischen 1 und 4 Zeichen in Kleinbuchstaben. Für Groß, ändern "a"zu "A"und "zzzz"zu "ZZZZ".

Für Groß- und Kleinschreibung wird es viel schwieriger, und wahrscheinlich nicht machbar mit einem von Perl eingebauter Operatoren so.

Beantwortet am 15/02/2009 um 11:02
quelle vom benutzer

stimmen
7

Hier ist ein einfaches Wort C # rekursive Lö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);
Beantwortet am 20/10/2008 um 01:17
quelle vom benutzer

stimmen
7

Recursive-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;
            }
        }
}
Beantwortet am 29/09/2008 um 02:34
quelle vom benutzer

stimmen
7

Dies ist eine Übersetzung von Mike 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 andere Version, etwas kürzer und Loop-Anlage Funktionen verwenden:

(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)))))
Beantwortet am 16/09/2008 um 06:15
quelle vom benutzer

stimmen
6

Die folgenden Java Rekursion druckt alle Permutationen einer gegebenen Zeichenkette:

//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);
    }
}

Im Anschluss ist die aktualisierte Version von oben „PERMUT“ Methode, die n macht! (N Fakultät) weniger rekursive Aufrufe im Vergleich zu dem oben beschriebenen Verfahren

//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()));
   }
}
Beantwortet am 19/06/2013 um 05:23
quelle vom benutzer

stimmen
5

Hier ist eine nicht-rekursive Version kam ich mit, in Javascript. Es ist nicht oben auf Knuths nicht-rekursive einer Basis, obwohl es einige Ähnlichkeiten in Elemente Swapping hat. Ich habe seine Richtigkeit für die Eingabe-Arrays von bis zu 8 Elementen überprüft.

Eine schnelle Optimierung würde Preflighten die outAnordnung und die Vermeidung push().

Die Grundidee ist:

  1. Gegeben Array eine einzelne Quelle, erzeugen ein erster Satz von Arrays, die das erste Element mit jedem nachfolgenden Element wiederum tauschen, jedes Mal ungestörte die anderen Elemente zu verlassen. zB: Da 1234 generiert 1234, 2134, 3214, 4231.

  2. Verwenden jedes Array aus dem vorhergehenden Durchlauf als Keim für einen neuen Durchlauf, sondern das erste Elements Swapping, tauscht das zweite Element mit jedem nachfolgenden Elemente. Auch diesmal, beinhaltet nicht den Original-Array in der Ausgabe.

  3. Wiederholen Sie Schritt 2 bis getan.

Hier ist der Code Beispiel:

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;
}
Beantwortet am 03/08/2011 um 08:11
quelle vom benutzer

stimmen
5
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;
    }
}
Beantwortet am 24/10/2010 um 23:01
quelle vom benutzer

stimmen
4

Ich bin mir nicht sicher, warum diese in erster Linie tun möchte. Der resultierende Satz für alle mäßig großen Werte von x und y wird sehr groß sein, und wird exponentiell wachsen als x und / oder y größer.

Nehmen wir an Ihre Gruppe von möglichen Zeichen die 26 Kleinbuchstaben des Alphabets ist, und Sie Ihre Anwendung bitten alle Permutationen zu erzeugen, wobei die Länge = 5. Sie laufen nicht aus dem Speicher Angenommen, Sie 11.881.376 (dh 26 an die Macht bekommen von 5) Strings zurück. Beule, die Länge bis zu 6, und Sie werden 308.915.776 Strings zurück. Diese Zahlen erhalten schmerzlich groß, sehr schnell.

Hier ist eine Lösung, die ich zusammen in Java. Sie müssen zwei Laufzeit Argumente liefern (entsprechend x und y). Habe 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);
            }
        }
    }
}
Beantwortet am 02/08/2008 um 10:40
quelle vom benutzer

stimmen
3

Ich brauchte diese heute, und obwohl die Antworten schon wies mich in die richtige Richtung gegeben, sie waren nicht ganz das, was ich wollte.

Hier ist eine Implementierung Heap-Methode. Die Länge des Arrays muss mindestens 3 und aus praktischen Erwägungen wird nicht größer als 10 oder so sein, je nachdem, was Sie tun wollen, Geduld und die Taktfrequenz.

Bevor Sie Ihre Schleife eingeben, initialisiert Perm(1 To N)mit der ersten Permutation, Stack(3 To N)mit Nullen * und Levelmit 2**. Am Ende der Schleife Aufruf NextPerm, die falsch zurückkehren wird , wenn wir fertig sind.

* VB wird für Sie das tun.

** Sie können NextPerm ändern, um ein wenig dies unnötig zu machen, aber es ist klarer so.

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 Verfahren werden von verschiedenen Autoren beschrieben. Knuth beschreibt zwei, eine lexikalische Reihenfolge gibt, ist aber komplex und langsam, die andere als die Methode von einfachen Änderungen bekannt sind. Jie Gao und Dianjun Wang schrieb auch ein interessantes Papier.

Beantwortet am 02/10/2011 um 10:13
quelle vom benutzer

stimmen
2

Hier ist ein Link, der beschreibt , wie Permutationen einer Zeichenkette drucken. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Beantwortet am 13/02/2014 um 22:08
quelle vom benutzer

stimmen
2

Dieser Code in Python, wenn sie mit genanntem allowed_charactersSatz [0,1]und 4 Zeichen max, würde 2 ^ 4 Ergebnisse erzeugen:

['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()

Hoffe, dass dies für Sie von Nutzen ist. Funktioniert mit jedem Charakter, nicht nur Zahlen

Beantwortet am 26/05/2011 um 15:22
quelle vom benutzer

stimmen
2

In Rubin:

str = "a"
100_000_000.times {puts str.next!}

Es ist ziemlich schnell, aber es wird einige Zeit in Anspruch nehmen =). Natürlich können Sie bei „aaaaaaaa“ gestartet werden, wenn die kurzen Strings Sie nicht interessant sind.

Ich habe vielleicht die eigentliche Frage aber falsch interpretiert - in einem der Pfosten es klang, als wenn Sie nur eine Brute-Force-Bibliothek von Strings benötigt, aber in der Hauptfrage, es klingt wie Sie eine bestimmte Zeichenfolge permutieren benötigen.

Ihr Problem ist etwas ähnlich wie diese: http://beust.com/weblog/archives/000491.html (Liste alle ganzen Zahlen , in denen keine der Ziffern wiederholen sich, die in einer ganzen Menge von Sprachen führte es mit der Lösung ocaml Kerl Permutationen verwenden und einige Java - Typ noch eine andere Lösung verwendet wird ).

Beantwortet am 15/09/2008 um 18:32
quelle vom benutzer

stimmen
0

Die möglichen String Permutationen können mit rekursiven Funktion berechnet werden. Im Folgenden finden Sie eine der möglichen Lösung.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
Beantwortet am 06/02/2017 um 06:00
quelle vom benutzer

stimmen
0

Code für Java-Sprache geschrieben:

Paket namo.algorithms;

import java.util.Scanner;

public class Permuations {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

Beantwortet am 05/06/2016 um 08:42
quelle vom benutzer

stimmen
0

Nun, hier ist eine elegante, nicht-rekursive, O (n!) Lösung:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }
Beantwortet am 27/06/2015 um 08:44
quelle vom benutzer

stimmen
0

Die pythonic Lösung:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Beantwortet am 13/07/2014 um 08:51
quelle vom benutzer

stimmen
0
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 mein nehmen auf einen nicht rekursiven Version

Beantwortet am 23/01/2014 um 04:28
quelle vom benutzer

stimmen
0

Rekursive Lösung mit Treiber - main()Methode.

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Beantwortet am 19/10/2013 um 02:34
quelle vom benutzer

stimmen
0
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
Beantwortet am 22/08/2013 um 18:51
quelle vom benutzer

stimmen
0

Eine rekursive Lösung in Python. Das Gute an diesem Code ist, dass es ein Wörterbuch, mit Tasten als Strings und alle möglichen Permutationen als Werte exportiert. Alle möglichen Stringlängen sind bereits enthalten, so in der Tat, Sie sind einen Ober zu schaffen.

Wenn Sie nur die letzten Permutationen benötigen, können Sie andere Schlüssel aus dem Wörterbuch löschen.

In diesem Code ist das Wörterbuch der Permutationen global.

An der Basis Fall speichere ich den Wert , da beide Möglichkeiten in einer Liste. perms['ab'] = ['ab','ba'].

Für höhere Saitenlängen bezieht sich die Funktionszeichenlängen und umfasst die zuvor berechneten Permutationen zu senken.

Die Funktion macht zwei Dinge:

  • nennt sich mit einer kleineren Zeichenfolge
  • gibt eine Liste von Permutationen einer bestimmten Zeichenfolge, wenn bereits verfügbar. Wenn sich zurück, werden diese verwendet, um den Charakter zu anhängen und neuere Permutationen erstellen.

Teuer für das Gedächtnis.

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]
Beantwortet am 05/07/2013 um 05:15
quelle vom benutzer

stimmen
0

Es ist eine iterative Java - Implementierung in UncommonsMaths (arbeitet 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;
}

Full Source

Beantwortet am 07/05/2013 um 02:18
quelle vom benutzer

stimmen
0

c # iterative:

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;
    }
Beantwortet am 26/07/2012 um 16:20
quelle vom benutzer

stimmen
0

Obwohl dies Ihre Frage nicht genau beantwortet, hier ist ein Weg, um jede Permutation der Buchstaben aus einer Reihe von Zeichenketten der gleichen Länge zu erzeugen: zum Beispiel, wenn Ihre Worte waren „Kaffee“, „joomla“ und „moodle“, können Sie erwarten Ausgabe wie "coodle", "joodee", "joffle" usw.

Grundsätzlich ist die Anzahl von Kombinationen ist die (Anzahl der Worte) auf die Kraft der (Anzahl der Buchstaben pro Wort). So wählen Sie eine Zufallszahl zwischen 0 und der Anzahl der Kombinationen - 1, wandelt diese Zahl auf Basis (Anzahl der Worte), dann verwenden Sie jede Ziffer dieser Zahl als Indikator für das Wort von den nächsten Buchstaben zu nehmen.

zB: in dem obigen Beispiel. 3 Wörter, 6 Buchstaben = 729 Kombinationen. Wählen Sie eine Zufallszahl: 465. Convert 3 zu stützen: 122020. Nehmen Sie die ersten Buchstaben von Wort 1, 2. von Wort 2, 3. von Wort 2, 4. von Wort 0 ... und man bekommt ... „joofle“.

Wenn Sie alle Permutationen, nur Schleife von 0 bis 728. Natürlich wollen, wenn Sie nur einen zufälligen Wert Wahl, eine viel einfacheren weniger verwirrende Art und Weise in einer Schleife über die Buchstaben sein würde. Mit dieser Methode können Sie die Rekursion zu vermeiden, sollten Sie alle Permutationen wollen, und es macht Sie sehen aus wie Sie Mathe wissen (tm) !

Wenn die Anzahl der Kombinationen zu groß ist, können Sie es brechen in eine Reihe von kleineren Worte und verketten sie am Ende.

Beantwortet am 16/09/2008 um 06:33
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more