Lista wszystkich permutacji łańcucha / liczby całkowitej


159

Częstym zadaniem w programowaniu wywiadów (choć nie z mojego doświadczenia w wywiadach) jest branie łańcucha lub liczby całkowitej i lista wszystkich możliwych permutacji.

Czy istnieje przykład, jak to się robi i logika rozwiązania takiego problemu?

Widziałem kilka fragmentów kodu, ale nie zostały one dobrze skomentowane / wyjaśnione, a przez to trudne do naśladowania.


Odpowiedzi:


152

Po pierwsze: oczywiście pachnie rekurencją !

Ponieważ chciałeś również poznać zasadę, zrobiłem wszystko, co w mojej mocy, aby wyjaśnić to ludzkim językiem. Myślę, że rekurencja jest bardzo łatwa w większości przypadków. Musisz tylko wykonać dwa kroki:

  1. Pierwszy krok
  2. Wszystkie inne kroki (wszystkie z tą samą logiką)

W języku ludzkim :

W skrócie:
1. Permutacja 1 elementu to jeden element.
2. Permutacja zbioru elementów jest listą każdego z elementów, połączoną z każdą permutacją pozostałych elementów.

Przykład:

Jeśli zestaw ma tylko jeden element ->
zwróć go.
perm (a) -> a

Jeśli zestaw ma dwa znaki: dla każdego elementu w nim: zwróć element, z dodaną permutacją pozostałych elementów, na przykład:

perm (ab) ->

a + dop. (b) -> ab

b + perm (a) -> ba

Dalej: dla każdego znaku w zestawie: zwróć znak, połączony z perumacją> reszty zestawu

perm (abc) ->

a + perm (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cab , cba

perm (abc ... z) ->

a + perm (...), b + perm (....)
....

Znalazłem pseudokod na http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

DO#

OK, i coś bardziej rozbudowanego (a ponieważ jest oznaczony jako c #), z http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Raczej długi, ale zdecydowałem się go skopiować zresztą post nie jest zależny od oryginału.

Funkcja przyjmuje ciąg znaków i zapisuje każdą możliwą permutację tego dokładnego ciągu, więc na przykład, jeśli podano „ABC”, powinna się wylać:

ABC, ACB, BAC, BCA, CAB, CBA.

Kod:

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

21
Dla większej przejrzystości nazwałbym k „recursionDepth”, a m „maxDepth”.
Nerf Herder

3
Druga zamiana ( Swap(ref list[k], ref list[i]);) jest niepotrzebna.
dance2die

1
Dziękuję za to rozwiązanie. Stworzyłem z niego to skrzypce ( dotnetfiddle.net/oTzihw ) (z odpowiednim nazewnictwem zamiast k i m). O ile rozumiem algo, druga zamiana jest wymagana (do śledzenia), ponieważ edytujesz oryginalną tablicę w miejscu.
Andrew

3
drobna uwaga: Wygląda na to, że metoda Swap lepiej być implementowana z tymczasową zmienną buforową i nie używać XOR ( dotnetperls.com/swap )
Sergioet

7
Używając krotek C # 7, możesz sprawić, że zamiana będzie bardziej elegancka:(a[x], a[y]) = (a[y], a[x]);
Darren,

81

To tylko dwa wiersze kodu, jeśli LINQ może używać. Zobacz moją odpowiedź tutaj .

EDYTOWAĆ

Oto moja ogólna funkcja, która może zwrócić wszystkie permutacje (nie kombinacje) z listy T:

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Przykład:

IEnumerable<IEnumerable<int>> result =
    GetPermutations(Enumerable.Range(1, 3), 3);

Wyjście - lista list całkowitych:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

Ponieważ ta funkcja korzysta z LINQ, wymaga .net 3.5 lub nowszej.


3
kombinacje i permutacje to różne rzeczy. jest podobnie, ale twoja odpowiedź wydaje się odpowiadać na inny problem niż wszystkie permutacje zbioru elementów.
Shawn Kovac,

@ShawnKovac, dzięki za wskazanie tego! Zaktualizowałem mój kod z kombinacji do permutacji.
Pengyang

1
@ Pengyang Spojrzałem na twoją drugą odpowiedź i powiem, że bardzo mi to pomogło, ale mam inną sytuację, której nie wiem, czy wskazałeś właściwy sposób jej rozwiązania. Chciałem znaleźć wszystkie permutacje słowa takiego jak „HALLOWEEN”, ale stwierdziłem, że chcę również uwzględnić w zestawie wyników zarówno „L”, jak i oba „E”. W moich iteracjach zapętlam twoją metodę, podając zwiększoną długość z każdą iteracją (długość ++) i spodziewałbym się, że biorąc pod uwagę pełną długość słowa HALLOWEEN (9 znaków), otrzymam wyniki o długości 9 znaków ... ale tak nie jest: Dostaję tylko 7 (1 L i 1 E są pominięte)
MegaMark

Chciałbym również zaznaczyć, że NIE chcę, aby 9 „H” występowało tylko raz w słowie.
MegaMark

4
@MegaMark Ta funkcja wymaga, aby elementy były unikalne. Spróbuj tego:const string s = "HALLOWEEN"; var result = GetPermutations(Enumerable.Range(0, s.Length), s.Length).Select(t => t.Select(i => s[i]));
Pengyang

36

Tutaj znalazłem rozwiązanie. Został napisany w Javie, ale przekonwertowałem go na C #. Mam nadzieję, że ci to pomoże.

Tutaj wprowadź opis obrazu

Oto kod w C #:

static void Main(string[] args)
{
    string str = "ABC";
    char[] charArry = str.ToCharArray();
    Permute(charArry, 0, 2);
    Console.ReadKey();
}

static void Permute(char[] arry, int i, int n)
{
    int j;
    if (i==n)
        Console.WriteLine(arry);
    else
    {
        for(j = i; j <=n; j++)
        {
            Swap(ref arry[i],ref arry[j]);
            Permute(arry,i+1,n);
            Swap(ref arry[i], ref arry[j]); //backtrack
        }
    }
}

static void Swap(ref char a, ref char b)
{
    char tmp;
    tmp = a;
    a=b;
    b = tmp;
}

Czy został przeniesiony z innego języka? Zdecydowanie +1 dla obrazu, ponieważ naprawdę dodaje wartości. Jednak sam kod wydaje się mieć pewien potencjał ulepszeń. Niektóre drobne części nie są potrzebne, ale co najważniejsze, odczuwam to uczucie C ++, gdy wysyłamy coś i robimy z tym coś zamiast podawać parametry wejściowe i pobierać zwracaną wartość. W rzeczywistości użyłem twojego obrazu do zaimplementowania kodu C # w stylu C # (styl jest oczywiście moją osobistą percepcją) i bardzo mi to pomogło, więc kiedy go opublikuję, zdecydowanie ukradnę ci go (i uznanie za to).
Konrad Viltersten

21

Rekursja nie jest konieczna, oto dobre informacje na temat tego rozwiązania.

var values1 = new[] { 1, 2, 3, 4, 5 };

foreach (var permutation in values1.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };

foreach (var permutation in values2.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Console.ReadLine();

Używam tego algorytmu od lat, ma on czas i przestrzeń O (N) złożoność aby obliczyć każdą permutację .

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[]) array.Clone();

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

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

Działa po wyjęciu z pudełka!
revobtz

1
może nie rozumiem notacji O (n). czy N nie odnosi się do liczby „wewnętrznych pętli” potrzebnych do działania algorytmu? wydaje mi się, że jeśli masz N liczb, wygląda na to, że jest to O (N * N!) (ponieważ N! razy musi wykonać N zamiany). Ponadto musi wykonać mnóstwo kopiowania macierzy. Ten kod jest „zgrabny”, ale nie użyłbym go.
eric frazer

@ericfrazer Każda permutacja używa tylko jednej kopii tablicy i O(N-1)dla sekwencji i O(N)zamiany, czyli O(N). I nadal używam tego w produkcji, ale z refaktorem do generowania tylko jednej permutacji, na przykład: GetPermutation(i)gdzie 0 <= i <= N!-1. Z przyjemnością użyję czegoś o lepszej wydajności niż ta, więc możesz swobodnie wywołać odniesienie dla czegoś lepszego, większość alternatyw używa się O(N!)w pamięci, więc możesz to również sprawdzić.
Najera

11
void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

Możesz napisać swoją funkcję swap, aby zamieniać znaki.
To ma być nazwane jako permute (string, 0);


5
To wygląda jak C, a nie C #.
Jon Schneider

9

Po pierwsze, zestawy mają permutacje, a nie łańcuchy lub liczby całkowite, więc przyjmuję, że masz na myśli „zestaw znaków w ciągu”.

Zauważ, że zbiór o rozmiarze n ma n! n-permutacje.

Poniższy pseudokod (z Wikipedii), wywołany z k = 1 ... n! poda wszystkie permutacje:

function permutation(k, s) {
    for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j; // integer division cuts off the remainder
    }
    return s;
}

Oto równoważny kod w Pythonie (dla indeksów tablic opartych na 0):

def permutation(k, s):
    r = s[:]
    for j in range(2, len(s)+1):
        r[j-1], r[k%j] = r[k%j], r[j-1]
        k = k/j+1
    return r

5
jaki to język? pytanie jest oznaczone C #. nie wiem, co k := k / j;robi.
Shawn Kovac

8

Nieznacznie zmodyfikowana wersja w C #, która daje potrzebne permutacje w tablicy dowolnego typu.

    // USAGE: create an array of any type, and call Permutations()
    var vals = new[] {"a", "bb", "ccc"};
    foreach (var v in Permutations(vals))
        Console.WriteLine(string.Join(",", v)); // Print values separated by comma


public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
    if (fromInd + 1 == values.Length)
        yield return values;
    else
    {
        foreach (var v in Permutations(values, fromInd + 1))
            yield return v;

        for (var i = fromInd + 1; i < values.Length; i++)
        {
            SwapValues(values, fromInd, i);
            foreach (var v in Permutations(values, fromInd + 1))
                yield return v;
            SwapValues(values, fromInd, i);
        }
    }
}

private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        T tmp = values[pos1];
        values[pos1] = values[pos2];
        values[pos2] = tmp;
    }
}

Jedno małe zastrzeżenie w tej implementacji: działa poprawnie tylko wtedy, gdy nie próbujesz przechowywać wartości wyliczenia. Jeśli spróbujesz zrobić coś takiego, Permutations(vals).ToArray()otrzymasz N odniesień do tej samej tablicy. Jeśli chcesz mieć możliwość przechowywania wyników, musisz ręcznie utworzyć kopię. Np.Permutations(values).Select(v => (T[])v.Clone())
Pharap

8
class Program
{
    public static void Main(string[] args)
    {
        Permutation("abc");
    }

    static void Permutation(string rest, string prefix = "")
    {
        if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);

        // Each letter has a chance to be permutated
        for (int i = 0; i < rest.Length; i++)
        {                
            Permutation(rest.Remove(i, 1), prefix + rest[i]);
        }
    }
}

1
Szalone rozwiązanie. Dziękuję Ci!
Cristian E.

7

Podobało mi się podejście FBryant87, ponieważ jest proste. Niestety, podobnie jak wiele innych „rozwiązań” nie oferuje wszystkich permutacji lub np. Liczby całkowitej, jeśli zawiera tę samą cyfrę więcej niż raz. Weźmy jako przykład 656123. Linia:

var tail = chars.Except(new List<char>(){c});

stosując wyjątkiem spowoduje wszystkie wystąpienia być usunięty, to znaczy gdy c = 6, dwie cyfry są usuwane, a my zostajemy z np 5123. Ponieważ żaden z rozwiązań Próbowałem rozwiązać ten, postanowiłem spróbować rozwiązać go samodzielnie przez FBryant87 S” kod jako podstawa. Oto, co wymyśliłem:

private static List<string> FindPermutations(string set)
    {
        var output = new List<string>();
        if (set.Length == 1)
        {
            output.Add(set);
        }
        else
        {
            foreach (var c in set)
            {
                // Remove one occurrence of the char (not all)
                var tail = set.Remove(set.IndexOf(c), 1);
                foreach (var tailPerms in FindPermutations(tail))
                {
                    output.Add(c + tailPerms);
                }
            }
        }
        return output;
    }

Po prostu usuwam pierwsze znalezione wystąpienie za pomocą .Remove i .IndexOf. Wygląda na to, że przynajmniej działa zgodnie z przeznaczeniem. Jestem pewien, że można by to uczynić mądrzejszym.

Należy jednak zwrócić uwagę na jedną rzecz: wynikowa lista może zawierać duplikaty, więc upewnij się, że metoda zwraca np. Zestaw HashSet lub usuwasz duplikaty po powrocie przy użyciu dowolnej metody.


Działa jak absolutne piękno, najpierw odkryłem, że obsługuje zduplikowane postacie +1
Jack Casey


5

Oto czysto funkcjonalna implementacja języka F #:


let factorial i =
    let rec fact n x =
        match n with
        | 0 -> 1
        | 1 -> x
        | _ -> fact (n-1) (x*n)
    fact i 1

let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a array) =
    if j = (r.Length + 1) then r
    else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }

Wydajność można znacznie poprawić, zmieniając zamianę, aby wykorzystać zmienną naturę tablic CLR, ale ta implementacja jest bezpieczna wątkowo w odniesieniu do tablicy źródłowej i może być pożądana w niektórych kontekstach. Ponadto w przypadku tablic zawierających więcej niż 16 elementów int należy zastąpić typami o większej / arbitralnej precyzji, ponieważ silnia 17 powoduje przepełnienie int32.


5

Oto proste rozwiązanie w języku C # przy użyciu rekurencji,

void Main()
{
    string word = "abc";
    WordPermuatation("",word);
}

void WordPermuatation(string prefix, string word)
{
    int n = word.Length;
    if (n == 0) { Console.WriteLine(prefix); }
    else
    {
        for (int i = 0; i < n; i++)
        {
            WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
        }
    }
}

Dziękuję za bardzo proste i krótkie rozwiązanie! :)
Kristaps Vilerts,

4

Oto łatwa do zrozumienia funkcja permutaion dla łańcucha i liczby całkowitej jako danych wejściowych. Dzięki temu możesz nawet ustawić długość wyjściową (która w normalnym przypadku jest równa długości wejściowej)

Strunowy

    static ICollection<string> result;

    public static ICollection<string> GetAllPermutations(string str, int outputLength)
    {
        result = new List<string>();
        MakePermutations(str.ToCharArray(), string.Empty, outputLength);
        return result;
    }

    private static void MakePermutations(
       char[] possibleArray,//all chars extracted from input
       string permutation,
       int outputLength//the length of output)
    {
         if (permutation.Length < outputLength)
         {
             for (int i = 0; i < possibleArray.Length; i++)
             {
                 var tempList = possibleArray.ToList<char>();
                 tempList.RemoveAt(i);
                 MakePermutations(tempList.ToArray(), 
                      string.Concat(permutation, possibleArray[i]), outputLength);
             }
         }
         else if (!result.Contains(permutation))
            result.Add(permutation);
    }

a dla Integer po prostu zmień metodę caller, a MakePermutations () pozostanie nietknięta:

    public static ICollection<int> GetAllPermutations(int input, int outputLength)
    {
        result = new List<string>();
        MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
        return result.Select(m => int.Parse(m)).ToList<int>();
    }

przykład 1: GetAllPermutations ("abc", 3); "abc" "acb" "bac" "bca" "cab" "cba"

przykład 2: GetAllPermutations ("abcd", 2); "ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"

przykład 3: GetAllPermutations (486,2); 48 46 84 86 64 68


Podoba mi się twoje rozwiązanie, ponieważ jest to łatwe do zrozumienia, dziękuję za to! Jednak zdecydowałem się na to: stackoverflow.com/questions/756055/… . Powodem jest to, że ToList, ToArray i RemoveAt mają złożoność czasową O (N). Więc w zasadzie musisz przejrzeć wszystkie elementy kolekcji (patrz stackoverflow.com/a/15042066/1132522 ). To samo dotyczy int, gdzie po prostu przechodzisz ponownie przez wszystkie elementy na końcu, aby przekonwertować je na int. Zgadzam się, że nie ma to większego wpływu na „abc” lub 486.
Andrew

2

Oto funkcja, która wypisze całą permutację. Ta funkcja implementuje logikę wyjaśnioną przez petera.

public class Permutation
{
    //http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm

    public static void permuteString(String beginningString, String endingString)
    {           

        if (endingString.Length <= 1)
            Console.WriteLine(beginningString + endingString);
        else
            for (int i = 0; i < endingString.Length; i++)
            {

                String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);

                permuteString(beginningString + endingString.ElementAt(i), newString);

            }
    }
}

    static void Main(string[] args)
    {

        Permutation.permuteString(String.Empty, "abc");
        Console.ReadLine();

    }

2

Poniżej znajduje się moja implementacja permutacji. Nie przejmuj się nazwami zmiennych, bo robiłem to dla przyjemności :)

class combinations
{
    static void Main()
    {

        string choice = "y";
        do
        {
            try
            {
                Console.WriteLine("Enter word :");
                string abc = Console.ReadLine().ToString();
                Console.WriteLine("Combinatins for word :");
                List<string> final = comb(abc);
                int count = 1;
                foreach (string s in final)
                {
                    Console.WriteLine("{0} --> {1}", count++, s);
                }
                Console.WriteLine("Do you wish to continue(y/n)?");
                choice = Console.ReadLine().ToString();
            }
            catch (Exception exc)
            {
                Console.WriteLine(exc);
            }
        } while (choice == "y" || choice == "Y");
    }

    static string swap(string test)
    {
        return swap(0, 1, test);
    }

    static List<string> comb(string test)
    {
        List<string> sec = new List<string>();
        List<string> first = new List<string>();
        if (test.Length == 1) first.Add(test);
        else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
        else if (test.Length > 2)
        {
            sec = generateWords(test);
            foreach (string s in sec)
            {
                string init = s.Substring(0, 1);
                string restOfbody = s.Substring(1, s.Length - 1);

                List<string> third = comb(restOfbody);
                foreach (string s1 in third)
                {
                    if (!first.Contains(init + s1)) first.Add(init + s1);
                }


            }
        }

        return first;
    }

    static string ShiftBack(string abc)
    {
        char[] arr = abc.ToCharArray();
        char temp = arr[0];
        string wrd = string.Empty;
        for (int i = 1; i < arr.Length; i++)
        {
            wrd += arr[i];
        }

        wrd += temp;
        return wrd;
    }

    static List<string> generateWords(string test)
    {
        List<string> final = new List<string>();
        if (test.Length == 1)
            final.Add(test);
        else
        {
            final.Add(test);
            string holdString = test;
            while (final.Count < test.Length)
            {
                holdString = ShiftBack(holdString);
                final.Add(holdString);
            }
        }

        return final;
    }

    static string swap(int currentPosition, int targetPosition, string temp)
    {
        char[] arr = temp.ToCharArray();
        char t = arr[currentPosition];
        arr[currentPosition] = arr[targetPosition];
        arr[targetPosition] = t;
        string word = string.Empty;
        for (int i = 0; i < arr.Length; i++)
        {
            word += arr[i];

        }

        return word;

    }
}

2

Oto przykład wysokiego poziomu, który napisałem, który ilustruje wyjaśnienie języka ludzkiego podane przez Piotra:

    public List<string> FindPermutations(string input)
    {
        if (input.Length == 1)
            return new List<string> { input };
        var perms = new List<string>();
        foreach (var c in input)
        {
            var others = input.Remove(input.IndexOf(c), 1);
            perms.AddRange(FindPermutations(others).Select(perm => c + perm));
        }
        return perms;
    }

To rozwiązanie jest w rzeczywistości błędne, ponieważ jeśli zestaw ciągów zawiera jakiekolwiek powtarzające się znaki, nie powiedzie się. Na przykład w słowie „test” polecenie Wyjątek usunie oba wystąpienia „t” zamiast tylko pierwszego i ostatniego, gdy będzie to konieczne.
Middas

1
@Middas dobrze zauważony, na szczęście Hug znalazł rozwiązanie tego problemu.
FBryant87

1

Jeśli problemem jest wydajność i pamięć, proponuję tę bardzo wydajną implementację. Według algorytmu Heapa w Wikipedii powinien on być najszybszy. Mam nadzieję, że będzie pasował do Twoich potrzeb :-)!

Podobnie jak porównanie tego z implementacją Linq dla 10! (zawiera kod):

  • To: 36288000 elementów w 235 milisekundach
  • Linq: 36288000 elementów w 50051 milisekundach

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    using System.Runtime.CompilerServices;
    using System.Text;
    
    namespace WpfPermutations
    {
        /// <summary>
        /// EO: 2016-04-14
        /// Generator of all permutations of an array of anything.
        /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
        /// </summary>
        public static class Permutations
        {
            /// <summary>
            /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
            /// </summary>
            /// <param name="items">Items to permute in each possible ways</param>
            /// <param name="funcExecuteAndTellIfShouldStop"></param>
            /// <returns>Return true if cancelled</returns> 
            public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
            {
                int countOfItem = items.Length;
    
                if (countOfItem <= 1)
                {
                    return funcExecuteAndTellIfShouldStop(items);
                }
    
                var indexes = new int[countOfItem];
                for (int i = 0; i < countOfItem; i++)
                {
                    indexes[i] = 0;
                }
    
                if (funcExecuteAndTellIfShouldStop(items))
                {
                    return true;
                }
    
                for (int i = 1; i < countOfItem;)
                {
                    if (indexes[i] < i)
                    { // On the web there is an implementation with a multiplication which should be less efficient.
                        if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                        {
                            Swap(ref items[i], ref items[indexes[i]]);
                        }
                        else
                        {
                            Swap(ref items[i], ref items[0]);
                        }
    
                        if (funcExecuteAndTellIfShouldStop(items))
                        {
                            return true;
                        }
    
                        indexes[i]++;
                        i = 1;
                    }
                    else
                    {
                        indexes[i++] = 0;
                    }
                }
    
                return false;
            }
    
            /// <summary>
            /// This function is to show a linq way but is far less efficient
            /// </summary>
            /// <typeparam name="T"></typeparam>
            /// <param name="list"></param>
            /// <param name="length"></param>
            /// <returns></returns>
            static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
            {
                if (length == 1) return list.Select(t => new T[] { t });
    
                return GetPermutations(list, length - 1)
                    .SelectMany(t => list.Where(e => !t.Contains(e)),
                        (t1, t2) => t1.Concat(new T[] { t2 }));
            }
    
            /// <summary>
            /// Swap 2 elements of same type
            /// </summary>
            /// <typeparam name="T"></typeparam>
            /// <param name="a"></param>
            /// <param name="b"></param>
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            static void Swap<T>(ref T a, ref T b)
            {
                T temp = a;
                a = b;
                b = temp;
            }
    
            /// <summary>
            /// Func to show how to call. It does a little test for an array of 4 items.
            /// </summary>
            public static void Test()
            {
                ForAllPermutation("123".ToCharArray(), (vals) =>
                {
                    Debug.Print(String.Join("", vals));
                    return false;
                });
    
                int[] values = new int[] { 0, 1, 2, 4 };
    
                Debug.Print("Non Linq");
                ForAllPermutation(values, (vals) =>
                {
                    Debug.Print(String.Join("", vals));
                    return false;
                });
    
                Debug.Print("Linq");
                foreach(var v in GetPermutations(values, values.Length))
                {
                    Debug.Print(String.Join("", v));
                }
    
                // Performance
                int count = 0;
    
                values = new int[10];
                for(int n = 0; n < values.Length; n++)
                {
                    values[n] = n;
                }
    
                Stopwatch stopWatch = new Stopwatch();
                stopWatch.Reset();
                stopWatch.Start();
    
                ForAllPermutation(values, (vals) =>
                {
                    foreach(var v in vals)
                    {
                        count++;
                    }
                    return false;
                });
    
                stopWatch.Stop();
                Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
    
                count = 0;
                stopWatch.Reset();
                stopWatch.Start();
    
                foreach (var vals in GetPermutations(values, values.Length))
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                }
    
                stopWatch.Stop();
                Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
    
            }
        }
    }

1

Oto moje rozwiązanie w JavaScript (NodeJS). Główną ideą jest to, że bierzemy po jednym elemencie na raz, "usuwamy go" z łańcucha, zmieniamy pozostałe znaki i wstawiamy element z przodu.

function perms (string) {
  if (string.length == 0) {
    return [];
  }
  if (string.length == 1) {
    return [string];
  }
  var list = [];
  for(var i = 0; i < string.length; i++) {
    var invariant = string[i];
    var rest = string.substr(0, i) + string.substr(i + 1);
    var newPerms = perms(rest);
    for (var j = 0; j < newPerms.length; j++) {
      list.push(invariant + newPerms[j]);
    }
  }
  return list;
}

module.exports = perms;

A oto testy:

require('should');
var permutations = require('../src/perms');

describe('permutations', function () {
  it('should permute ""', function () {
    permutations('').should.eql([]);
  })

  it('should permute "1"', function () {
    permutations('1').should.eql(['1']);
  })

  it('should permute "12"', function () {
    permutations('12').should.eql(['12', '21']);
  })

  it('should permute "123"', function () {
    var expected = ['123', '132', '321', '213', '231', '312'];
    var actual = permutations('123');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })

  it('should permute "1234"', function () {
    // Wolfram Alpha FTW!
    var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
    var actual = permutations('1234');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })
})

1

Oto najprostsze rozwiązanie, jakie przychodzi mi do głowy:

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs

distributeFunkcja przyjmuje nowego elementu eoraz nlisty -elementowe i zwraca listę n+1list z których każdy ma ewłożonych w innym miejscu. Na przykład wstawianie 10w każdym z czterech możliwych miejsc na liście [1;2;3]:

> distribute 10 [1..3];;
val it : int list list =
  [[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]

permuteFunkcja fałdy nad każdym elementem z kolei nad dystrybucją permutacji zgromadzone do tej pory, zakończonego we wszystkich permutacji. Na przykład 6 permutacji listy [1;2;3]:

> permute [1;2;3];;
val it : int list list =
  [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]

Zmiana na folda scanw celu zachowania akumulatorów pośrednich rzuca trochę światła na to, jak permutacje są generowane po jednym elemencie:

> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
  seq
    [[[]]; [[1]]; [[2; 1]; [1; 2]];
     [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]

1

Wyświetla permutacje ciągu. Pozwala uniknąć powielania, gdy znaki się powtarzają:

using System;
using System.Collections;

class Permutation{
  static IEnumerable Permutations(string word){
    if (word == null || word.Length <= 1) {
      yield return word;
      yield break;
    }

    char firstChar = word[0];
    foreach( string subPermute in Permutations (word.Substring (1)) ) {
      int indexOfFirstChar = subPermute.IndexOf (firstChar);
      if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;

      for( int index = 0; index <= indexOfFirstChar; index++ )
        yield return subPermute.Insert (index, new string (firstChar, 1));
    }
  }

  static void Main(){
    foreach( var permutation in Permutations ("aab") )
      Console.WriteLine (permutation);
  }
}

2
Przy tak wielu już działających rozwiązaniach możesz chcieć opisać, co wyróżnia Twoje rozwiązanie spośród wszystkich innych rozwiązań tutaj.
nvoigt

Unika powielania, gdy znaki są powtarzane (przez chindirala dla innej odpowiedzi). Dla „aab”: aab aba baa
Val

1

Opierając się na rozwiązaniu @ Peter, oto wersja, która deklaruje prostą Permutations()metodę rozszerzenia w stylu LINQ, która działa na dowolnym IEnumerable<T>.

Użycie (na przykładzie znaków ciągu):

foreach (var permutation in "abc".Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Wyjścia:

a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
c, a, b

Lub w przypadku każdego innego rodzaju kolekcji:

foreach (var permutation in (new[] { "Apples", "Oranges", "Pears"}).Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Wyjścia:

Apples, Oranges, Pears
Apples, Pears, Oranges
Oranges, Apples, Pears
Oranges, Pears, Apples
Pears, Oranges, Apples
Pears, Apples, Oranges
using System;
using System.Collections.Generic;
using System.Linq;

public static class PermutationExtension
{
    public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> source)
    {
        var sourceArray = source.ToArray();
        var results = new List<T[]>();
        Permute(sourceArray, 0, sourceArray.Length - 1, results);
        return results;
    }

    private static void Swap<T>(ref T a, ref T b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    private static void Permute<T>(T[] elements, int recursionDepth, int maxDepth, ICollection<T[]> results)
    {
        if (recursionDepth == maxDepth)
        {
            results.Add(elements.ToArray());
            return;
        }

        for (var i = recursionDepth; i <= maxDepth; i++)
        {
            Swap(ref elements[recursionDepth], ref elements[i]);
            Permute(elements, recursionDepth + 1, maxDepth, results);
            Swap(ref elements[recursionDepth], ref elements[i]);
        }
    }
}

0

Oto funkcja, która wypisze rekursywnie wszystkie permutacje.

public void Permutations(string input, StringBuilder sb)
    {
        if (sb.Length == input.Length)
        {
            Console.WriteLine(sb.ToString());
            return;
        }

        char[] inChar = input.ToCharArray();

        for (int i = 0; i < input.Length; i++)
        {
            if (!sb.ToString().Contains(inChar[i]))
            {
                sb.Append(inChar[i]);
                Permutations(input, sb);    
                RemoveChar(sb, inChar[i]);
            }
        }
    }

private bool RemoveChar(StringBuilder input, char toRemove)
    {
        int index = input.ToString().IndexOf(toRemove);
        if (index >= 0)
        {
            input.Remove(index, 1);
            return true;
        }
        return false;
    }

0
class Permutation
{
    public static List<string> Permutate(string seed, List<string> lstsList)
    {
        loopCounter = 0;
        // string s="\w{0,2}";
        var lstStrs = PermuateRecursive(seed);

        Trace.WriteLine("Loop counter :" + loopCounter);
        return lstStrs;
    }

    // Recursive function to find permutation
    private static List<string> PermuateRecursive(string seed)
    {
        List<string> lstStrs = new List<string>();

        if (seed.Length > 2)
        {
            for (int i = 0; i < seed.Length; i++)
            {
                str = Swap(seed, 0, i);

                PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
                    s =>
                    {
                        lstStrs.Add(str[0] + s);
                        loopCounter++;
                    });
                ;
            }
        }
        else
        {
            lstStrs.Add(seed);
            lstStrs.Add(Swap(seed, 0, 1));
        }
        return lstStrs;
    }
    //Loop counter variable to count total number of loop execution in various functions
    private static int loopCounter = 0;

    //Non recursive  version of permuation function
    public static List<string> Permutate(string seed)
    {
        loopCounter = 0;
        List<string> strList = new List<string>();
        strList.Add(seed);
        for (int i = 0; i < seed.Length; i++)
        {
            int count = strList.Count;
            for (int j = i + 1; j < seed.Length; j++)
            {
                for (int k = 0; k < count; k++)
                {
                    strList.Add(Swap(strList[k], i, j));
                    loopCounter++;
                }
            }
        }
        Trace.WriteLine("Loop counter :" + loopCounter);
        return strList;
    }

    private static string Swap(string seed, int p, int p2)
    {
        Char[] chars = seed.ToCharArray();
        char temp = chars[p2];
        chars[p2] = chars[p];
        chars[p] = temp;
        return new string(chars);
    }
}

0

Oto odpowiedź w języku C #, która jest nieco uproszczona.

public static void StringPermutationsDemo()
{
    strBldr = new StringBuilder();

    string result = Permute("ABCD".ToCharArray(), 0);
    MessageBox.Show(result);
}     

static string Permute(char[] elementsList, int startIndex)
{
    if (startIndex == elementsList.Length)
    {
        foreach (char element in elementsList)
        {
            strBldr.Append(" " + element);
        }
        strBldr.AppendLine("");
    }
    else
    {
        for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
        {
            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);

            Permute(elementsList, (startIndex + 1));

            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
        }
    }

    return strBldr.ToString();
}

static void Swap(ref char Char1, ref char Char2)
{
    char tempElement = Char1;
    Char1 = Char2;
    Char2 = tempElement;
}

Wynik:

1 2 3
1 3 2

2 1 3
2 3 1

3 2 1
3 1 2

0

To jest moje rozwiązanie, które jest dla mnie łatwe do zrozumienia

class ClassicPermutationProblem
{
    ClassicPermutationProblem() { }

    private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
    {
         foreach (T element in list)
         {
             List<T> currentTemp = temp.ToList();
             if (!currentTemp.Contains(element))
                currentTemp.Add(element);
             else
                continue;

             if (position == list.Count)
                finalList.Add(currentTemp);
             else
                PopulatePosition(finalList, list, currentTemp, position + 1);
        }
    }

    public static List<List<int>> GetPermutations(List<int> list)
    {
        List<List<int>> results = new List<List<int>>();
        PopulatePosition(results, list, new List<int>(), 1);
        return results;
     }
}

static void Main(string[] args)
{
    List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}

0

Oto jeszcze jedna implementacja wspomnianego algo.

public class Program
{
    public static void Main(string[] args)
    {
        string str = "abcefgh";
        var astr = new Permutation().GenerateFor(str);
        Console.WriteLine(astr.Length);
        foreach(var a in astr)
        {
            Console.WriteLine(a);
        }
        //a.ForEach(Console.WriteLine);
    }
}

class Permutation
{
    public string[] GenerateFor(string s)
    {  

        if(s.Length == 1)
        {

            return new []{s}; 
        }

        else if(s.Length == 2)
        {

            return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};

        }

        var comb = new List<string>();

        foreach(var c in s)
        {

            string cStr = c.ToString();

            var sToProcess = s.Replace(cStr,"");
            if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
            {
                var conCatStr = GenerateFor(sToProcess);



                foreach(var a in conCatStr)
                {
                    comb.Add(c.ToString()+a);
                }


            }
        }
        return comb.ToArray();

    }
}

new Permutation().GenerateFor("aba")wyjściastring[4] { "ab", "baa", "baa", "ab" }
Atomosk

0
    //Generic C# Method
            private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
            {
                var perms = new List<T[]>();

                var l = input.Length - 1;

                if (l == startIndex)
                    perms.Add(input);
                else
                {

                    for (int i = startIndex; i <= l; i++)
                    {
                        var copy = input.ToArray(); //make copy

                        var temp = copy[startIndex];

                        copy[startIndex] = copy[i];
                        copy[i] = temp;

                        perms.AddRange(GetPerms(copy, startIndex + 1));

                    }
                }

                return perms;
            }

            //usages
            char[] charArray = new char[] { 'A', 'B', 'C' };
            var charPerms = GetPerms(charArray);


            string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
            var stringPerms = GetPerms(stringArray);


            int[] intArray = new int[] { 1, 2, 3 };
            var intPerms = GetPerms(intArray);

Byłoby wspaniale, gdybyś mógł trochę rozwinąć, jak działa ten kod, zamiast zostawiać go tutaj w spokoju.
iBug

-1
    /// <summary>
    /// Print All the Permutations.
    /// </summary>
    /// <param name="inputStr">input string</param>
    /// <param name="strLength">length of the string</param>
    /// <param name="outputStr">output string</param>
    private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars)
    {
        //Means you have completed a permutation.
        if (outputStr.Length == NumberOfChars)
        {
            Console.WriteLine(outputStr);                
            return;
        }

        //For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc.
        for(int i=0 ; i< strLength; i++)
        {
            // Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc.
            PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4);
        }
    }        
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.