[C++] Permutacje

theBRO
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 17 cze 2021, o 19:19
Płeć: Mężczyzna
wiek: 27
Pomógł: 1 raz

[C++] Permutacje

Post autor: theBRO »

Może ktoś mógłby pomóc z takim zadaniem:
Napisać program, który dla podanej liczby \(\displaystyle{ n}\) wypisuje na ekran wszystkie możliwe permutacje zbioru \(\displaystyle{ n}\)-elementowego, to znaczy zbioru liczb \(\displaystyle{ 1,2,..., n}\).
Ostatnio zmieniony 17 cze 2021, o 19:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
matmatmm
Użytkownik
Użytkownik
Posty: 2280
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Re: [C++] Permutacje

Post autor: matmatmm »

Każdą permutację zbioru \(\displaystyle{ n}\)-elementowego \(\displaystyle{ \{1,\ldots,n\}}\) można przedstawić jako złożenie \(\displaystyle{ \sigma\circ\tau}\), gdzie \(\displaystyle{ \sigma(n)=n}\), natomiast \(\displaystyle{ \tau}\) jest identycznością bądź transpozycją \(\displaystyle{ (n \phantom{0} i)}\) dla pewnego \(\displaystyle{ i\in\{1,\ldots,n-1\}}\).

\(\displaystyle{ \sigma}\) można utożsamić z permutacją zbioru \(\displaystyle{ (n-1)}\)-elementowego, a funkcji \(\displaystyle{ \tau}\) jest dokładnie \(\displaystyle{ n}\).
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Re: [C++] Permutacje

Post autor: Mariusz M »

Kiedyś pisałem taki programik jako część programiku do liczenia wyznacznika macierzy

Kod: Zaznacz cały

#include<stdio.h>
#include<stdlib.h>

void perm(int poz,int n,int* t,int* s)
{

    int i,j;
    int wystapil;

    FILE* fp;

    if((fp=fopen("permutations.txt","a"))==NULL)
    {
        printf("Nie mozna otworzyc pliku do dopisywania \n");
        exit(1);
    }

    if(poz>n)
    {
        for(i=1; i<=n; i++)
            fprintf(fp,"%d ",t[i]);
        fprintf(fp,"\n");
    }
    else
        for(j=1; j<=n; j++)
        {
            wystapil=0;
            for (i=1; i<=poz-1; i++)
                if(t[i]==s[j])
                    wystapil=1;
            if(!wystapil)
            {
                t[poz]=s[j];
                perm(poz+1,n,t,s);
            }
        }
    fclose(fp);
}

int main()
{
    int k,n;
    int *t;
    int *s;
    printf("Podaj n=");
    scanf("%d",&n);
    t = (int *)malloc((n+1)*sizeof(int));
    s = (int *)malloc((n+1)*sizeof(int));
    for(k = 1; k<=n; k++)
        s[k] = k;
    perm(1,n,t,s);
    return 0;
}

rivit
Użytkownik
Użytkownik
Posty: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: [C++] Permutacje

Post autor: rivit »

Można też tak:

Kod: Zaznacz cały

#include <algorithm>
#include <iostream>

std::ostream &operator<<(std::ostream &os, const std::vector<int> &vec) {
    for (int v : vec) {
        os << v << ", ";
    }
    return os;
}

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    do {
        std::cout << data << '\n';
    } while (std::next_permutation(data.begin(), data.end()));
}
Operator przeciążony tylko, żeby dało się wypisać vector za pomocą <<
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11200
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3136 razy
Pomógł: 744 razy

Re: [C++] Permutacje

Post autor: mol_ksiazkowy »

:arrow: Algorytm Steinhausa
utworzyć \(\displaystyle{ n}\) kopii dowolnej z permutacji \(\displaystyle{ n-1}\) elementów, a następnie element \(\displaystyle{ n}\) ty ustawić do każdej z tych kopii na wszystkie możliwe \(\displaystyle{ n}\) pozycje; np.

\(\displaystyle{ \left[\begin{array}{cccccc}1&2\\1&2\\1&2\\2&1\\2&1\\2&1\end{array}\right]}\)

\(\displaystyle{ \left[\begin{array}{cccccc}\color{red} {3} \color{red}
&1&2\\1& \color{red} {3} \color{red} &2\\1&2 & \color{red} {3} \color{red} \\ \color{red} {3} \color{red} & 2&1\\2& \color{red} {3} \color{red} &1\\2&1& \color{red} {3} \color{red} \end{array}\right]}\)

itd.
ODPOWIEDZ