Kombinacije

V

vlado_036

Početnik
Poruka
7
Potrebna mi je pomoc u resavanju sledeceg problema :

Imam niz od 20 elemenata "NizA" (broj elemenata zadaje korisnik),
NizA[0] = "A01";
NizA[1] = "A02";
------------------------
NizA[18] = "A19";
NizA[19] = "A20";
potrebna mi je funkcija koja ce da napravi novi niz "NizB" a koji treba da sadrzi sve kombinacije sa 8 elemenata od nizA (ovaj broj isto zadaje korisnik)
Npr. to treba da izgleda ovako :
NizB[0] = "A01A02A03A04A05A06A07A08";
NizB[1] = "A01A02A03A04A05A06A07A09";
NizB[2] = "A01A02A03A04A05A06A07A10";
--------------------------------------------------------------
NizB[125969] = "A13A14A15A16A17A18A19A20";
 
potreban ti je alogoritam za nalazenje varijacija.

var
duzina_drugog_niza : integer;

procedure varijacije(a : string; b : string);
var i : word ; c, d : string;

begin
if Length(a) = duzina_drugog_niza then writeln(a) else
for i := 1 to length(b) do begin
c := b;
d := a + c;
delete(c, i, 1);
varijacije(d, c)
end;
end;

funkciju zovi ovako:

varijacije ('', ulaz);

prvi parametar je prazan string
drugi je string od koga trazimo varijacije
duzina_drugog_niza je duzina dobijenih varijacija.

malo je moras preurediti za svoj problem ali ovako ces najlakse svatiti logiku.

ako ti treba u c++ javi.
 
Mislim da cu malo bolje da objasnim sta mi treba na primeru :
Uzecu manje brojeve za kombinovanje da bih mogao da napisem sve kombinacije.
Ukupno kombinacija 3 od 5 ima 10 i to su:

A01A02A03
A01A02A04
A01A02A05
A01A03A04
A01A03A05
A01A04A05
A02A03A04
A02A03A05
A02A04A05
A03A04A05

Ja mislim da su ovo kombinacije a ne varijacije, ako gresim ispravite me.
Sto se tice vremena koje je potrebno da se naprave sve kombinacije 10 od 20 (ima ih 184756) mislim da ne bi trebalo da bude vece od 10 minuta.
 
Evo ti jedan glup primer u javi koji radi samo ispis, a ti ga prepravi u sta ti vec treba i dodaj upis u rezultujuci niz:

Kod: 
public class Combinations {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Combinations!");
		long count = 0;
		for (int i1 = 0; i1 < 13; i1++) {
		  for (int i2 = i1+1; i2 < 14; i2++) {
		    for (int i3 = i2+1; i3 < 15; i3++) {
		      for (int i4 = i3+1; i4 < 16; i4++) {
			for (int i5 = i4+1; i5 < 17; i5++) {
			  for (int i6 = i5+1; i6 < 18; i6++) {
			    for (int i7 = i6+1; i7 < 19; i7++) {
			      for (int i8 = i7+1; i8 < 20; i8++) {
				System.out.println(" A"+i1+" A"+i2+" A"+i3+" A"+i4+" A"+i5+" A"+i6+" A"+i7+" A"+i8);
				count++;
			      }
			    }
			  }
			}
		      }
		    }
		  }
		}
		System.out.println("count :"+count);
	}

}
Ima 125970 kombinacija, kao sto si ocekivao.
 
Garw, kod je OK što i sam znaš.

Za one koji ne znaju, broj kombinacija n brojeva iz grupe od m brojeva računa se kao m nad n što se opet izračunava kao m!/(n!*(m-n)!) što za sistem 8 elemenata iz grupe od 20 daje 20!/8!*12! = 125970.
 
Grawor kod je OK, radi bas onako onako kako mi treba. Hvala.

Imao bih jos jedno pitanje na ovu temu.

Postoji li mogucnost da se ovaj kod prepravi da radi sa zadatim brojevima za kombinovanje, recimo da zadam da mi napravi sve kombinacija 6 od 18 ili 10 od 20 ili bilo koju drugu kombinaciju, da nebih morao svaki put da prepravljam kod?
 
Naravno da se može. U programiranju se može skoro sve. Ali, potrudi se malo, nemoj da ti sav kod pišu drugi. Ovo nije čak ni mnogo teško prepraviti.
(Naravno, u nekim razumnim granicama, i računar ima svoja fizička ograničenja, a i C++ svoja).
 
Garwor:
Evo ti jedan glup primer u javi koji radi samo ispis, a ti ga prepravi u sta ti vec treba i dodaj upis u rezultujuci niz:

Kod: 
public class Combinations {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Combinations!");
		long count = 0;
		for (int i1 = 0; i1 < 13; i1++) {
		  for (int i2 = i1+1; i2 < 14; i2++) {
		    for (int i3 = i2+1; i3 < 15; i3++) {
		      for (int i4 = i3+1; i4 < 16; i4++) {
			for (int i5 = i4+1; i5 < 17; i5++) {
			  for (int i6 = i5+1; i6 < 18; i6++) {
			    for (int i7 = i6+1; i7 < 19; i7++) {
			      for (int i8 = i7+1; i8 < 20; i8++) {
				System.out.println(" A"+i1+" A"+i2+" A"+i3+" A"+i4+" A"+i5+" A"+i6+" A"+i7+" A"+i8);
				count++;
			      }
			    }
			  }
			}
		      }
		    }
		  }
		}
		System.out.println("count :"+count);
	}

}
Ima 125970 kombinacija, kao sto si ocekivao.
Kliknite za proširenje...


Ala glupog resenja znasli koja je slozenost tvog alogoritma? N na 8
 
vlado_036:
Grawor kod je OK, radi bas onako onako kako mi treba. Hvala.

Imao bih jos jedno pitanje na ovu temu.

Postoji li mogucnost da se ovaj kod prepravi da radi sa zadatim brojevima za kombinovanje, recimo da zadam da mi napravi sve kombinacija 6 od 18 ili 10 od 20 ili bilo koju drugu kombinaciju, da nebih morao svaki put da prepravljam kod?
Kliknite za proširenje...


Nema sanse pogotova ovaj njegocv alogoritam. Za ovo se mora malo koristiti dinamickim programiranjem da bi se zadatak ubrzo ali za 6 od 18 nema sanse
 
Garwor:
Bravo majstore, zapanjen sam tvojim analitickim sposobnostima, stavise upravo si ispunio sve uslove za project managera: nista ne radis, samo ides okolo i smaras glupim konstatacijama.
Kliknite za proširenje...

Nebudali neko iznese za sto pravi program pa cu pomoci, a ne ovako trebamu kombinacije. Neka iznese kakav program radi pa se onda program moze ubrzati ali ovako nista. Ako njemu moze da program radi obradu duze dobro ali nito nece moci dobice gresku Stack Overflow
 
Nemanja666:
Nebudali neko iznese za sto pravi program pa cu pomoci, a ne ovako trebamu kombinacije. Neka iznese kakav program radi pa se onda program moze ubrzati ali ovako nista. Ako njemu moze da program radi obradu duze dobro ali nito nece moci dobice gresku Stack Overflow
Kliknite za proširenje...
Kad već tako dobro analiziraš programe, hajde ovdje iznesi svoju procjenu koliko bi trebao da bude dubok stack da se izvrši Garwov kod. Ali pazi, ne radi se o rekurzivnom pozivanju nego o ugnježdenim for petljama.
Evo ti moja procjena: dovoljan je sistemski stack za slučaj da program bude prekinut (a hoće biti od strane sistema). Tada će biti na stek smješteni deskriptori prekinutog programa i stanja registara. I to je sve. Sam kod zahtijeva dubinu stack-a 0, jer ga i ne koristi.

(DXXIII)
 
Nemanja666:
Nebudali neko iznese za sto pravi program pa cu pomoci, a ne ovako trebamu kombinacije. Neka iznese kakav program radi pa se onda program moze ubrzati ali ovako nista. Ako njemu moze da program radi obradu duze dobro ali nito nece moci dobice gresku Stack Overflow
Kliknite za proširenje...

Bas kao sto rekoh, neka neko uradi, a ti ces onda da pomognes. ;)

Vlada je dao zanimljiv zadatak, resavaj.
 
Prijavite se ili registrujte da biste poslali poruku.

Back
Top