Permutacje - zastosowanie instrukcji swap

Question

Proszę o pomoc w napisaniu procedury, która wyświetli wszystkie permutacje dla zadanego ciągu znaków. Znaki mam zapisane w tablicy tab [i]. Początkowo próbowałem kod napisać samodzielnie, lecz zupełnie bezskutecznie, następnie odszukałem przykłady w sieci, ale nie rozumiem ich działania i także nie potrafię ich zastosować. Prawdopodobnie to zadanie jest zbyt trudne dla mnie, ale właśnie w taki sposób chciałbym się rozwijać. Będę wdzięczny za wskazówki, które pozwoliłyby mi samodzielnie rozwiązać ten problem lub ostatecznie zaadoptować inne rozwiązanie.

Comments

Spróbuj sobie rozpisać na kartce jak tworzone są kolejne permutacje.

Kiedyś tak zrobiłem i doszedłem do wniosku, że grubsza zasada jest taka że trzeba zrobić rekurencje w taki sposób:

1) Iterujesz się (i) od id do n elementów

2) W każdym obiegu pętli zamieniasz miejscami obecne id (argument funkcji) z i.

3) Odpalasz rekurencyjnie podając id+1

4) Cofasz swap

2b) W przypadku jeżeli id ustawione na ostatni element to trzeba wypisać tą kombinacje, bo już nic więcej się nie przestawi.

 

Nie wiem czy jest to kolejność leksykograficzna, jeżeli nie to zawsze możesz posortować.

Answer 1

Witam,

możesz troszkę zedytować ten program aby pasował do Twoich wymagań ale myślę że sprawdzi się do tego zadania.

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

Tutaj masz więcej informacji na temat tego algorytmu i powyższego programu :

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Comments

Dziękuję bardzo - algorytm znacznie mi pomógł. Generalnie w C++ próbuję rozwiązać zadanie z platformy SPOJ o nazwie: "Permutacje" - ID:495 z utrudnieniem takim, iż chciałbym aby rozwiązanie wyglądało dokładnie tak jak w podanym przykładzie, czyli najpierw wczytywanie danych, a dopiero po ich wczytaniu wypisanie permutacji dla każdego testu. Zadeklarowałem dynamicznie tablice dwuwymiarowe, jednak samo generowanie permutacji nie działa prawidłowo - program "wplata" dodatkowy znak będący znakiem z tablicy ASCII o numerze równym ilości znaków i znaku tego używa do generowania permutacji. Nie potrafię poprawić tego błędu, chociaż intuicyjnie wydaje mi się, że błąd tkwi w podaniu pierwszego argumentu w procedurze "permute".

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
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));
       }
   }
}
int main()
{
    int ile_prob, ile_liter;
    char **tab;
    cin>>ile_prob;
    tab=new char *[ile_prob];

    for (int i=0; i<ile_prob; i++)
    {
        cin>>ile_liter;
        tab[i]=new char[ile_liter+1];
        for(int j=0; j<ile_liter; j++)
        {
            tab[i][j]=j+97;
            tab[i][ile_liter]=ile_liter;
        }
    }
    for (int i=0; i<ile_prob; i++)
    {
        for(int j=0; j<ile_liter; j++)
        {
            cout<<(int)tab[i][ile_liter];
            permute(tab[i], 0, (int)tab[i][ile_liter]);
        }
    }
return 0;
}