Generere en liste over alle mulige permutasjoner av en streng

stemmer
147

Hvordan skulle jeg gå om å generere en liste over alle mulige permutasjoner av en streng mellom x og y tegn i lengde, som inneholder en variabel liste over tegn.

Alle språk ville fungere, men det bør være bærbare.

Publisert på 02/08/2008 klokken 06:57
kilden bruker
På andre språk...                            


35 svar

stemmer
68

Det er flere måter å gjøre dette. Vanlige metoder bruke rekursjon, memoization, eller dynamisk programmering. Den grunnleggende ideen er at du produserer en liste over alle strenger av lengde 1, deretter i hver iterasjon, for alle strenger er produsert i den siste iterasjon, legge til at streng sammenkjedet med hvert tegn i strengen individuelt. (Variabelen indeksen i koden under holder styr på starten av forrige og neste iterasjon)

Noen pseudokode:

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)

ville du da trenger å fjerne alle strenger mindre enn x i lengde, de vil være de første (x-1) * Len (originalString) oppføringer på listen.

Svarte 02/08/2008 kl. 07:48
kilden bruker

stemmer
36

Det er bedre å bruke tilbakesporing

#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;
}
Svarte 10/01/2012 kl. 18:00
kilden bruker

stemmer
24

Du kommer til å få mange strenger, det er sikkert ...

\ 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!
Hvor, x og y er hvordan du definerer dem, og r er antall tegn vi skal velge mellom - -Hvis jeg forstå deg riktig. Du bør definitivt generere disse etter behov og ikke bli våt og si, generere en Powerset og deretter filtrere lengden på strengene.

Følgende definitivt ikke er den beste måten å generere disse, men det er en interessant side, ingen de mindre.

Knuth (volum 4, fascikkel 2, 7.2.1.3) forteller oss at (r, t) -combination er ekvivalent med r + 1 ting tatt t i en tid med repetisjon - en (r, t) -combination blir notasjonen som brukes av Knuth som er lik {t \ velge {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Vi kan finne ut av dette ved først å generere hver (s, t) -combination i binær form (slik at, med lengde (s + t)), og telling av antallet av 0 s til venstre for hver 1.

10001000011101 -> blir permutasjonen: {0, 3, 4, 4, 4, 1}

Svarte 05/08/2008 kl. 04:57
kilden bruker

stemmer
14

Ikke rekursiv løsning i henhold til Knuth, Python eksempel:

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)
Svarte 09/11/2010 kl. 13:58
kilden bruker

stemmer
12

Det er mange gode svar her. Jeg foreslår også en veldig enkel rekursiv løsning i 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;
    });
}

Merk : strengene med gjentatte tegn vil ikke produsere unike permutasjoner.

Svarte 08/01/2014 kl. 11:00
kilden bruker

stemmer
12

Her er en enkel løsning i C #.

Det genererer bare de forskjellige permutasjoner av en gitt streng.

    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;
        }
    }
Svarte 05/07/2010 kl. 09:06
kilden bruker

stemmer
12

Noen arbeider Java-kode basert på Sarp svar :

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);
    }
}
Svarte 04/04/2010 kl. 18:18
kilden bruker

stemmer
12

Du kan se på " Effektivt Opplisting undergrupper av et sett ", som beskriver en algoritme for å gjøre en del av hva du vil - raskt generere alle undergrupper av N tegn fra lengde x til y. Den inneholder en implementasjon i C.

For hver undergruppe, du har fortsatt å generere alle permutasjoner. For eksempel hvis du ønsket 3 tegn fra "abcde", vil denne algoritmen gi deg "abc", "abd", "Abe" ... men du må permutere hver enkelt å få "ACB", "bac", "BCA", osv

Svarte 14/11/2008 kl. 19:36
kilden bruker

stemmer
9

Jeg pisket opp dette rask i 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

Du kan se inn i språket API for innebygde permutasjon typen funksjoner, og du kan være i stand til å skrive mer optimalisert kode, men hvis tallene er alle som høy, er jeg ikke sikker på at det er mye av en vei rundt å ha en masse resultater .

Anyways, ideen bak koden er å starte med streng med lengde 0, og deretter holde styr på alle strenger av lengde Z hvor Z er den nåværende størrelsen på iterasjon. Deretter gå gjennom hver streng og legge hver karakter på hver streng. Til slutt ved enden, fjern de som var under x-terskel og returnerer resultatet.

Jeg hadde ikke teste det med potensielt meningsløst inngang (null tegnlisten, rare verdiene for x og y, etc).

Svarte 02/08/2008 kl. 07:56
kilden bruker

stemmer
7

Ruby svar som fungerer:

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")
Svarte 20/04/2012 kl. 00:21
kilden bruker

stemmer
7

forandre rekkefølgen (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 * )] for å fjerne duplikater ved innsetting av hvert alfabet sjekk for å se om tidligere strengen slutter med den samme alfabet (hvorfor? -Trening)

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

Skriver ut alle permutasjoner sans duplikater

Svarte 22/02/2011 kl. 18:45
kilden bruker

stemmer
7

... og her er C-versjonen:

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;
}
Svarte 07/02/2011 kl. 21:56
kilden bruker

stemmer
7

I Perl, hvis du ønsker å begrense deg til små bokstaver alfabetet, kan du gjøre dette:

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

Dette gir alle mulige strenger mellom 1 og 4 tegn med små bokstaver. For store bokstaver, endres "a"til "A"og "zzzz"til "ZZZZ".

For mixed-saken blir det mye vanskeligere, og sannsynligvis ikke gjennomførbart med en av Perls builtin operatører sånn.

Svarte 15/02/2009 kl. 10:02
kilden bruker

stemmer
7

Her er et enkelt ord C # rekursiv løsning:

Metode:

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

Calling:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Svarte 20/10/2008 kl. 00:17
kilden bruker

stemmer
7

Rekursiv løsning i 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;
            }
        }
}
Svarte 29/09/2008 kl. 01:34
kilden bruker

stemmer
7

Dette er en oversettelse av Mike Ruby versjon, i 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)))))

Og en annen versjon, litt kortere og bruke mer sløyfe anlegget funksjoner:

(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)))))
Svarte 16/09/2008 kl. 05:15
kilden bruker

stemmer
6

Følgende Java rekursjonsuttrykk utskrifter alle permutasjoner av en gitt streng:

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

Det følgende er en oppdatert versjon av ovennevnte "PERMUT" metode som gjør n! (N fakultet) mindre rekursive samtaler i forhold til den ovennevnte metode

//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()));
   }
}
Svarte 19/06/2013 kl. 04:23
kilden bruker

stemmer
5

Her er en ikke-rekursiv versjonen jeg kom opp med, i javascript. Det er ikke basert på Knuth ikke-rekursiv ovenfor, selv om den har noen likheter i element bytte. Jeg har bekreftet sin riktighet for inngangs rekker opp til 8 elementer.

En rask optimalisering vil være forhånds flighting på outrekke og unngå push().

Den grunnleggende ideen er:

  1. Gitt en enkelt kildegruppe, generere et første nytt sett av matriser som bytte av det første element og hver etterfølgende element i sin tur, hver gang etterlater de andre elementer uaffisert. f.eks: gitt 1234, genererer 1234, 2134, 3214, 4231.

  2. Bruk hver gruppe fra den foregående pasning som kime for en ny pasning, men i stedet for å bytte det første element, bytter det andre element med hver etterfølgende element. Også denne gangen, ikke inkluderer den opprinnelige matrisen i produksjonen.

  3. Gjenta trinn 2 til ferdig.

Her er kodeeksempel:

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;
}
Svarte 03/08/2011 kl. 07:11
kilden bruker

stemmer
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;
    }
}
Svarte 24/10/2010 kl. 22:01
kilden bruker

stemmer
5

Jeg er ikke sikker på hvorfor du ønsker å gjøre dette i første omgang. Den resulterende sett for noen moderat store verdier av x og y vil være enorme, og vil vokse eksponentielt som x og / eller y blir større.

La oss si din sett av mulige tegn er de 26 små bokstaver i alfabetet, og du spør din søknad for å generere alle permutasjoner der lengde = 5. Forutsatt at du ikke går tom for minne du får 11881376 (dvs. 26 til strøm av 5) strenger tilbake. Bump som lengde opp til 6, og du får 308,915,776 strenger tilbake. Disse tallene blir smertelig stor, veldig raskt.

Her er en løsning jeg satt sammen i Java. Du må gi to runtime argumenter (tilsvarende x og y). Ha det gøy.

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);
            }
        }
    }
}
Svarte 02/08/2008 kl. 09:40
kilden bruker

stemmer
3

Jeg trengte dette i dag, og selv om svarene allerede gitt pekte meg i riktig retning, de var ikke helt hva jeg ville.

Her er en implementering hjelp Heap metode. Lengden av tabellen må være minst tre og av praktiske hensyn ikke være større enn 10 eller så, avhengig av hva du vil gjøre, tålmodighet og klokkehastighet.

Før du angir sløyfe, initial Perm(1 To N)med den første permutasjon, Stack(3 To N)med nuller *, og Levelmed 2**. På slutten av loopen samtalen NextPerm, som vil returnere falsk når vi er ferdige.

* VB vil gjøre det for deg.

** Du kan endre NextPerm litt for å gjøre dette unødvendig, men det er tydeligere som dette.

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

Andre metoder er beskrevet av ulike forfattere. Knuth beskriver to, gir man leksikalsk orden, men er komplisert og langsom, den andre er kjent som metoden til vanlig endringer. Jie Gao og Dianjun Wang skrev også en interessant papir.

Svarte 02/10/2011 kl. 09:13
kilden bruker

stemmer
2

Her er en link som beskriver hvordan du skriver ut permutasjoner av en streng. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Svarte 13/02/2014 kl. 21:08
kilden bruker

stemmer
2

Denne koden i python, da kalt med allowed_characterssatt til [0,1]og fire karakter max, ville generere 2 ^ 4 resultater:

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

Håper dette er til nytte for deg. Fungerer med alle tegn, ikke bare tall

Svarte 26/05/2011 kl. 14:22
kilden bruker

stemmer
2

I rubin:

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

Det er ganske fort, men det kommer til å ta litt tid =). Selvfølgelig kan du starte på "aaaaaaaa" hvis de korte strenger er ikke interessant for deg.

Jeg kan ha feiltolket selve spørsmålet om - i et av innleggene det hørtes ut som om du bare trengte en bruteforce bibliotek av strenger, men i det viktigste spørsmålet høres det ut som du trenger å permutate en bestemt streng.

Ditt problem er noe som ligner på denne: http://beust.com/weblog/archives/000491.html (liste alle heltall der ingen av sifrene gjentar seg selv, noe som resulterte i en hel rekke språk løse det, med Objective Caml fyr ved hjelp av permutasjoner, og noen java fyr ved hjelp av enda en løsning).

Svarte 15/09/2008 kl. 17:32
kilden bruker

stemmer
0

De mulige streng permutasjoner kan beregnes ved hjelp av rekursiv funksjon. Nedenfor er en av mulig løsning.

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());
}
Svarte 06/02/2017 kl. 06:00
kilden bruker

stemmer
0

kode skrevet for java språk:

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

}

Svarte 05/06/2016 kl. 08:42
kilden bruker

stemmer
0

Vel her er en elegant, ikke-rekursiv, O (n!) Løsning:

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;
    }
Svarte 27/06/2015 kl. 08:44
kilden bruker

stemmer
0

Den Pytonske løsning:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Svarte 13/07/2014 kl. 07:51
kilden bruker

stemmer
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

Her er min ta på en ikke rekursiv versjon

Svarte 23/01/2014 kl. 03:28
kilden bruker

stemmer
0

Rekursiv løsning med sjåfør main()metode.

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

}

Svarte 19/10/2013 kl. 01:34
kilden bruker

stemmer
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
Svarte 22/08/2013 kl. 17:51
kilden bruker

stemmer
0

En rekursiv løsning i python. Den gode ting om denne koden er at det eksporterer en ordbok, med nøkler som strykere og alle mulige permutasjoner som verdier. Alle mulige strengelengder er inkludert, så i praksis, oppretter du et overordnet.

Hvis du bare trenger den endelige permutasjoner, kan du slette andre taster fra ordlisten.

I denne koden, er ordboken permutasjoner global.

I base case, jeg lagre verdien som både muligheter i en liste. perms['ab'] = ['ab','ba'].

For høyere strenglengder, refererer den funksjon å redusere strenglengder og inkorporerer de tidligere beregnede permutasjoner.

Funksjonen gjør to ting:

  • kaller seg med en mindre streng
  • returnerer en liste over permutasjoner av en bestemt streng hvis den allerede er tilgjengelig. Hvis tilbake til seg selv, vil disse bli brukt til å legge til karakteren og skape nyere permutasjoner.

Dyrt for minne.

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]
Svarte 05/07/2013 kl. 04:15
kilden bruker

stemmer
0

Det er en iterativ Java implementering i UncommonsMaths (arbeider for en liste over objekter):

/**
 * 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 kilde

Svarte 07/05/2013 kl. 01:18
kilden bruker

stemmer
0

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;
    }
Svarte 26/07/2012 kl. 15:20
kilden bruker

stemmer
0

Selv om dette ikke svare på spørsmålet ditt akkurat, her er en måte å generere hver permutasjon av bokstavene fra en rekke strenger av samme lengde: f.eks, hvis ord var "kaffe", "Joomla" og "moodle", kan du forvente utgang som "coodle", "joodee", "joffle", osv

I utgangspunktet er det antall kombinasjoner av (antall ord) til kraften i (antall bokstaver pr ord). Så velger et tilfeldig tall mellom 0 og antall kombinasjoner - 1, konvertere det tallet til base (antall ord), og deretter bruke hvert siffer av dette nummeret som indikator for hvilke ord å ta det neste brevet fra.

f.eks i ovennevnte eksempel. 3 ord, bokstaver 6 = 729 kombinasjoner. Velg et tilfeldig tall: 465. Convert å basere 3: 122020. Ta det første brevet fra ordet en, andre fra ordet 2, tredje fra ordet 2, fjerde fra ordet 0 ... og du får ... "joofle".

Hvis du ønsket alle permutasjoner, bare sløyfe fra 0 til 728. Selvfølgelig, hvis du bare velger en tilfeldig verdi, en mye enklere mindre forvirrende måte ville være å sløyfe over bokstavene. Denne metoden gjør det mulig å unngå rekursjon, bør du vil at alle permutasjoner, pluss det gjør at du ser ut som du vet Maths (TM) !

Hvis antall kombinasjoner er overdreven, kan du bryte den opp i en rekke mindre ord og sette sammen dem på slutten.

Svarte 16/09/2008 kl. 05:33
kilden bruker

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