Generowanie wszystkich permutacji danego ciągu


418

Co to jest elegancki sposób na znalezienie wszystkich permutacji ciągu. Np. Permutacja dla ba, będzie bai ab, ale co z dłuższym ciągiem, takim jak abcdefgh? Czy jest jakiś przykład implementacji Java?


3
Istnieje wiele odpowiedzi tutaj: stackoverflow.com/questions/361/…
Marek Sapota

to bardzo popularne pytanie. możesz zajrzeć tutaj: karierycup.com/question?id=3861299
JJunior

9
Należy wspomnieć o założeniu. Postacie są wyjątkowe. Na przykład dla ciągu „aaaa” istnieje tylko jedna odpowiedź. Aby uzyskać bardziej ogólną odpowiedź, możesz zapisać ciągi w zestawie, aby uniknąć powielania
Afshin Moazami

1
Czy powtórzenie znaków jest dozwolone, czy też powtórzenie znaków jest niedozwolone? Czy pojedynczy ciąg może mieć wiele wystąpień tego samego znaku?
Anderson Green

2
Przeczytaj teorię (lub jeśli, podobnie jak ja, jesteś leniwy, przejdź do en.wikipedia.org/wiki/Permutation ) i zaimplementuj prawdziwy algorytm. Zasadniczo możesz wygenerować sekwencję uporządkowania elementów (fakt, że jest to ciąg znaków, nie ma znaczenia) i przechodzić przez porządki, aż wrócisz do początku. Unikaj wszystkiego, co wymaga rekurencji lub manipulacji ciągiem.
CurtainDog

Odpowiedzi:


601
public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(poprzez wprowadzenie do programowania w Javie )


67
Wydaje się, że rozwiązanie nadchodzi stąd introcs.cs.princeton.edu/java/23recursion/…
cyber-mnich

48
To nie jest nauka o rakietach, wymyśliłem prawie taką samą odpowiedź. Drobne poprawki: zamiast powtarzać się do momentu n==0, możesz zatrzymać poziom wcześniej o n==1i wydrukować prefix + str.
lambshaanxy

7
„jaka jest złożoność czasu i przestrzeni?” bez jakiejś częściowej odpowiedzi buforującej dowolny algorytm, który wyprowadza permutację, jest o (n!), ponieważ zestaw wyników dla pytania o permutację jest silni dla danych wejściowych.
jeremyjjbrown

9
Elegancki, tak. Ale rozwiązanie, które konwertuje na tablicę char i zamienia w celu wygenerowania permutacji, będzie wymagało znacznie mniej kopiowania i wygeneruje znacznie mniej śmieci. Również ten algorytm nie uwzględnia powtarzających się znaków.
Gene,

20
@AfshinMoazami Myślę, że str. Podciąg (i + 1, n) można zastąpić str. Podciąg (i + 1). Użycie str.substring (i) spowoduje błąd java.lang.StackOverflowError.
Ayusman,

196

Użyj rekurencji.

  • Wypróbuj kolejno każdą z liter jako pierwszą, a następnie znajdź wszystkie permutacje pozostałych liter za pomocą wywołania rekurencyjnego.
  • Podstawowym przypadkiem jest, gdy wejście jest pustym ciągiem, jedyną permutacją jest pusty ciąg.

3
Jak dodać typ zwrotu do metody permute? kompilator nie może określić typu zwracanego przez tę metodę przy każdej iteracji, nawet jeśli jest to oczywiście typ String.
user1712095

Jak zapewnić różne permutacje w tej metodzie?
kapad

70

Oto moje rozwiązanie oparte na książce „Cracking the Coding Interview” (P54):

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

Uruchomione wyjście ciągu „abcd”:

  • Krok 1: Scal [a] ib: [ba, ab]

  • Krok 2: Scal [ba, ab] ic: [cba, bca, bac, cab, acb, abc]

  • Krok 3: Scal [cba, bca, bac, cab, acb, abc] id: [dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb , cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd]


Strona (71) w Cracking the Coding Interview Book, wydanie 6. :)
KarimIhab

5
Czy to naprawdę dobre rozwiązanie? Polega na przechowywaniu wyników na liście, dlatego w przypadku krótkiego ciągu wejściowego wymyka się spod kontroli.
Androrider

co robi scalanie?
Basavaraj Walikar

Wstawia c w każdej możliwej pozycji każdego łańcucha na liście, więc jeśli lista zawiera tylko [„b”], a c jest „a”, wynikiem scalenia jest [„ab”, „ba”] tutaj to samo rozwiązanie z Swift gist.github. com / daniaDlbani / 3bc10e02541f9ba310d546040c5322fc
Dania Delbani

53

Ze wszystkich rozwiązań podanych tutaj i na innych forach najbardziej podobał mi się Mark Byers. Ten opis naprawdę zmusił mnie do myślenia i samodzielnego kodowania. Szkoda, że ​​nie mogę głosować na jego rozwiązanie, ponieważ jestem nowicjuszem.
W każdym razie tutaj jest moja implementacja jego opisu

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}   

Wolę to rozwiązanie przed pierwszym w tym wątku, ponieważ to rozwiązanie używa StringBuffer. Nie powiedziałbym, że moje rozwiązanie nie tworzy żadnego łańcucha tymczasowego (faktycznie robi to system.out.printlntam, gdzie toString()wywoływany jest StringBuffer). Ale po prostu uważam, że jest to lepsze niż pierwsze rozwiązanie, w którym powstaje zbyt wiele literałów łańcuchowych. Może być jakimś facetem od wydajności, który może to ocenić pod względem „pamięci” (na „czas” to już opóźnia się z powodu tej dodatkowej „wymiany”)


Dlaczego nie po prostu zrobić if(index == str.length())i doPerm(str, index + 1);? currPosWydaje się tu zbędne.
Robur_131,

Przepraszam, czy możesz rozwinąć więcej pytań? Czy po prostu sugerujesz, aby nie używać dodatkowej zmiennej currPos (używanej z powodu wielu wystąpień, a także czytelności), jeśli nie, wklej rozwiązanie, które sugerujesz, aby
rzucić

Ach, rozumiem, że miałeś na myśli zmianę warunków bazowych z indeksowaniem do przodu. Działa w porządku. Tylko na to, że na przedstawione przeze mnie rozwiązanie wpłynęły głównie inne wówczas rozwiązania, które często przechodziły przez obcięty łańcuch zamiast oryginalnego (który przypadek 0 ma sens). Niemniej jednak dziękuję za wskazanie. Zobaczę, czy mogę edytować, minęły lata, odkąd zalogowałem się na tej stronie.
srikanth yaradla

22

Bardzo podstawowym rozwiązaniem w Javie jest użycie rekurencji + zestawu (aby uniknąć powtórzeń), jeśli chcesz przechowywać i zwracać ciągi rozwiązania:

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

2
Jaka jest złożoność czasowa tego alogrithm?
ashisahu

1
@ashisahu O (n!), ponieważ mamy n! permutacje w danym ciągu o długości n.
Zok

17

Wszyscy poprzedni współpracownicy wykonali świetną robotę wyjaśniając i udostępniając kod. Pomyślałem, że powinienem również podzielić się tym podejściem, ponieważ mogłoby to komuś pomóc. Rozwiązanie oparte jest na ( algorytm hałd )

Kilka rzeczy:

  1. Zauważ, że ostatni element przedstawiony w programie Excel służy wyłącznie do lepszej wizualizacji logiki. Tak więc rzeczywiste wartości w ostatniej kolumnie wyniosłyby 2,1,0 (gdybyśmy uruchomili kod, ponieważ mamy do czynienia z tablicami, a tablice zaczynają się od 0).

  2. Algorytm zamiany odbywa się na podstawie parzystych lub nieparzystych wartości bieżącej pozycji. Jest to bardzo zrozumiałe, jeśli spojrzysz na to, gdzie wywoływana jest metoda zamiany. Możesz zobaczyć, co się dzieje.

Oto co się dzieje: wprowadź opis zdjęcia tutaj

public static void main(String[] args) {

        String ourword = "abc";
        String[] ourArray = ourword.split("");
        permute(ourArray, ourArray.length);

    }

    private static void swap(String[] ourarray, int right, int left) {
        String temp = ourarray[right];
        ourarray[right] = ourarray[left];
        ourarray[left] = temp;
    }

    public static void permute(String[] ourArray, int currentPosition) {
        if (currentPosition == 1) {
            System.out.println(Arrays.toString(ourArray));
        } else {
            for (int i = 0; i < currentPosition; i++) {
                // subtract one from the last position (here is where you are
                // selecting the the next last item 
                permute(ourArray, currentPosition - 1);

                // if it's odd position
                if (currentPosition % 2 == 1) {
                    swap(ourArray, 0, currentPosition - 1);
                } else {
                    swap(ourArray, i, currentPosition - 1);
                }
            }
        }
    }

11

Ten jest bez rekurencji

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}

to rozwiązanie wydaje się błędne System.out.println(permute("AABBC").size());wyświetla 45, ale w rzeczywistości 5! = 120
Mladen Adamovic

11

Użyjmy danych wejściowych abcJako przykład .

Zacznij od ostatniego elementu ( c) w zestawie ( ["c"]), a następnie dodaj drugi ostatni element ( b) do jego przodu, końca i wszystkich możliwych pozycji na środku, tworząc go, ["bc", "cb"]a następnie w ten sam sposób doda następny element od back ( a) do każdego ciągu w zestawie, dzięki czemu:

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"] 

Zatem cała permutacja:

["abc", "bac", "bca","acb" ,"cab", "cba"]

Kod:

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

1
Kocham twoje rozwiązanie. Bardzo intuicyjny i dobrze wyjaśniony. Dziękuję Ci bardzo.
user2585781

9

Oto eleganckie, nierekurencyjne rozwiązanie O (n!):

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

To rozwiązanie działa tylko wtedy, gdy słowo ma mniej niż 4 litery, w przeciwnym razie tylko połowa wynikowej tablicy zawiera unikalne słowa.
Maksim Maksimov

5

Jednym z prostych rozwiązań może być po prostu zamiana znaków rekurencyjnie za pomocą dwóch wskaźników.

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}

Jest to podobne do rozwiązania podanego tutaj: geeksforgeeks.org/… , obejmującego cofanie się i złożoność czasową O (n * n!).
Nakul Kumar

5

implementacja python

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')

4

to działało dla mnie ..

import java.util.Arrays;

public class StringPermutations{
    public static void main(String args[]) {
        String inputString = "ABC";
        permute(inputString.toCharArray(), 0, inputString.length()-1);
    }

    public static void permute(char[] ary, int startIndex, int endIndex) {
        if(startIndex == endIndex){
            System.out.println(String.valueOf(ary));
        }else{
            for(int i=startIndex;i<=endIndex;i++) {
                 swap(ary, startIndex, i );
                 permute(ary, startIndex+1, endIndex);
                 swap(ary, startIndex, i );
            }
        }
    }

    public static void swap(char[] ary, int x, int y) {
        char temp = ary[x];
        ary[x] = ary[y];
        ary[y] = temp;
    }
}

3

Użyj rekurencji.

gdy wejście jest pustym ciągiem, jedyną permutacją jest pusty ciąg. Wypróbuj każdą z liter w ciągu, ustawiając go jako pierwszą literę, a następnie znajdź wszystkie permutacje pozostałych liter za pomocą wywołania rekurencyjnego.

import java.util.ArrayList;
import java.util.List;

class Permutation {
    private static List<String> permutation(String prefix, String str) {
        List<String> permutations = new ArrayList<>();
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
            }
        }
        return permutations;
    }

    public static void main(String[] args) {
        List<String> perms = permutation("", "abcd");

        String[] array = new String[perms.size()];
        for (int i = 0; i < perms.size(); i++) {
            array[i] = perms.get(i);
        }

        int x = array.length;

        for (final String anArray : array) {
            System.out.println(anArray);
        }
    }
}

3

Pozwól mi spróbować rozwiązać ten problem za pomocą Kotlin:

fun <T> List<T>.permutations(): List<List<T>> {
    //escape case
    if (this.isEmpty()) return emptyList()

    if (this.size == 1) return listOf(this)

    if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))

    //recursive case
    return this.flatMap { lastItem ->
        this.minus(lastItem).permutations().map { it.plus(lastItem) }
    }
}

Podstawowa koncepcja: Podział długiej listy na mniejszą listę + rekurencja

Długa odpowiedź z przykładową listą [1, 2, 3, 4]:

Nawet w przypadku listy 4 to już trochę mylące, próbując wymienić wszystkie możliwe permutacje w twojej głowie, a to, co musimy zrobić, to właśnie tego uniknąć. Łatwo jest nam zrozumieć, jak wykonać wszystkie permutacje listy o rozmiarach 0, 1 i 2, więc wszystko, co musimy zrobić, to rozbić je na dowolny z tych rozmiarów i połączyć je poprawnie. Wyobraź sobie maszynę z jackpotem: ten algorytm zacznie się obracać od prawej do lewej i zapisze

  1. zwraca pustą / listę 1, gdy rozmiar listy wynosi 0 lub 1
  2. obsłużyć, gdy rozmiar listy wynosi 2 (np. [3, 4]), i wygenerować 2 permutacje ([3, 4] i [4, 3])
  3. Dla każdego elementu zaznacz to jako ostatnie w ostatnim i znajdź wszystkie permutacje dla reszty elementu na liście. (np. połóż [4] na stole i ponownie wrzuć [1, 2, 3] do permutacji)
  4. Teraz z całą permutacją są to dzieci, wróć na koniec listy (np .: [1, 2, 3] [, 4], [1, 3, 2] [, 4], [2, 3, 1] [, 4], ...)

2
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
    public static void main(String[] args) throws IOException {
        hello h = new hello();
        h.printcomp();
    }
      int fact=1;
    public void factrec(int a,int k){
        if(a>=k)
        {fact=fact*k;
        k++;
        factrec(a,k);
        }
        else
        {System.out.println("The string  will have "+fact+" permutations");
        }
        }
    public void printcomp(){
        String str;
        int k;
        Scanner in = new Scanner(System.in);
        System.out.println("enter the string whose permutations has to b found");
        str=in.next();
        k=str.length();
        factrec(k,1);
        String[] arr =new String[fact];
        char[] array = str.toCharArray();
        while(p<fact)
        printcomprec(k,array,arr);
            // if incase u need array containing all the permutation use this
            //for(int d=0;d<fact;d++)         
        //System.out.println(arr[d]);
    }
    int y=1;
    int p = 0;
    int g=1;
    int z = 0;
    public void printcomprec(int k,char array[],String arr[]){
        for (int l = 0; l < k; l++) {
            for (int b=0;b<k-1;b++){
            for (int i=1; i<k-g; i++) {
                char temp;
                String stri = "";
                temp = array[i];
                array[i] = array[i + g];
                array[i + g] = temp;
                for (int j = 0; j < k; j++)
                    stri += array[j];
                arr[z] = stri;
                System.out.println(arr[z] + "   " + p++);
                z++;
            }
            }
            char temp;
            temp=array[0];
            array[0]=array[y];
            array[y]=temp;
            if (y >= k-1)
                y=y-(k-1);
            else
                y++;
        }
        if (g >= k-1)
            g=1;
        else
            g++;
    }

}

2
/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

2

Oto proste minimalistyczne rekurencyjne rozwiązanie w Javie:

public static ArrayList<String> permutations(String s) {
    ArrayList<String> out = new ArrayList<String>();
    if (s.length() == 1) {
        out.add(s);
        return out;
    }
    char first = s.charAt(0);
    String rest = s.substring(1);
    for (String permutation : permutations(rest)) {
        out.addAll(insertAtAllPositions(first, permutation));
    }
    return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
    ArrayList<String> out = new ArrayList<String>();
    for (int i = 0; i <= s.length(); ++i) {
        String inserted = s.substring(0, i) + ch + s.substring(i);
        out.add(inserted);
    }
    return out;
}

2

Możemy użyć silni, aby dowiedzieć się, ile ciągów zaczyna się od konkretnej litery.

Przykład: weź dane wejściowe abcd. (3!) == 6ciągi zaczynają się od każdej litery abcd.

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}

2

Zrobiłem to poprzez podstawowe zrozumienie permutacji i wywoływania funkcji rekurencyjnych. Trwa to trochę czasu, ale odbywa się to niezależnie.

public class LexicographicPermutations {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s="abc";
    List<String>combinations=new ArrayList<String>();
    combinations=permutations(s);
    Collections.sort(combinations);
    System.out.println(combinations);
}

private static List<String> permutations(String s) {
    // TODO Auto-generated method stub
    List<String>combinations=new ArrayList<String>();
    if(s.length()==1){
        combinations.add(s);
    }
    else{
        for(int i=0;i<s.length();i++){
            List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
            for (String string : temp) {
                combinations.add(s.charAt(i)+string);
            }
        }
    }
    return combinations;
}}

który generuje dane wyjściowe jako [abc, acb, bac, bca, cab, cba].

Podstawowa logika tego jest

Dla każdej postaci uważaj ją za pierwszą i znajdź kombinacje pozostałych postaci. np [abc](Combination of abc)->.

  1. a->[bc](a x Combination of (bc))->{abc,acb}
  2. b->[ac](b x Combination of (ac))->{bac,bca}
  3. c->[ab](c x Combination of (ab))->{cab,cba}

A następnie rekurencyjnie nazywając siebie [bc], [ac]i [ab]niezależnie od siebie.


2

Implementacja Java bez rekurencji

public Set<String> permutate(String s){
    Queue<String> permutations = new LinkedList<String>();
    Set<String> v = new HashSet<String>();
    permutations.add(s);

    while(permutations.size()!=0){
        String str = permutations.poll();
        if(!v.contains(str)){
            v.add(str);
            for(int i = 0;i<str.length();i++){
                String c = String.valueOf(str.charAt(i));
                permutations.add(str.substring(i+1) + c +  str.substring(0,i));
            }
        }
    }
    return v;
}

1

// wstaw każdy znak do tablicy arraylist

static ArrayList al = new ArrayList();

private static void findPermutation (String str){
    for (int k = 0; k < str.length(); k++) {
        addOneChar(str.charAt(k));
    }
}

//insert one char into ArrayList
private static void addOneChar(char ch){
    String lastPerStr;
    String tempStr;
    ArrayList locAl = new ArrayList();
    for (int i = 0; i < al.size(); i ++ ){
        lastPerStr = al.get(i).toString();
        //System.out.println("lastPerStr: " + lastPerStr);
        for (int j = 0; j <= lastPerStr.length(); j++) {
            tempStr = lastPerStr.substring(0,j) + ch + 
                    lastPerStr.substring(j, lastPerStr.length());
            locAl.add(tempStr);
            //System.out.println("tempStr: " + tempStr);
        }
    }
    if(al.isEmpty()){
        al.add(ch);
    } else {
        al.clear();
        al = locAl;
    }
}

private static void printArrayList(ArrayList al){
    for (int i = 0; i < al.size(); i++) {
        System.out.print(al.get(i) + "  ");
    }
}

Nie uważam tej odpowiedzi za przydatną, ponieważ nie zawiera żadnego wyjaśnienia i używa tego samego algorytmu, co kilka innych odpowiedzi, które zawierają wyjaśnienie.
Bernhard Barker

1
//Rotate and create words beginning with all letter possible and push to stack 1

//Read from stack1 and for each word create words with other letters at the next location by rotation and so on 

/*  eg : man

    1. push1 - man, anm, nma
    2. pop1 - nma ,  push2 - nam,nma
       pop1 - anm ,  push2 - amn,anm
       pop1 - man ,  push2 - mna,man
*/

public class StringPermute {

    static String str;
    static String word;
    static int top1 = -1;
    static int top2 = -1;
    static String[] stringArray1;
    static String[] stringArray2;
    static int strlength = 0;

    public static void main(String[] args) throws IOException {
        System.out.println("Enter String : ");
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader bfr = new BufferedReader(isr);
        str = bfr.readLine();
        word = str;
        strlength = str.length();
        int n = 1;
        for (int i = 1; i <= strlength; i++) {
            n = n * i;
        }
        stringArray1 = new String[n];
        stringArray2 = new String[n];
        push(word, 1);
        doPermute();
        display();
    }

    public static void push(String word, int x) {
        if (x == 1)
            stringArray1[++top1] = word;
        else
            stringArray2[++top2] = word;
    }

    public static String pop(int x) {
        if (x == 1)
            return stringArray1[top1--];
        else
            return stringArray2[top2--];
    }

    public static void doPermute() {

        for (int j = strlength; j >= 2; j--)
            popper(j);

    }

    public static void popper(int length) {
        // pop from stack1 , rotate each word n times and push to stack 2
        if (top1 > -1) {
            while (top1 > -1) {
                word = pop(1);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 2);
                }
            }
        }
        // pop from stack2 , rotate each word n times w.r.t position and push to
        // stack 1
        else {
            while (top2 > -1) {
                word = pop(2);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 1);
                }
            }
        }

    }

    public static void rotate(int position) {
        char[] charstring = new char[100];
        for (int j = 0; j < word.length(); j++)
            charstring[j] = word.charAt(j);

        int startpos = strlength - position;
        char temp = charstring[startpos];
        for (int i = startpos; i < strlength - 1; i++) {
            charstring[i] = charstring[i + 1];
        }
        charstring[strlength - 1] = temp;
        word = new String(charstring).trim();
    }

    public static void display() {
        int top;
        if (top1 > -1) {
            while (top1 > -1)
                System.out.println(stringArray1[top1--]);
        } else {
            while (top2 > -1)
                System.out.println(stringArray2[top2--]);
        }
    }
}

1

Innym prostym sposobem jest zapętlenie łańcucha, wybranie nieużywanego znaku i umieszczenie go w buforze, kontynuowanie pętli, aż rozmiar bufora będzie równy długości łańcucha. Bardziej podoba mi się to rozwiązanie do śledzenia wstecznego, ponieważ:

  1. Łatwy do zrozumienia
  2. Łatwo uniknąć powielania
  3. Dane wyjściowe są sortowane

Oto kod Java:

List<String> permute(String str) {
  if (str == null) {
    return null;
  }

  char[] chars = str.toCharArray();
  boolean[] used = new boolean[chars.length];

  List<String> res = new ArrayList<String>();
  StringBuilder sb = new StringBuilder();

  Arrays.sort(chars);

  helper(chars, used, sb, res);

  return res;
}

void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
  if (sb.length() == chars.length) {
    res.add(sb.toString());
    return;
  }

  for (int i = 0; i < chars.length; i++) {
    // avoid duplicates
    if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
      continue;
    }

    // pick the character that has not used yet
    if (!used[i]) {
      used[i] = true;
      sb.append(chars[i]);

      helper(chars, used, sb, res);

      // back tracking
      sb.deleteCharAt(sb.length() - 1);
      used[i] = false;
    }
  }
}

Dane wejściowe: 1231

Lista wyjściowa: {1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211}

Zauważyłem, że dane wyjściowe są posortowane i nie ma duplikatu wyników.


1

Rekurencja nie jest konieczna, nawet jeśli możesz bezpośrednio obliczyć dowolną permutację , w tym rozwiązaniu zastosowano ogólne funkcje do permutacji dowolnej tablicy.

Oto dobra informacja na temat tego algorytmu.

Dla C # twórców tutaj jest bardziej przydatna realizacja.

public static void main(String[] args) {
    String word = "12345";

    Character[] array = ArrayUtils.toObject(word.toCharArray());
    long[] factorials = Permutation.getFactorials(array.length + 1);

    for (long i = 0; i < factorials[array.length]; i++) {
        Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
        printPermutation(permutation);
    }
}

private static void printPermutation(Character[] permutation) {
    for (int i = 0; i < permutation.length; i++) {
        System.out.print(permutation[i]);
    }
    System.out.println();
}

Algorytm ten ma złożoność czasową i przestrzenną O (N) do obliczania każdej permutacji .

public class Permutation {
    public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
        int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
        T[] permutation = generatePermutation(array, sequence);

        return permutation;
    }

    public static <T> T[] generatePermutation(T[] array, int[] sequence) {
        T[] clone = array.clone();

        for (int i = 0; i < clone.length - 1; i++) {
            swap(clone, i, i + sequence[i]);
        }

        return clone;
    }

    private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
        int[] sequence = new int[size];

        for (int j = 0; j < sequence.length; j++) {
            long factorial = factorials[sequence.length - j];
            sequence[j] = (int) (permutationNumber / factorial);
            permutationNumber = (int) (permutationNumber % factorial);
        }

        return sequence;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static long[] getFactorials(int length) {
        long[] factorials = new long[length];
        long factor = 1;

        for (int i = 0; i < length; i++) {
            factor *= i <= 1 ? 1 : i;
            factorials[i] = factor;
        }

        return factorials;
    }
}

1

Permutacja ciągu:

public static void main(String args[]) {
    permu(0,"ABCD");
}

static void permu(int fixed,String s) {
    char[] chr=s.toCharArray();
    if(fixed==s.length())
        System.out.println(s);
    for(int i=fixed;i<s.length();i++) {
        char c=chr[i];
        chr[i]=chr[fixed];
        chr[fixed]=c;
        permu(fixed+1,new String(chr));
    }   
}

1

Oto kolejna prostsza metoda przeprowadzania permutacji łańcucha.

public class Solution4 {
public static void main(String[] args) {
    String  a = "Protijayi";
  per(a, 0);

}

static void per(String a  , int start ) {
      //bse case;
    if(a.length() == start) {System.out.println(a);}
    char[] ca = a.toCharArray();
    //swap 
    for (int i = start; i < ca.length; i++) {
        char t = ca[i];
        ca[i] = ca[start];
        ca[start] = t;
        per(new String(ca),start+1);
    }

}//per

}

1

Implementacja Java, która drukuje wszystkie permutacje danego ciągu z uwzględnieniem duplikatów znaków i drukuje tylko unikalne znaki, jest następująca:

import java.util.Set;
import java.util.HashSet;

public class PrintAllPermutations2
{
    public static void main(String[] args)
    {
        String str = "AAC";

    PrintAllPermutations2 permutation = new PrintAllPermutations2();

    Set<String> uniqueStrings = new HashSet<>();

    permutation.permute("", str, uniqueStrings);
}

void permute(String prefixString, String s, Set<String> set)
{
    int n = s.length();

    if(n == 0)
    {
        if(!set.contains(prefixString))
        {
            System.out.println(prefixString);
            set.add(prefixString);
        }
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
        }
    }
}
}

0
/*
     * eg: abc =>{a,bc},{b,ac},{c,ab}
     * =>{ca,b},{cb,a}
     * =>cba,cab
     * =>{ba,c},{bc,a}
     * =>bca,bac
     * =>{ab,c},{ac,b}
     * =>acb,abc
     */
    public void nonRecpermute(String prefix, String word)
    {
        String[] currentstr ={prefix,word};
        Stack<String[]> stack = new Stack<String[]>();
        stack.add(currentstr);
        while(!stack.isEmpty())
        {
            currentstr = stack.pop();
            String currentPrefix = currentstr[0];
            String currentWord = currentstr[1];
            if(currentWord.equals(""))
            {
                System.out.println("Word ="+currentPrefix);
            }
            for(int i=0;i<currentWord.length();i++)
            {
                String[] newstr = new String[2];
                newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
                newstr[1] = currentWord.substring(0, i);
                if(i<currentWord.length()-1)
                {
                    newstr[1] = newstr[1]+currentWord.substring(i+1);
                }
                stack.push(newstr);
            }

        }

    }

0

Można to zrobić iteracyjnie, po prostu wstawiając kolejno każdą literę łańcucha we wszystkich lokalizacjach poprzednich wyników częściowych.

Zaczynamy [A], który ze Bstaje [BA, AB], i C,[CBA, BCA, BAC, CAB, etc] .

Czas pracy byłoby O(n!), które dla przypadku testowego ABCD, jest1 x 2 x 3 x 4 .

W powyższym produkcie 1jest za A, 2jest za Bitp.

Próbka Dart:

void main() {

  String insertAt(String a, String b, int index)
  {
    return a.substring(0, index) + b + a.substring(index);
  }

  List<String> Permute(String word) {

    var letters = word.split('');

    var p_list = [ letters.first ];

    for (var c in letters.sublist(1)) {

      var new_list = [ ];

      for (var p in p_list)
        for (int i = 0; i <= p.length; i++)
          new_list.add(insertAt(p, c, i));

      p_list = new_list;
    }

    return p_list;
  }

  print(Permute("ABCD"));

}

0

Oto implementacja Java:

/* All Permutations of a String */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Complexity O(n*n!) */
class Ideone
{
     public static ArrayList<String> strPerm(String str, ArrayList<String> list)
     {
        int len = str.length();
        if(len==1){
            list.add(str);
            return list;
        }

        list = strPerm(str.substring(0,len-1),list);
        int ls = list.size();
        char ap = str.charAt(len-1);
        for(int i=0;i<ls;i++){
            String temp = list.get(i);
            int tl = temp.length();
            for(int j=0;j<=tl;j++){
                list.add(temp.substring(0,j)+ap+temp.substring(j,tl));  
            }
        }

        while(true){
            String temp = list.get(0);
            if(temp.length()<len)
                list.remove(temp);
            else
                break;
        }

        return list;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        String str = "abc";
        ArrayList<String> list = new ArrayList<>();

        list = strPerm(str,list);
        System.out.println("Total Permutations : "+list.size());
        for(int i=0;i<list.size();i++)
            System.out.println(list.get(i));

    }
}

http://ideone.com/nWPb3k

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.