Matematické Fórum

yellowzelo · 15. 11. 2009 05:00

Čaute,
potrebujem vytvoriť program, ktorý nájde všetky permutácie s niektorými opakovanými prvkami.
pre lepšie pochopenie hodím príklad:

ak by bol vstup programu boli prvky: 0, 0, 1, 1, 1
výstup by mal byť:

Code:

Jediné, čo zatiaľ viem je, že počet týcho permutácii je možné vypočítať podľa vzorca: $\frac{(n_1+n_2+...)!}{n_1! n_2! ...)}$
Teda pre uvedený príklad by to bolo: $\frac{(2+3)!}{2! 3!}=10$

Neviete ako by sa to dalo spraviť?
Díki.

Kondr · 15. 11. 2009 10:32

Chceme k jedniček a n-k nul. Na začátku umístíme jedničky na pozice 1,2,...,k. V každém kroku posuneme poslední jedničku doprava. Když dojede na konec, posuneme doprava předposlední a tu poslední dáme těsně za posunutou předposlední. Když dojedou na konec dvě, posuneme předpředposlední a dvě poslední zarovnáme těsně za ni, atd.

Stačí takto? Mám k tomu někde i C++ kód, co jsem psal za domácí úkol.

yellowzelo · 15. 11. 2009 22:58

↑ Kondr:

Díki, za odpoveď.

Už tomu oveľa lepšie rozumiem. Mohol by si sem predsa len hodiť ten algoritmus, ak ho máš niekde po ruke?
(Môj program mi vyhadzuje nie vždy správne hodnoty.)

Ďakujem.

Kondr · 15. 11. 2009 23:17

Code:

while(!done){
        for(int i=0;i<57;i++)key[i]=0;
        for(int i=0;i<6;i++)key[ones[i]]=1;

//zde se neco dela s polem key, ve tvem pripade vypis
         
        ones[5]++;
        int c;
        for(c=5;ones[c]==57+c-5;c--){
            if(c==0){
                        done=true;
            }
            else ones[c-1]++;
        }
        for(int i=c+1;i<6;i++)ones[i]=ones[c]+i-c;
    }

Je to součást programu na prolamování šifrované komunikace mezi počítačem a kreditkou. Šifrovací věci jsem z toho vyházel, snad jsem tím nenarušil funkcionalitu. V programu bylo napevno zvoleno, že rozdělujeme 6 jedniček na 57 pozic.

Matematické Fórum

#1 15. 11. 2009 05:00

permutácie s niektorými opakovanými prvkami

Code:

#2 15. 11. 2009 10:32

Re: permutácie s niektorými opakovanými prvkami

#3 15. 11. 2009 22:58

Re: permutácie s niektorými opakovanými prvkami

#4 15. 11. 2009 23:17

Re: permutácie s niektorými opakovanými prvkami

Code:

Zápatí