Šta su varijacije?

• Varijacije k-te klase( bez ponavljanja ) skupa A od n elementa je svaka uredjena k-torka različitih elemenata tog skupa.
• Broj varijacija bez ponavljanja k-te klase je n(n-1)(n-1)…(n-k+1).

Za zadati prirodan broj n treba generisati sve varijacije k-te klase skupa A={1,2,..n}. Na primer za n=4 i k=3 program bi trebalo da izgeneriše sledeci varijacije :

1 2 3
1 2 4
1 3 4
1 3 4
2 1 3
…
Biće ih ukupno 24 (4*3*2=24).

Ove je prikazano rešenje koje koristi rekurziju:

#include <stdio.h>
#include <stdlib.h>
 
void varijacije(int n,int k,int pozicija, int niz[],int ubacen[])
		{
			int i;
 
		if (pozicija > k)
			{
				for (i=1;i<k+1;i++)
				printf("%d ",niz[i]);
				printf("\n");
			}
		else
			{
				for (i=1;i<n+1;i++)
					{
						if (ubacen[i]==0)
							{
								niz[pozicija]=i;
								ubacen[i]=1;
								varijacije(n,k,pozicija+1,niz,ubacen);
								ubacen[i]=0;
							}
					}
			}
 
			}
 
main()
{
int *niz,*ubacen;
int n,k;
printf("Unesite broj elemenata skupa i klasu\n");
printf("n:");
scanf("%d",&n);
printf("k:");
scanf("%d",&k);
niz=(int *)malloc((k+1)*sizeof(int));
ubacen=(int*)calloc(n+1,sizeof(int));
varijacije(n,k,1,niz,ubacen);
}

Promenljive:
niz : niz u koji se smešta izgenerisana varijacija. On ima k+1 elemenata zbog indeksiranja u C-u koja kreću od 0
ubacen: niz integer-a koji ima n elemenata.Na početku su svi njegovi elementi inicijalizovani sa 0 ¹⁾. Niz je uveden da označi da li je neki element uključen u tekuću varijaciju ili ne (0- nije, 1- uključen je).
n : broj elemenata skupa A čije varijacije k-te klase generišemo
k : klasa
pozicija : pozicija za koju trenutno tražimo element. Pošto su varijacije k-te klase, ona može biti najviše k.
Neka je n=4 a k=3;
Pri prvom pozivu f-je varijacije() u niz se na 1. poziciju stavlja 1, i ubacen[1]=1, dakle označavamo da je 1 već ušlo u tekuću varijaciju (posto su varijacije bez ponavljanja jedan element može najviše jednom da se pojavi). U ovom trenutku niz je {0,1,0,0}²⁾. Zatim se vrši rekurzivan poziv f-je varijacije() (prethodna f-ja neće moći da pređe na sledeću instrukciju (ubacen[i]=0),sve dok se ne do kraja ne izvrši rekurzivno pozvana f-ja) sa izmenjenim parametrom pozicija= pozicija +1 tj. za poziciju 2 jer smo naši odgovarajuću vrednost za pozicija=1. Ova f-ja prihvata izmenjene podatke i u nizovima niz i ubacen ³⁾.Zbog toga ona u okviru for petlje prvi put nailazi na ubacen=0 za i=2. Ubacuje 2 u niz, ponovo poziva varijacije() sa promenjenim parametrima. Ova f-ja sad prvi put nailazi da je ubacen[i]=0 za i=3,i ubacuje 3 u niz. Sada i ona rekurzivno poziva f-ju varijacije() za vrednost pozicija=4. Pri izvršavanju ove f-je biće ispunjen uslov da je pozicija > 3, stampaće se
1 2 3
i ova f-ja završava sa radom. Sada se redom završavaju f-je : najpre f-ja koja je u niz ubacila 3, vraća ubacen[3]=0,vraća se u for-petlju, povećava i na 4 i ponovo poziva varijacije() za poziciju 4 koja kao rezultat daje
1 2 4
…

Program vrši generisanje samo varijacija skupa oblika A={1,2,…n}. Poboljšana verzija bi bila da radi sa bilo kojim skupom (slova, znakovi, višecifreni brojevi…). To može da se reši tako da se svakom elementu pridruži indeks koji odgovara poziciji tog elementa u polaznom skupu. Štampaju se umesto niz[i] ,polazni_niz[niz[i]].