Algorytm do generowania wszystkich możliwych permutacji listy?

119

Powiedzmy, że mam listę n elementów, wiem, że jest n! możliwe sposoby zamówienia tych elementów. Jaki jest algorytm generujący wszystkie możliwe uporządkowania tej listy? Przykład, mam listę [a, b, c]. Algorytm zwróciłby [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , a]].

Czytam to tutaj http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Ale Wikipedia nigdy nie była dobra w wyjaśnianiu. Niewiele z tego rozumiem.

fent
źródło
5
Napisałem kiedyś obszerną odpowiedź na inne pytanie dotyczące generowania permutacji. Myślę, że Cię to zainteresuje: stackoverflow.com/questions/1506078/…
Joren
2
To może rozwiązać twój problem. En.wikipedia.org/wiki/Heap's_algorithm
Felix

Odpowiedzi:

96

Zasadniczo dla każdego elementu od lewej do prawej generowane są wszystkie permutacje pozostałych elementów (i każdy z nich jest dodawany z bieżącymi elementami). Można to zrobić rekurencyjnie (lub iteracyjnie, jeśli lubisz ból), aż do osiągnięcia ostatniego elementu, w którym to momencie jest tylko jedno możliwe zamówienie.

Tak więc z listą [1, 2, 3, 4] generowane są wszystkie permutacje, które zaczynają się od 1, a następnie wszystkie permutacje zaczynające się od 2, potem 3 i 4.

To skutecznie redukuje problem ze znalezienia permutacji listy czterech pozycji do listy trzech pozycji. Po zredukowaniu list pozycji do 2, a następnie 1, wszystkie zostaną znalezione.
Przykład pokazujący permutacje procesów przy użyciu 3 kolorowych kul:
Czerwone, zielone i niebieskie kule uporządkowały obraz permutacji(z https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB. svg )

Trąba powietrzna
źródło
2
Na początku też o tym myślałem, ale wtedy bieżący element nie zostałby wstawiony między niektóre z poniższych. Więc nie wszystkie permutacje zostaną wygenerowane.
wyzwolony
@LLer przepraszam, zaktualizowałem moją odpowiedź z „obserwujący” na „pozostały”, aby wyjaśnić. Ale działa dobrze. Sprawdź to, pisząc kod i sprawdzając, czy otrzymujesz 4! różne wyniki.
WhirlWind
2
permutacje int (int n, wektor <int> a) {static int num_permutations = 0; if (n == (a.size () - 1)) {for (int i = 0; i <a.size (); i ++) cout << a [i] << ""; cout << "\ n"; num_permutations ++; } else {for (int i = n + 1; i <= a.size (); i ++) {permutations (n ​​+ 1, a); if (i <a.size ()) int temp = a [n], a [n] = a [i], a [i] = temp; }} return num_permutations; } int main (void) {vector <int> v; v.push_back (1); ... zwraca permutacje (0, v); }
Somesh
Ups - nie wiem, jak sformatować kod w komentarzu ... Przetestowałem kod z 7 i otrzymałem 5040. Dzięki @WhirlWind za sugestię.
Somesh
Czy to się nie zmienia, jeśli możesz mieć 2 lub 3 czerwone kulki nr 1 zamiast tylko 1 w każdym kolorze?
Alexander Mills,
26

Oto algorytm w Pythonie, który działa w miejscu na tablicy:

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p

Możesz sam wypróbować kod tutaj: http://repl.it/J9v

cdiggins
źródło
Czy możesz wyjaśnić część dotyczącą wydajności? Nie mogłem uruchomić kodu na sucho. Z góry dziękuję.
Agniswar Bakshi
Pytanie o przepełnienie stosu na stackoverflow.com/questions/104420/ ... stwierdza, że ​​istnieje standardowy moduł biblioteki w wersji 2.6 i nowszych i zawiera odpowiedź zapewniającą 6-wierszowe rozwiązanie w funkcji uzyskiwania list permutacji.
Edward
@Agniswar W skrócie, instrukcja yield służy do definiowania generatorów, zastępując zwrot funkcji w celu dostarczenia wyniku jej wywołującemu bez niszczenia zmiennych lokalnych. W przeciwieństwie do funkcji, w której przy każdym wywołaniu zaczyna się od nowego zestawu zmiennych, generator wznowi wykonanie od miejsca, w którym zostało przerwane. pythoncentral.io/python-generators-and-yield-keyword
MSS
To rozwiązanie nie zadziała w przypadku obsługi listy identycznych wpisów.
KaiserKatze
Dzięki za udostępnienie. Jest to intuicyjne i wydajne, chociaż wyniki nie są uporządkowane leksykograficznie.
Sam
16

Jest już tutaj wiele dobrych rozwiązań, ale chciałbym podzielić się tym, jak samodzielnie rozwiązałem ten problem i mam nadzieję, że może to być pomocne dla kogoś, kto również chciałby znaleźć własne rozwiązanie.

Po zastanowieniu się nad problemem doszedłem do dwóch następujących wniosków:

  1. Aby uzyskać listę Lrozmiarówn będzie równa liczba rozwiązań zaczynających się od L 1 , L 2 ... L n elementów listy. Ponieważ w sumie istnieją n!permutacje listy rozmiarów n, otrzymujemy n! / n = (n-1)!permutacje w każdej grupie.
  2. Lista 2 elementów ma tylko 2 permutacje => [a,b]i [b,a].

Korzystając z tych dwóch prostych pomysłów, wyprowadziłem następujący algorytm:

permute array
    if array is of size 2
       return first and second element as new array
       return second and first element as new array
    else
        for each element in array
            new subarray = array with excluded element
            return element + permute subarray

Oto jak zaimplementowałem to w C #:

public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
    if (input.Count == 2) // this are permutations of array of size 2
    {
        yield return new List<T>(input);
        yield return new List<T> {input[1], input[0]}; 
    }
    else
    {
        foreach(T elem in input) // going through array
        {
            var rlist = new List<T>(input); // creating subarray = array
            rlist.Remove(elem); // removing element
            foreach(List<T> retlist in Permutate(rlist))
            {
                retlist.Insert(0,elem); // inserting the element at pos 0
                yield return retlist;
            }

        }
    }
}
Alexander Galkin
źródło
16

Odpowiedź Wikipedii na „porządek leksykograficzny” wydaje mi się całkowicie jednoznaczna w stylu książki kucharskiej. Przytacza XIV-wieczne pochodzenie algorytmu!

Właśnie napisałem szybką implementację algorytmu Wikipedii w Javie jako czek i nie było problemu. Ale to, co masz w swoim Q jako przykład, to NIE "lista wszystkich permutacji", ale "LISTA wszystkich permutacji", więc Wikipedia nie będzie dla ciebie zbyt pomocna. Potrzebujesz języka, w którym listy permutacji są wykonalne. I wierz mi, listy długie na kilka miliardów zwykle nie są obsługiwane w językach imperatywnych. Naprawdę chcesz, aby nie ścisły funkcjonalny język programowania, w którym listy są obiektem pierwszej klasy, aby wydobyć rzeczy, nie doprowadzając maszyny do bliskiej śmierci Wszechświata.

To łatwe. W standardowym języku Haskell lub dowolnym nowoczesnym języku FP:

-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms []     = [ [] ]

i

-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits []     = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]
Peter Breuer
źródło
9

Jak powiedział WhirlWind, zaczynasz od początku.

Zamieniasz kursor z każdą pozostałą wartością, w tym z samym kursorem, są to wszystkie nowe instancje (użyłem int[]i array.clone()w przykładzie).

Następnie wykonaj permutacje na wszystkich tych różnych listach, upewniając się, że kursor znajduje się o jeden po prawej stronie.

Gdy nie ma już pozostałych wartości (kursor znajduje się na końcu), wydrukuj listę. To jest warunek zatrzymania.

public void permutate(int[] list, int pointer) {
    if (pointer == list.length) {
        //stop-condition: print or process number
        return;
    }
    for (int i = pointer; i < list.length; i++) {
        int[] permutation = (int[])list.clone();.
        permutation[pointer] = list[i];
        permutation[i] = list[pointer];
        permutate(permutation, pointer + 1);
    }
}
dinadineke
źródło
8

Utrzymanie rekurencji zawsze wymaga wysiłku umysłowego. A w przypadku dużych liczb silnia jest z łatwością ogromna, a przepełnienie stosu z łatwością będzie problemem.

W przypadku małych liczb (3 lub 4, które są najczęściej spotykane), wiele pętli jest dość prostych i prostych. To niefortunne odpowiedzi, w których pętle nie zostały ocenione.

Zacznijmy od wyliczenia (zamiast permutacji). Po prostu przeczytaj kod jako kod pseudo Perla.

$foreach $i1 in @list
    $foreach $i2 in @list 
        $foreach $i3 in @list
            print "$i1, $i2, $i3\n"

Wyliczenie jest częściej spotykane niż permutacja, ale jeśli potrzebna jest permutacja, po prostu dodaj warunki:

$foreach $i1 in @list
    $foreach $i2 in @list 
        $if $i2==$i1
            next
        $foreach $i3 in @list
            $if $i3==$i1 or $i3==$i2
                next
            print "$i1, $i2, $i3\n"

Teraz, jeśli naprawdę potrzebujesz ogólnej metody potencjalnie dla dużych list, możemy użyć metody radix. Najpierw rozważ problem wyliczenia:

$n=@list
my @radix
$for $i=0:$n
    $radix[$i]=0
$while 1
    my @temp
    $for $i=0:$n
        push @temp, $list[$radix[$i]]
    print join(", ", @temp), "\n"
    $call radix_increment

subcode: radix_increment
    $i=0
    $while 1
        $radix[$i]++
        $if $radix[$i]==$n
            $radix[$i]=0
            $i++
        $else
            last
    $if $i>=$n
        last

Przyrost radix jest zasadniczo zliczaniem liczb (w podstawie liczby elementów listy).

Teraz, jeśli potrzebujesz permutacji, po prostu dodaj sprawdzenia wewnątrz pętli:

subcode: check_permutation
    my @check
    my $flag_dup=0
    $for $i=0:$n
        $check[$radix[$i]]++
        $if $check[$radix[$i]]>1
            $flag_dup=1
            last
    $if $flag_dup
        next

Edycja: powyższy kod powinien działać, ale w przypadku permutacji radix_increment może być marnotrawstwem. Więc jeśli czas ma znaczenie praktyczne, musimy zmienić radix_increment na permute_inc:

subcode: permute_init
    $for $i=0:$n
        $radix[$i]=$i

subcode: permute_inc                                       
    $max=-1                                                
    $for $i=$n:0                                           
        $if $max<$radix[$i]                                
            $max=$radix[$i]                                
        $else                                              
            $for $j=$n:0                                   
                $if $radix[$j]>$radix[$i]                  
                    $call swap, $radix[$i], $radix[$j]     
                    break                                  
            $j=$i+1                                        
            $k=$n-1                                        
            $while $j<$k                                   
                $call swap, $radix[$j], $radix[$k]         
                $j++                                       
                $k--                                       
            break                                          
    $if $i<0                                               
        break                                              

Oczywiście teraz ten kod jest logicznie bardziej złożony, zostawię czytelnikowi ćwiczenie.

Hui Zhou
źródło
7

wprowadź opis obrazu tutaj

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Źródła : Geeksforgeeks.org

Sazzad Hissain Khan
źródło
5

Jeśli ktoś się zastanawia jak to zrobić w permutacji w javascript.

Pomysł / pseudokod

  1. wybieraj jeden element na raz
  2. permutuj resztę elementu, a następnie dodaj wybrany element do całej permutacji

na przykład. „a” + permute (bc). permutą bc byłoby bc & cb. Teraz dodaj te dwa, aby uzyskać abc, acb. podobnie, wybierz b + permute (ac) będzie sprzyjać bac, bca ... i kontynuować.

teraz spójrz na kod

function permutations(arr){

   var len = arr.length, 
       perms = [],
       rest,
       picked,
       restPerms,
       next;

    //for one or less item there is only one permutation 
    if (len <= 1)
        return [arr];

    for (var i=0; i<len; i++)
    {
        //copy original array to avoid changing it while picking elements
        rest = Object.create(arr);

        //splice removed element change array original array(copied array)
        //[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
        picked = rest.splice(i, 1);

        //get the permutation of the rest of the elements
        restPerms = permutations(rest);

       // Now concat like a+permute(bc) for each
       for (var j=0; j<restPerms.length; j++)
       {
           next = picked.concat(restPerms[j]);
           perms.push(next);
       }
    }

   return perms;
}

Nie spiesz się, aby to zrozumieć. Mam ten kod z ( pertumation w JavaScript )

Jhankar Mahbub
źródło
Myślałem o czymś podobnym, ale czy nie powinieneś dodawać wybranego elementu zarówno z przodu, jak i na końcu pozostałych paramów? W tym przypadku dla „abc”, jeśli wybierzesz a, to permutacjami „bc” będą „bc” i „cb”. Kiedy dodajesz „a” z powrotem do listy, czy nie należy dodawać go na początku jako „a + bc” + „a + cb”, ale także na końcu jako „bc + a” + „cb + a” z Lista?
Artimus
Otrzymasz te permutacje, gdy permutujesz zaczynając odpowiednio od „b” i „c”. (tj. drugi i trzeci bieg zewnętrznej pętli „for”)
Ryan O'Neill
3

Kolejny w Pythonie, nie jest na miejscu jak @ cdiggins, ale myślę, że jest łatwiejszy do zrozumienia

def permute(num):
    if len(num) == 2:
        # get the permutations of the last 2 numbers by swapping them
        yield num
        num[0], num[1] = num[1], num[0]
        yield num
    else:
        for i in range(0, len(num)):
            # fix the first number and get the permutations of the rest of numbers
            for perm in permute(num[0:i] + num[i+1:len(num)]):
                yield [num[i]] + perm

for p in permute([1, 2, 3, 4]):
    print p
zhywu
źródło
3

Myślałem o napisaniu kodu do uzyskania permutacji dowolnej liczby całkowitej dowolnego rozmiaru, tj. Podając liczbę 4567 otrzymujemy wszystkie możliwe permutacje do 7654 ... Więc pracowałem nad tym, znalazłem algorytm i ostatecznie zaimplementowałem go, tutaj to kod zapisany w „c”. Możesz go po prostu skopiować i uruchomić na dowolnym kompilatorze open source. Ale niektóre błędy czekają na debugowanie. Proszę docenić.

Kod:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

                //PROTOTYPES

int fact(int);                  //For finding the factorial
void swap(int*,int*);           //Swapping 2 given numbers
void sort(int*,int);            //Sorting the list from the specified path
int imax(int*,int,int);         //Finding the value of imax
int jsmall(int*,int);           //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm();                    //All the important tasks are done in this function


int n;                         //Global variable for input OR number of digits

void main()
{
int c=0;

printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}

void perm(int c){
int *p;                     //Pointer for allocating separate memory to every single entered digit like arrays
int i, d;               
int sum=0;
int j, k;
long f;

n = 0;

while(c != 0)               //this one is for calculating the number of digits in the entered number
{
    sum = (sum * 10) + (c % 10);
    n++;                            //as i told at the start of loop
    c = c / 10;
}

f = fact(n);                        //It gives the factorial value of any number

p = (int*) malloc(n*sizeof(int));                //Dynamically allocation of array of n elements

for(i=0; sum != 0 ; i++)
{
    *(p+i) = sum % 10;                               //Giving values in dynamic array like 1234....n separately
    sum = sum / 10;
}

sort(p,-1);                                         //For sorting the dynamic array "p"

for(c=0 ; c<f/2 ; c++) {                        //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);                       //Loop for printing one of permutations
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);                            //provides the max i as per algo (i am restricted to this only)
    j = i;
    j = jsmall(p,j);                            //provides smallest i val as per algo
    swap(&p[i],&p[j]);

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);
    j = i;
    j = jsmall(p,j);
    swap(&p[i],&p[j]);

    sort(p,i);
}
free(p);                                        //Deallocating memory
}

int fact (int a)
{
long f=1;
while(a!=0)
{
    f = f*a;
    a--;
}
return f;
}


void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}


void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
    for(j=i+1 ; j<n ; j++)
    {
        if(*(p+i) > *(p+j))
        {
            temp = *(p+i);
            *(p+i) = *(p+j);
            *(p+j) = temp;
        }
    }
}
}


int imax(int *p, int i , int d)
{
    while(i<n-1 && d<n-1)
{
    if(*(p+d) < *(p+d+1))
    {   
        i = d;
        d++;
    }
    else
        d++;
}
return i;
}


int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
    if (p[i]<small && p[i]>p[k])
    {     
       small = p[i];
       j = i;
    }
}
return j;
}
FreakPirate
źródło
3
void permutate(char[] x, int i, int n){
    x=x.clone();
    if (i==n){
        System.out.print(x);
        System.out.print(" ");
        counter++;}
    else
    {
        for (int j=i; j<=n;j++){
     //   System.out.print(temp); System.out.print(" ");    //Debugger
        swap (x,i,j);
      //  System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
        permutate(x,i+1,n);
    //    swap (temp,i,j);
    }
    }
}

void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}

Stworzyłem ten. oparte na badaniach zbyt permutacja (qwe, 0, qwe.length-1); Pamiętaj, że możesz to zrobić z cofaniem lub bez

Luigi Mackenzie C. Brito
źródło
3

Oto metoda Ruby z zabawkami, która działa w ten sposób #permutation.to_a, może być bardziej czytelna dla szalonych ludzi. Jest bardzo powolny, ale także 5 linii.

def permute(ary)
  return [ary] if ary.size <= 1
  ary.collect_concat.with_index do |e, i|
    rest = ary.dup.tap {|a| a.delete_at(i) }
    permute(rest).collect {|a| a.unshift(e) }
  end
end
Jenner La Fave
źródło
3

Napisałem to rozwiązanie rekurencyjne w ANSI C. Każde wykonanie funkcji Permutate zapewnia jedną inną permutację, aż wszystkie zostaną ukończone. Zmienne globalne mogą być również używane do zmiennych faktów i liczb.

#include <stdio.h>
#define SIZE 4

void Rotate(int vec[], int size)
{
    int i, j, first;

    first = vec[0];
    for(j = 0, i = 1; i < size; i++, j++)
    {
        vec[j] = vec[i];
    }
    vec[j] = first;
}

int Permutate(int *start, int size, int *count)
{
    static int fact;

    if(size > 1)
    {
        if(Permutate(start + 1, size - 1, count))
        {
            Rotate(start, size);
        }
        fact *= size;
    }
    else
    {
        (*count)++;
        fact = 1;
    }

    return !(*count % fact);
}

void Show(int vec[], int size)
{
    int i;

    printf("%d", vec[0]);
    for(i = 1; i < size; i++)
    {
        printf(" %d", vec[i]);
    }
    putchar('\n');
}

int main()
{
    int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
    int count = 0;

    do
    {
        Show(vec, SIZE);
    } while(!Permutate(vec, SIZE, &count));

    putchar('\n');
    Show(vec, SIZE);
    printf("\nCount: %d\n\n", count);

    return 0;
}
Horacio
źródło
3

Wersja Java

/**
 * @param uniqueList
 * @param permutationSize
 * @param permutation
 * @param only            Only show the permutation of permutationSize,
 *                        else show all permutation of less than or equal to permutationSize.
 */
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
    if (permutation == null) {
        assert 0 < permutationSize && permutationSize <= uniqueList.size();
        permutation = new ArrayList<>(permutationSize);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
    }
    for (int i : uniqueList) {
        if (permutation.contains(i)) {
            continue;
        }
        permutation.add(i);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        } else if (permutation.size() == permutationSize) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
        if (permutation.size() < permutationSize) {
            my_permutationOf(uniqueList, permutationSize, permutation, only);
        }
        permutation.remove(permutation.size() - 1);
    }
}

Na przykład

public static void main(String[] args) throws Exception { 
    my_permutationOf(new ArrayList<Integer>() {
        {
            add(1);
            add(2);
            add(3);

        }
    }, 3, null, true);
}

wynik:

  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]
Bruce Zu
źródło
3

w PHP

$set=array('A','B','C','D');

function permutate($set) {
    $b=array();
    foreach($set as $key=>$value) {
        if(count($set)==1) {
            $b[]=$set[$key];
        }
        else {
            $subset=$set;
            unset($subset[$key]);
            $x=permutate($subset);
            foreach($x as $key1=>$value1) {
                $b[]=$value.' '.$value1;
            }
        }
    }
    return $b;
}

$x=permutate($set);
var_export($x);
nerdface
źródło
3

Oto kod w Pythonie do wydrukowania wszystkich możliwych permutacji listy:

def next_perm(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    print arr
    return True

def all_perm(arr):
    a = next_perm(arr)
    while a:
        a = next_perm(arr)
    arr = raw_input()
    arr.split(' ')
    arr = map(int, arr)
    arr.sort()
    print arr
    all_perm(arr)

Użyłem algorytmu porządku leksykograficznego, aby uzyskać wszystkie możliwe permutacje, ale algorytm rekurencyjny jest bardziej wydajny. Możesz znaleźć kod algorytmu rekurencyjnego tutaj: Permutacje rekurencyjne w Pythonie

Anuj Mittal
źródło
3
public class PermutationGenerator
{
    private LinkedList<List<int>> _permutationsList;
    public void FindPermutations(List<int> list, int permutationLength)
    {
        _permutationsList = new LinkedList<List<int>>();
        foreach(var value in list)
        {
            CreatePermutations(value, permutationLength);
        }
    }

    private void CreatePermutations(int value, int permutationLength)
    {
        var node = _permutationsList.First;
        var last = _permutationsList.Last;
        while (node != null)
        {
            if (node.Value.Count < permutationLength)
            {
                GeneratePermutations(node.Value, value, permutationLength);
            }
            if (node == last)
            {
                break;
            }
            node = node.Next;
        }

        List<int> permutation = new List<int>();
        permutation.Add(value);
        _permutationsList.AddLast(permutation);
    }

    private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
    {
       if (permutation.Count < permutationLength)
        {
            List<int> copyOfInitialPermutation = new List<int>(permutation);
            copyOfInitialPermutation.Add(value);
            _permutationsList.AddLast(copyOfInitialPermutation);
            List<int> copyOfPermutation = new List<int>();
            copyOfPermutation.AddRange(copyOfInitialPermutation);
            int lastIndex = copyOfInitialPermutation.Count - 1;
            for (int i = lastIndex;i > 0;i--)
            {
                int temp = copyOfPermutation[i - 1];
                copyOfPermutation[i - 1] = copyOfPermutation[i];
                copyOfPermutation[i] = temp;

                List<int> perm = new List<int>();
                perm.AddRange(copyOfPermutation);
                _permutationsList.AddLast(perm);
            }
        }
    }

    public void PrintPermutations(int permutationLength)
    {
        int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
        Console.WriteLine("The number of permutations is " + count);
    }
}
Bahruz Balabayov
źródło
to przydatna odpowiedź
Ayaz Alifov
2

W Scala

    def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)



def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {

    var result: List[List[Int]] = Nil
    for (i ← n if (!(acc contains (i))))
        if (acc.size == n.size-1)
            result = (i :: acc) :: result
        else
            result = result ::: permutationeAcc(n, i :: acc)
    result
}
Marco
źródło
2

to jest wersja Java do permutacji

public class Permutation {

    static void permute(String str) {
        permute(str.toCharArray(), 0, str.length());
    }

    static void permute(char [] str, int low, int high) {
        if (low == high) {
            System.out.println(str);
            return;
        }

        for (int i=low; i<high; i++) {
            swap(str, i, low);
            permute(str, low+1, high);
            swap(str, low, i);
        }

    }

    static void swap(char [] array, int i, int j) {
        char t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
杨小勇
źródło
2

Oto implementacja ColdFusion (wymaga CF10 ze względu na argument merge funkcji ArrayAppend ()):

public array function permutateArray(arr){

    if (not isArray(arguments.arr) ) {
        return ['The ARR argument passed to the permutateArray function is not of type array.'];    
    }

    var len = arrayLen(arguments.arr);
    var perms = [];
    var rest = [];
    var restPerms = [];
    var rpLen = 0;
    var next = [];

    //for one or less item there is only one permutation 
    if (len <= 1) {
        return arguments.arr;
    }

    for (var i=1; i <= len; i++) {
        // copy the original array so as not to change it and then remove the picked (current) element
        rest = arraySlice(arguments.arr, 1);
        arrayDeleteAt(rest, i);

         // recursively get the permutation of the rest of the elements
         restPerms = permutateArray(rest);
         rpLen = arrayLen(restPerms);

        // Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
        for (var j=1; j <= rpLen; j++) {
            // for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
            next = arraySlice(arguments.arr, i, 1);
            arrayAppend(next, restPerms[j], true);
            arrayAppend(perms, next);
        }
     }

    return perms;
}

Oparte na rozwiązaniu js firmy KhanSharp powyżej.

bóle uszufl
źródło
Pewne wyjaśnienie ogólnej strategii algorytmu byłoby dobrym sposobem na ulepszenie tej odpowiedzi.
Richard,
Skąd więc głos przeciw? To jest działająca implementacja.
earachefl
@Richard, ogólna strategia została opisana powyżej przez Whirlwind i innych. Nie widzę twojego komentarza do wszystkich innych odpowiedzi opublikowanych jako implementacje bez wyjaśnień.
ból uchafl
1

Wiem, że jest to bardzo stare i nawet nie na temat w dzisiejszym przepływie stosów, ale nadal chciałem wnieść przyjazną odpowiedź javascript z prostego powodu, że działa w Twojej przeglądarce.

Dodałem również debuggerpunkt przerwania dyrektywy, dzięki czemu można przejść przez kod (wymagany Chrome), aby zobaczyć, jak działa ten algorytm. Otwórz konsolę deweloperską w Chrome ( F12w systemie Windows lub CMD + OPTION + Ina Macu), a następnie kliknij „Uruchom fragment kodu”. Implementuje ten sam dokładny algorytm, który @WhirlWind przedstawił w swojej odpowiedzi.

Twoja przeglądarka powinna wstrzymać wykonywanie przy debuggerdyrektywie. Służy F8do kontynuowania wykonywania kodu.

Przejdź przez kod i zobacz, jak to działa!

function permute(rest, prefix = []) {
  if (rest.length === 0) {
    return [prefix];
  }
  return (rest
    .map((x, index) => {
      const oldRest = rest;
      const oldPrefix = prefix;
      // the `...` destructures the array into single values flattening it
      const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
      const newPrefix = [...prefix, x];
      debugger;

      const result = permute(newRest, newPrefix);
      return result;
    })
    // this step flattens the array of arrays returned by calling permute
    .reduce((flattened, arr) => [...flattened, ...arr], [])
  );
}
console.log(permute([1, 2, 3]));

Rico Kahler
źródło
1

W poniższym rozwiązaniu Java wykorzystujemy fakt, że ciągi znaków są niezmienne, aby uniknąć klonowania zestawu wyników przy każdej iteracji.

Dane wejściowe będą ciągiem znaków, powiedzmy „abc”, a danymi wyjściowymi będą wszystkie możliwe permutacje:

abc
acb
bac
bca
cba
cab

Kod:

public static void permute(String s) {
    permute(s, 0);
}

private static void permute(String str, int left){
    if(left == str.length()-1) {
        System.out.println(str);
    } else {
        for(int i = left; i < str.length(); i++) {
            String s = swap(str, left, i);
            permute(s, left+1);
        }
    }
}

private static String swap(String s, int left, int right) {
    if (left == right)
        return s;

    String result = s.substring(0, left);
    result += s.substring(right, right+1);
    result += s.substring(left+1, right);
    result += s.substring(left, left+1);
    result += s.substring(right+1);
    return result;
}

To samo podejście można zastosować do tablic (zamiast ciągu):

public static void main(String[] args) {
    int[] abc = {1,2,3};
    permute(abc, 0);
}
public static void permute(int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = index; i < arr.length; i++) {
            int[] permutation = arr.clone();
            permutation[index] = arr[i];
            permutation[i] = arr[index];
            permute(permutation, index + 1);
        }
    }
}
Nir Alfasi
źródło
1

To moje rozwiązanie w Javie:

public class CombinatorialUtils {

    public static void main(String[] args) {
        List<String> alphabet = new ArrayList<>();
        alphabet.add("1");
        alphabet.add("2");
        alphabet.add("3");
        alphabet.add("4");

        for (List<String> strings : permutations(alphabet)) {
            System.out.println(strings);
        }
        System.out.println("-----------");
        for (List<String> strings : combinations(alphabet)) {
            System.out.println(strings);
        }
    }

    public static List<List<String>> combinations(List<String> alphabet) {
        List<List<String>> permutations = permutations(alphabet);
        List<List<String>> combinations = new ArrayList<>(permutations);

        for (int i = alphabet.size(); i > 0; i--) {
            final int n = i;
            combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
        }
        return combinations;
    }

    public static <T> List<List<T>> permutations(List<T> alphabet) {
        ArrayList<List<T>> permutations = new ArrayList<>();
        if (alphabet.size() == 1) {
            permutations.add(alphabet);
            return permutations;
        } else {
            List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
            T addedElem = alphabet.get(0);
            for (int i = 0; i < alphabet.size(); i++) {
                for (List<T> permutation : subPerm) {
                    int index = i;
                    permutations.add(new ArrayList<T>(permutation) {{
                        add(index, addedElem);
                    }});
                }
            }
        }
        return permutations;
    }
}
user2153604
źródło
1

Nie można naprawdę mówić o rozwiązaniu problemu permultacji w rekurencji bez opublikowania implementacji w języku (dialekcie), który był pionierem tego pomysłu . Tak więc, aby uzyskać kompletność, oto jeden ze sposobów, które można wykonać w Scheme.

(define (permof wd)
  (cond ((null? wd) '())
        ((null? (cdr wd)) (list wd))
        (else
         (let splice ([l '()] [m (car wd)] [r (cdr wd)])
           (append
            (map (lambda (x) (cons m x)) (permof (append l r)))
            (if (null? r)
                '()
                (splice (cons m l) (car r) (cdr r))))))))

dzwoniąc (permof (list "foo" "bar" "baz"))otrzymamy:

'(("foo" "bar" "baz")
  ("foo" "baz" "bar")
  ("bar" "foo" "baz")
  ("bar" "baz" "foo")
  ("baz" "bar" "foo")
  ("baz" "foo" "bar"))

Nie będę wchodził w szczegóły algorytmu, ponieważ zostało to wystarczająco wyjaśnione w innych postach. Idea jest taka sama.

Jednak problemy rekurencyjne są znacznie trudniejsze do modelowania i myślenia w destrukcyjnych mediach, takich jak Python, C i Java, podczas gdy w Lisp lub ML można je zwięźle wyrazić.

Ciasto „Oh” Pah
źródło
0

Oto rozwiązanie rekurencyjne w PHP. Post WhirlWinda dokładnie opisuje logikę. Warto wspomnieć, że generowanie wszystkich permutacji przebiega w czasie silni, więc dobrym pomysłem może być użycie podejścia iteracyjnego.

public function permute($sofar, $input){
  for($i=0; $i < strlen($input); $i++){
    $diff = strDiff($input,$input[$i]);
    $next = $sofar.$input[$i]; //next contains a permutation, save it
    $this->permute($next, $diff);
  }
}

Funkcja strDiff pobiera dwa łańcuchy s1i s2, i zwraca nowy ciąg zawierający wszystko s1bez elementów w s2(powielona materia). A więc strDiff('finish','i')=> 'fnish'(drugie „i” nie jest usuwane).

Anthony Naddeo
źródło
0

Oto algorytm w R, na wypadek gdyby ktoś musiał unikać ładowania dodatkowych bibliotek, tak jak ja musiałem.

permutations <- function(n){
    if(n==1){
        return(matrix(1))
    } else {
        sp <- permutations(n-1)
        p <- nrow(sp)
        A <- matrix(nrow=n*p,ncol=n)
        for(i in 1:n){
            A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
        }
        return(A)
    }
}

Przykładowe użycie:

> matrix(letters[permutations(3)],ncol=3)
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 
Rozmyślny
źródło
0
#!/usr/bin/env python
import time

def permutations(sequence):
  # print sequence
  unit = [1, 2, 1, 2, 1]

  if len(sequence) >= 4:
    for i in range(4, (len(sequence) + 1)):
      unit = ((unit + [i - 1]) * i)[:-1]
      # print unit
    for j in unit:
      temp = sequence[j]
      sequence[j] = sequence[0]
      sequence[0] = temp
      yield sequence
  else:
    print 'You can use PEN and PAPER'


# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']

print s

z = permutations(s)
try:
  while True:
    # time.sleep(0.0001)
    print next(z)
except StopIteration:
    print 'Done'

['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']
mahmoh
źródło
Rozwiązanie pokazuje, że ciąg nie został permutowany zgodnie z wymaganiem. Druga permutacja powinna być PYTHNO
Rahul Kadukar
0

To jest kod rekurencyjny dla java, chodzi o to, aby mieć przedrostek dodający resztę znaków:

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

Przykład:

Input = "ABC"; Wynik:

ABC ACB BAC BCA CAB CBA

Rafael Amsili
źródło
1
Niezły pomysł, ale myślę, że powinieneś także usunąć charAt (i) z strwywołania rekurencyjnego, w przeciwnym razie nie zakończy się.
Crystal
1
Jeśli zamierzasz kopiować i wklejać, musisz (1) podać źródło i (2) upewnić się, że wszelkie zmiany są poprawne. Dla atrybucji jest to perm1 z introcs.cs.princeton.edu/java/23recursion/… . Również twoja edycja jest niepoprawna: str.substring (0, i) + str.substring (i + 1, n) to nie to samo co str, ponieważ ta pierwsza pomija znak na pozycji i.
kevin
0

Aby być kompletnym, C ++

#include <iostream>
#include <algorithm>
#include <string>

std::string theSeq = "abc";
do
{
  std::cout << theSeq << endl;
} 
while (std::next_permutation(theSeq.begin(), theSeq.end()));

...

abc
acb
bac
bca
cab
cba
AndersK
źródło
0

Oto nierekurencyjne rozwiązanie w C ++, które zapewnia następną permutację w porządku rosnącym, podobnie do funkcjonalności zapewnianej przez std :: next_permutation:

void permute_next(vector<int>& v)
{
  if (v.size() < 2)
    return;

  if (v.size() == 2)
  { 
    int tmp = v[0];
    v[0] = v[1];
    v[1] = tmp;
    return;
  }

  // Step 1: find first ascending-ordered pair from right to left
  int i = v.size()-2;
  while(i>=0)
  { 
    if (v[i] < v[i+1])
      break;
    i--;
  }
  if (i<0) // vector fully sorted in descending order (last permutation)
  {
    //resort in ascending order and return
    sort(v.begin(), v.end());
    return;
  }

  // Step 2: swap v[i] with next higher element of remaining elements
  int pos = i+1;
  int val = v[pos];
  for(int k=i+2; k<v.size(); k++)
    if(v[k] < val && v[k] > v[i])
    {
      pos = k;
      val = v[k];
    }
  v[pos] = v[i];
  v[i] = val;

  // Step 3: sort remaining elements from i+1 ... end
  sort(v.begin()+i+1, v.end());
}
Marios Choudary
źródło