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}\).
[C++] Permutacje
[C++] Permutacje
Ostatnio zmieniony 17 cze 2021, o 19:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 2282
- Rejestracja: 14 cze 2011, o 11:34
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 88 razy
- Pomógł: 351 razy
Re: [C++] Permutacje
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}\).
\(\displaystyle{ \sigma}\) można utożsamić z permutacją zbioru \(\displaystyle{ (n-1)}\)-elementowego, a funkcji \(\displaystyle{ \tau}\) jest dokładnie \(\displaystyle{ n}\).
- Mariusz M
- Użytkownik
- Posty: 6908
- 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
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;
}
-
- 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
Można też tak:
Operator przeciążony tylko, żeby dało się wypisać vector za pomocą <<
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()));
}
- mol_ksiazkowy
- Użytkownik
- Posty: 11361
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: [C++] Permutacje
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.
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.