Voozh

Z Wikipedie, otevřené encyklopedie

Variace k-té třídy z n prvků je každá uspořádaná k-tice vytvořená z celkového počtu n prvků, přičemž "uspořádaná" zde znamená, že při výběru záleží na pořadí jednotlivých prvků. Rozlišujeme variace s opakováním a bez opakování. Pro výpočet hodnoty je používán faktoriál.

Kombinace se od variací odlišují tím, že u nich na pořadí nezáleží.

Permutace je v podstatě zvláštní příklad variace, kdy n=k, tj. máme množinu prvků a určujeme možný počet jejich pořadí.

Variace bez opakování

[editovat | editovat zdroj]

Variace bez opakování je k-členná skupina utvořená z daných n prvků tak, že v nich záleží na pořadí a žádný z daných prvků se v ní neopakuje.

Počet k-členných variací z n prvků: 👁 {\displaystyle V(k,n)=n(n-1)(n-2)...(n-k+1)={\frac {n!}{(n-k)!}}}
pro 👁 {\displaystyle k\leq n}

Příklad: dvoučlenné variace ze 3 prvků a, b, c jsou: (ab), (ba), (ac), (ca), (bc), (cb) 👁 {\displaystyle ={\frac {3!}{(3-2)!}}=6}

Variace s opakováním

[editovat | editovat zdroj]

Variace s opakováním je uspořádaná k-tice z n prvků sestavená tak, že každý se v ní vyskytuje nejvýše k-krát. Opět záleží na pořadí.

Počet k-členných variací s opakováním z n prvků: 👁 {\displaystyle V'(k,n)=n^{k}}
platí i pro 👁 {\displaystyle k<n}

Tedy například: dvoučlenná variace s opakováním ze 3 prvků a, b, c: (aa), (ab), (ac), (ba), (bb), (bc), (ca), (cb), (cc) 👁 {\displaystyle =3^{2}=9}

Příklady

[editovat | editovat zdroj]

Příklad 1

[editovat | editovat zdroj]

Kolik trojciferných čísel je možné sestavit z číslic 1, 2, 3, 4, jestliže:

a) se v čísle každá cifra může vyskytovat nejvýše jednou

👁 {\displaystyle V(3,4)={\frac {4!}{(4-3)!}}={\frac {4!}{1!}}=4\cdot 3\cdot 2=24}

b) se v čísle cifry můžou opakovat

👁 {\displaystyle V'(3,4)=4^{3}=64}

Příklad 2

[editovat | editovat zdroj]

Kolik je možností pro obsazení 1., 2. a 3. místa v závodě s 20 účastníky?

👁 {\displaystyle V(3,20)={\frac {20!}{(20-3)!}}={\frac {20!}{17!}}={\frac {20\cdot 19\cdot 18\cdot 17!}{17!}}=20\cdot 19\cdot 18=6840}

Příklad 3

[editovat | editovat zdroj]

Posádka lodi potřebuje k dorozumívání vytvořit 50 různých signálů. Budou jim k tomu stačit 4 různobarevné praporky?

jednopraporkové signály: 👁 {\displaystyle V(1,4)=4}
dvoupraporkové signály: 👁 {\displaystyle V(2,4)={\frac {4!}{2!}}=4\cdot 3=12}
třípraporkové signály: 👁 {\displaystyle V(3,4)={\frac {4!}{1!}}=4!=4\cdot 3\cdot 2=24}
čtyřpraporkové signály: 👁 {\displaystyle V(4,4)=P(4)=4!=24}

Celkem lze vytvořit: 👁 {\displaystyle 4+12+24+24=64}
signálů. Na vytvoření 50 signálů budou tedy 4 různobarevné praporky stačit.

Příklad 4

[editovat | editovat zdroj]

Kolika způsoby můžete nastavit šestimístný číselný kód na zámku u trezoru?

👁 {\displaystyle V'(6,10)=10^{6}=1000000}

Šestimístný zámek trezoru umožňuje 1 milion různých kódů.

Příklad 5

[editovat | editovat zdroj]

Heslo je složené z písmen anglické abecedy (26 písmen) a je dlouhé 8 znaků. Je pro zvýšení bezpečnosti (zvýšení síly hesla) lepší zachovat jeho délku a použít i čísla nebo jen prodloužit heslo?

👁 {\displaystyle V'(8,26)=26^{8}=2\cdot 10^{11}}

👁 {\displaystyle V'(8,36)=36^{8}=2{,}8\cdot 10^{12}}

👁 {\displaystyle V'(9,26)=26^{9}=5{,}4\cdot 10^{12}}

Pro zvýšení bezpečnosti hesla je lepší ho prodloužit už jen o jeden znak, protože počet možných variant hesla je vyšší (👁 {\displaystyle 5{,}4\cdot 10^{12}}
) než při zachování délky a použití písmen a čísel (👁 {\displaystyle 2{,}8\cdot 10^{12}}
). Důvodem je, že exponenciální funkce zvyšuje svůj růst rychleji se změnou exponentu než základu mocniny.

Algoritmus

[editovat | editovat zdroj]

Algoritmus pro nalezení všech variací znaků (s opakováním, v jazyku Java)

publicstaticList<String>variaceSOpakovanim(inttrida,StringpouzitelneZnaky){
List<String>list=newArrayList<String>((int)Math.pow(pouzitelneZnaky.length(),trida)/*(1)*/);

if(trida==0){
list.add("");/*(2)*/
}else{
List<String>l=variaceSOpakovanim(trida-1,pouzitelneZnaky);
for(charc:pouzitelneZnaky.toCharArray()){/*(3)*/
for(Strings:l){
list.add(c+s);/*(4)*/
}
}
}
returnlist;
}

Počet variací s opakováním je dán jako počet použitelných prvků umocněný na třídu variace.
Variace nulté třídy je právě jedna: prázdná množina.
Variace s opakováním se dá vnímat jako kartézský součin množiny použitelných prvků s množinou variací ze stejných použitelných prvků, ale s třídou o jednu menší. Z toho vyplývá použití rekurze.
Přidá do výstupního (vraceného) seznamu příslušný prvek, vzniklý spojením jednoho (každého) prvku s jednou (každou) variací nižší třídy.