Permutazioni semplici e ripetute in C

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 printf(“%d ”, sol);
  printf(“\n”);
  return count+1;
  }

  for(i = 0; 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 printf(“%d ”, sol);
  printf(“\n”);
  return count+1;
  }

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