Esplorazione dello spazio - Permutazioni semplici e ripetute in C


  • Permutazioni semplici: le permutazioni semplici permettono di esplorare lo spazio delle soluzioni di n elementi dato un insieme di n elementi distinti, tenendo conto del loro ordine e senza ripetizione degli n elementi stessi; (esempio di utilizzo, anagrammi di una parola di n lettere distinte). Le permutazioni semplici sono delle disposizioni semplici con k = n.
    Vi sono esattamente n! permutazioni semplici.

    Esempio:

    int perm_s(int pos, int *val, int *sol, int *mark, int n, int count){
    int i;
    if(pos>=n){
    for(i = 0; i<n; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

    for(i = 0; i<n; i++){
    if(mark == 0){
    mark
    = 1;
    sol[pos] = val;
    count = perm_s(pos+1, val, sol, mark, n, count);
    mark
    = 0;
    }
    }
    return count;

    }


  • Permutazioni ripetute: permettono di esplorare lo spazio delle soluzioni di n elementi dato un multiinsieme di n elementi uguali fra loro a gruppi, considerandone l’ordine; la ripetizione degli elementi genera il multiinsieme. (esempio di utilizzo, anagrammi di una parola di n lettere con lettere ripetute).
    Vi sono esattamente (n!)/(n_oggetti1! x n_oggetti2! x ...) permutazioni ripetute.

    Esempio:

    int perm_r(int pos, int *dist_val, int *sol, int *mark, int n, int ndist, int count){
    int i;
    if(pos>=n){
    for(i = 0; i<n; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

    for(i = 0; i<ndist; i++){
    if(mark>0){
    mark
    --;
    sol[pos] = dist_val;
    count = perm_r(pos+1, dist_val, sol, mark, n, ndist, count);
    mark
    ++;
    }
    }
    return count;
    }

Hai bisogno di aiuto in Informatica?
Trova il tuo insegnante su Skuola.net | Ripetizioni
Registrati via email