Strona 1 z 1
[C++] Permutacje
: 17 cze 2021, o 19:22
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}\).
Re: [C++] Permutacje
: 18 cze 2021, o 11:09
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}\).
Re: [C++] Permutacje
: 2 lip 2021, o 19:47
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;
}
Re: [C++] Permutacje
: 10 lip 2021, o 09:25
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ą <<
Re: [C++] Permutacje
: 20 sie 2021, o 10:44
autor: mol_ksiazkowy
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.