Permutacie – C / C++ – Fórum – Programujte.com

Rad by som vypisal permutacie prvkov.
no ako som tak rozmyslal, nie je to jednoduche :)
napr (1,2,3):
123
132
213
231
321
312
-----------------
ale co tak (1,2,3,4,5,6,7,8,9)
nema niekto napad ako to tam zautomatizovat ?

Jasn? ?e m? - koukej, m?? funkci, kter? p?ejme jako argument index prvku (bude to nejv?t?? z ??sel, neboli po?et cifer), pole prvk? v int (samot?ejm? ukazatelem, bude nastaveno na 0) a velikost nejvy???ho prvku (na za??tku stejn? ??slo jako po?et cifer).
Tahle fukce (v cyklu, je? je pom?n?n t?m, aby velikost prvku byla v?c ne? 0 a velikost counteru je? to bude po??tat byl men?? nebo roven velikosti nejvy???ho prvku):
1) zv?t?? prvek podle indexu o jedna,
2) vytiskne ??slo z pole (samoz?ejm? kv?li indexov?n? je t?eba tisknout pozp?tku)
3) a zavol? sama sebe s indexem o jedna men??m.
4) zvedne counter o 1

Vlastně to co jsi uvedl je jednou ze základních ukázek rekurze.

Nejako som sa v tom stratil. Mozes uviest tu funkciu ? :)

No nerad bych, jelikož nemám po ruce kompilátor, takže bych v tom klidně moh napsat chybu a nemuselo by to fungovat, ale....
Ale zkusim to:
void permutace(int * PointArr, int cifry, int prvek) {
int counter = cifry;
while (counter <= cifry) {
PointArr[prvek]++;
cout << PointArr; //Bude to teda tisknout pozpátku, pak
//se to dá upravit.
if (prvek >= 0)
permutace(PointArr, cifry, --prvek);
counter++
}
prvek++;
}

tak toto mi hlava neberie :-(
ako fakt nechapem postup
----
to PointArr v priklade reprezentuje to 1,2,3
cifry to je pocet prvkov, teda 3
prvok to by mal byt podla nasledneho dekrementu posledny prvok 3
----
oprav ma, ked som nieco zle pochopil.
---
je tu niekto iny co to chape ? :D

Ja jen dodam, ze staci pouzit i funkci vytvorenou pro tento ucel a tou je next_permutation z STL. Ale na druhou stranu nen nad to zjistit, jak to vlastne funguje. Je to priklad vytahnuty z msdn.

//////////////////////////////////////////////////////////////////////[color=black]

[/color]//[color=black]

[/color]// Compile options needed: /GX[color=black]

[/color]//[color=black]

[/color]// next_permutation.cpp : Illustrates how to use the[color=black]

[/color]//                        next_permutation function.[color=black]

[/color]//[color=black]

[/color]// Functions:[color=black]

[/color]//[color=black]

[/color]//    next_permutation : Change the order of the sequence to the[color=black]

[/color]//                       next lexicograhic permutation.[color=black]

[/color]//////////////////////////////////////////////////////////////////////[color=black]

[/color][color=black]

[/color]// disable warning C4786: symbol greater than 255 character,[color=black]

[/color]// okay to ignore[color=black]

[/color][color=black]

[/color][color=black]

[/color][color=blue]#include[/color] [color=black]<[/color][color=black]iostream[/color][color=black]>[/color][color=black]

[/color][color=blue]#include[/color] [color=black]<[/color][color=black]vector[/color][color=black]>[/color][color=black]

[/color][color=blue]#include[/color] [color=black]<[/color][color=black]string[/color][color=black]>[/color][color=black]

[/color][color=blue]#include[/color] [color=black]<[/color][color=black]algorithm[/color][color=black]>[/color][color=black]

[/color][color=blue]#include[/color] [color=black]<[/color][color=black]iterator[/color][color=black]>[/color][color=black]

[/color][color=black]

[/color][color=blue]using[/color] [color=blue]namespace[/color] [color=black]std[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color][color=blue]int[/color] [color=black]main[/color][color=black]([/color][color=black])[/color][color=black]

[/color][color=black]{[/color][color=black]

[/color]    [color=blue]const[/color] [color=blue]int[/color] [color=black]VECTOR[/color][color=black]_[/color][color=black]SIZE[/color] [color=black]=[/color] [color=red]3[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    // Define a template class vector of strings[color=black]

[/color]    [color=blue]typedef[/color] [color=black]vector[/color][color=black]<[/color][color=black]string[/color][color=black]>[/color] [color=black]StrVector[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    //Define an iterator for template class vector of strings[color=black]

[/color]    [color=blue]typedef[/color] [color=black]StrVector[/color][color=black]:[/color][color=black]:[/color][color=black]iterator[/color] [color=black]StrVectorIt[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    //Define an ostream iterator for strings[color=black]

[/color]    [color=blue]typedef[/color] [color=black]ostream[/color][color=black]_[/color][color=black]iterator[/color][color=black]<[/color][color=black]string[/color][color=black]>[/color] [color=black]StrOstreamIt[/color][color=black];[/color][color=black]

[/color][color=black]

[/color]    [color=black]StrVector[/color] [color=black]Pattern[/color][color=black]([/color][color=black]VECTOR[/color][color=black]_[/color][color=black]SIZE[/color][color=black])[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    [color=black]StrVectorIt[/color] [color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black],[/color] [color=black]it[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    [color=black]StrOstreamIt[/color] [color=black]outIt[/color][color=black]([/color][color=black]cout[/color][color=black],[/color] [color=green]" "[/color][color=black])[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    [color=black]start[/color] [color=black]=[/color] [color=black]Pattern[/color][color=black].[/color][color=black]begin[/color][color=black]([/color][color=black])[/color] [color=black];[/color]   // location of first[color=black]

[/color]                                      // element of Pattern[color=black]

[/color][color=black]

[/color]    [color=black]end[/color] [color=black]=[/color] [color=black]Pattern[/color][color=black].[/color][color=black]end[/color][color=black]([/color][color=black])[/color] [color=black];[/color]       // one past the location last[color=black]

[/color]                                       // element of Pattern[color=black]

[/color][color=black]

[/color]    //Initialize vector Pattern[color=black]

[/color]    [color=black]Pattern[/color][color=black][[/color][color=red]0[/color][color=black]][/color] [color=black]=[/color] [color=green]"A"[/color] [color=black];[/color][color=black]

[/color]    [color=black]Pattern[/color][color=black][[/color][color=red]1[/color][color=black]][/color] [color=black]=[/color] [color=green]"B"[/color] [color=black];[/color][color=black]

[/color]    [color=black]Pattern[/color][color=black][[/color][color=red]2[/color][color=black]][/color] [color=black]=[/color] [color=green]"C"[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    // print content of Pattern[color=black]

[/color]    [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"Before calling next_permutation...\n"[/color] [color=black]<[/color][color=black]<[/color] [color=green]"Pattern: "[/color] [color=black];[/color][color=black]

[/color]    [color=blue]for[/color][color=black]([/color][color=black]it[/color] [color=black]=[/color] [color=black]start[/color][color=black];[/color] [color=black]it[/color] [color=black]![/color][color=black]=[/color] [color=black]end[/color][color=black];[/color] [color=black]it[/color][color=black]+[/color][color=black]+[/color][color=black])[/color][color=black]

[/color]        [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=black]*[/color][color=black]it[/color] [color=black]<[/color][color=black]<[/color] [color=green]" "[/color] [color=black];[/color][color=black]

[/color]    [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"\n\n"[/color] [color=black];[/color][color=black]

[/color][color=black]

[/color]    // Generate all possible permutations[color=black]

[/color][color=black]

[/color]    [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"After calling next_permutation...."[/color] [color=black]<[/color][color=black]<[/color] [color=black]endl[/color] [color=black];[/color][color=black]

[/color]    [color=blue]while[/color] [color=black]([/color] [color=black]next[/color][color=black]_[/color][color=black]permutation[/color][color=black]([/color][color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black])[/color] [color=black])[/color][color=black]

[/color]    [color=black]{[/color][color=black]

[/color]        [color=black]copy[/color][color=black]([/color][color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black],[/color] [color=black]outIt[/color][color=black])[/color] [color=black];[/color][color=black]

[/color]        [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=black]endl[/color] [color=black];[/color][color=black]

[/color]    [color=black]}[/color][color=black]

[/color]    [color=black]cin[/color][color=black].[/color][color=black]get[/color][color=black]([/color][color=black])[/color][color=black];[/color][color=black]

[/color]    [color=blue]return[/color] [color=red]0[/color][color=black];[/color][color=black]

[/color][color=black]}[/color][color=black]

[/color][color=black]

[/color]

Nech?pe?? Tak principi?ln?, co to d?l? -
vyvol?? t?eba fci pro ?ty?i cifry - tzn. pro ??sla 1-4. Co se stane?
Vytvo?? se pole ?ty? prvk? na hodnot? nula a p?ed? se fci, n?sledn? se s n?m pracuje jen pomoc? ukazatele PointArr (Array, Pointer - ?ili pole, ukazatel). Prob?hne prvn? fce:
Zvedne posledn? prvek (s indexem (prvkem) 3, tam m?m chybku, mus?? dotat index o jedno men?? ne? je po?et cifer samoz?ejm?)
m?? 0001.
Zavol? se druh? fce uvnit? cyklu prvn?, index 2 se zvedne o jedna vznikne 0011.
Zavol? se t?et? fce uvnit? cyklu druh?, index 1 se zvedne o jedna vznikne 0111.
Zavol? se ?tvrt? fce uvnit? cyklu t?et?, index 0 se zvedne o jedna vznikne 1111, podn?mka nepravdiv?, dal?? fce se nezavol?, prob?h? cyklus:
2111
3111
4111
podm?nka nepravdiv?, cyklus kon??, kon?? ?tvrt? fce.
T?et? fce prob?hne cyklus zvedne na 1211 (to by se m?lo st?t, j? tam m?m chybu, tak?e tam bude 4211, proto?e jsem zapom?l na konci fce zm?nit prvek zp?t na 1)
po zvednut? prvku o jedna se zavol? zase ?tvrt? fce a zase
2211
3211............
a? skon?? t?et? funkce, tak druh? ikrementuje a zavol? t?et?, kter? inkrementuje a zavol? ?tvrtou, pak skon?? i druh? a prvn? ji zavol? znovu a ta zavol? t?et? a... a takhle to bude a? do ??sla 4444...

Jinak m?m tam chybky, tak?e by to nefungovalo, cht?l jsem jen vysv?tlit princip, a? budu m?t kompil?tor, mo?n? vytvo??m funk?n? verzi

ach jo. trochu svetla :)
takze ked to chapem dostanem
1111 2111 3111 4111
1211 2211 3211 4211
1311 2311 3311 4311
1411 2411 3411 4411
1121 ...
----------
tieto polia budem dostavat po volani ?
(teraz neviem ci som to pochopil)
ale ked hej tak toto nie su "permutacie"
ja chcem dostat
1234 2134 ...
1243 2143
1324 2314
1342 2341
1432 2413
1423 2431

Sorry, pochopil jsi správně, já nevěděl přesně, co jsou to permutace :((. Až budu mít trochu času, tak nad tím popřemýšlím.

Jinak už ti zase blbne zvýrazňování syntaxe - závorky

I'm GOD, workship me!!!

#include <iostream>

using namespace std;



void permutace(int * pointer, int size);

void swap(int & a, int & b);

void print(int * pointer, int size);

int faktorial(int cislo, int citac);

int zjisti_a(int counter);

int zjisti_b(int counter);



int main() {

   cout << "Zadejte pocet prvku (cifer): n";

   int size;

   cin >> size;

   int array[size]; // Pole pro ulo?en? ??sla

   for (int counter = 1; counter <= size; counter++)

      array[counter - 1] = counter;  // Na?ten? pole po sob? jdouc?mi ??sly

   permutace(array, size);

   cin.get();

   cin.get();

}



void permutace(int * pointer, int size) {

   int counter = 1;

   int cyklu = faktorial(size, size); // zjist? po?et permutac?

   int a; // korekce prvn?ho m?n?n?ho prvku prvku

   int b; // korekce druh?ho m?n?n?ho prvku prvku

   while (counter <= cyklu) {

      a = zjisti_a(counter); // zjist? korekci prvn?ho m?n?n?ho prvku prvku

      b = zjisti_b(counter); // zjist? korekci druh?ho m?n?n?ho prvku prvku

      print(pointer, size); // v?stup

      swap(pointer[size - a], pointer[size - b]); // z?m?na prvk?     

      counter++;

   }

}

   

void swap(int & a, int & b) { // Zam?n? prvky

   int temp;

   temp = a;

   a = b;

   b = temp;

}



void print(int * pointer, int size) {

   for (int counter = 0; counter < size; counter++) //Vytiskne v?echny prvky pole

      cout << pointer[counter];

   cout << endl;

}



int faktorial(int navrat, int cislo) { // Rekurzivn? fce pro v?po?et faktori?lu

    cislo--;

    if (cislo > 0) // Podm?nka pro rekurzivn? vol?n?

    navrat *= faktorial(cislo, cislo); /* Rekurzivn? vol? sama sebe s prvkem o jedna men??m a n?sob? j?m v?sledek (pro v?po?et faktori?lu) */ 

    return navrat; //vrac? hodnotu n?vratu

}



int zjisti_a(int counter) { // Zjist? korekci pro po?ad? prvku a (prvn?ho prvku)

if((counter % faktorial(7, 7)) == 0) //Pro ka?d? 7! prvek

    return 8;

if((counter % faktorial(6, 6)) == 0) //Pro ka?d? 720 prvek

    return 7;

if((counter % faktorial(5, 5)) == 0) //Pro ka?d? 120 prvek

    return 6;

if((counter % faktorial(4, 4)) == 0) //Pro ka?d? 24 prvek

    return 5;

if((counter % faktorial(3, 3)) == 0) //Pro ka?d? ?est? prvek

    return 4;

if((counter % faktorial(2, 2)) == 0) //Pro ka?d? druh? prvek

    return 3; 

else   // Pro ostatn? prvky

   return 2;   

}   

        

int zjisti_b(int counter) { // Zjist? korekci pro po?ad? prvku b (druh?ho prvku)

counter %= 24; // Celo??seln? zbytek po d?len? 24

if((counter % 18) == 0) //Pro 18-ct? prvkek ze 24

    return 3;

if((counter % 12) == 0) //Pro 12-ct? prvkek ze 24

    return 2; 

else

   return 1;  // Pro ostatn? prvky 

}      



/* Po?ad? zam??ovan?ch prvk? z?vis? na z?konech pro permutace, kter? jsem vypozoroval p?i pokusech s permutacemi */

/* Program po??t? jen pro permutace do 8 ??d?, jeliko? tyto permutace stejn? ani rozum? nevyp??e..., pro v?t?? permutace je pot?eba p?idat p??slu?n? ??dek na za??tek fce zjisti_a, jedn? se o stejn? ??dek jako jsou ostatn?, jen o jeden ??d vy???*/

A? bude ?as, dod?m koment??e, te? to fakt nedop??u, jelik? nem?m ?as - Kdo na to p?ijde jak to je, m? u m? bomb?n ;)... Jinak program v?m vyobraz? jen permutace p?ti - permutace ?esti u? maj? 720 ??dk?, tak?e budou u??zl?, program dopo??t? permutace max do permutac? 7, kdo by ale cht?l z n?jak?ho d?vodu v?c p?idejte p?ed ??dek:
if((counter % faktorial(7, 7)) == 0)
return 8;
??dek:
if((counter % faktorial(8, 8)) == 0)
return 9;
a tak d?le.....

Jinak to hodim ještě do zdrojáků...

Tak jsem přidal i komentáře.