[C++] Permutacje

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

[C++] Permutacje

Post autor: theBRO » 17 cze 2021, o 19:22

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

matmatmm
Użytkownik
Użytkownik
Posty: 2074
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 78 razy
Pomógł: 310 razy

Re: [C++] Permutacje

Post autor: matmatmm » 18 cze 2021, o 11:09

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
mariuszm
Użytkownik
Użytkownik
Posty: 6772
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1224 razy

Re: [C++] Permutacje

Post autor: mariuszm » 2 lip 2021, o 19:47

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: 164
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 » 10 lip 2021, o 09:25

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ą <<

ODPOWIEDZ