Liste des permutations avec des répétitions dans le tableau 2D

Question

J'ai un problème pour lister les permutations avec des répétitions, en maintenant ce "style", avec des fonctions récursives.

ayant par exemple l'élément 2, « AB » et « CD », dans un tableau 2D:

Element[0][0] = A; Element[0][1] = B; // AB  
Element[1][0] = C; Element[1][1] = D; // CD 

Je veux obtenir toutes les permutations possibles avec la répétition des éléments n (dans ce cas 2) en k groupes (dans ce cas 2) et les enregistrer dans un nouveau tableau 2D Par exemple, dans:

Permutation[0][0] = AB; Permutation[0][1] = AB; // 1°: AB,AB 
Permutation[1][0] = AB; Permutation[1][1] = CD; // 2°: AB,CD 
Permutation[2][0] = CD; Permutation[2][1] = AB; // 3°: CD,AB 
Permutation[3][0] = CD; Permutation[3][1] = CD; // 4°: CD,CD 

élément et Permutation doit être un tableau à deux dimensions. Je essayé de cette façon, mais il ne fonctionne qu'avec une permutation de l'élément 2 en 2 groupes et je suis fermé à clef:

int i_perm = 0; 
    int i_element = 0; 
    int k_tot = 2; // number of groups 

    [...] 

    calcPerms(2); 

    [...] 

    private void calcPerms(int k) 
    { 
     if (k == 0) 
     { 
      if(i_perm + 1 < i_perm) 
       i_perm++; 

      i_element=0; 
     } 
     else 
     { 
      for (int i = 0; i < element.length; i++) 
      { 
       Permutation[i_perm][i_element][0] = Element[i][0]; 
       Permutation[i_perm][i_element][1] = Element[i][1]; 

       if(i_element + 1 < k_tot) 
        i_element++; 

       calcPerms(k - 1); 

       if(i_perm >= i_perm) 
        i_perm--; 

       Permutation[i_perm][i_element][0] = Element[i][0]; 
       Permutation[i_perm][i_element][1] = Element[i][1]; 
       if(i_element + 1 < k_tot) 
        i_element++; 
      } 
     } 
    } 

Cela fonctionne, comme mentionné ci-dessus, que sur les permutations de 2 éléments en groupes de 2, le retour correctement:

ABAB, ABCD, CDAB, CDCD.

En effet, si je mets 3 éléments (le 3ème élément est EF), il retourne:

ABAB, ABCD, CDEF, EFAB, ABCD, CDEF, EFAB, ABCD, EFEF

Au lieu de:

ABAB, ABCD, ABEF, CCRDC, CDCD, CDEF, EFAB, EFCD, EFEF

Comment puis-je obtenir ce que je veux? Merci à tous pour votre aide et présenter des excuses pour mon mauvais anglais

Answer 1

Qu'est-ce que vous avez besoin est le Heap's Algorithm

Il y a un code pseudo clair mise en œuvre dans la page wikipedia liée.

La version non récursif ressemble à ceci

procedure generate(n : integer, A : array of any): 
    c : array of int 

    for i := 0; i < n; i += 1 do 
     c[i] := 0 
    end for 

    output(A) 

    i := 0; 
    while i < n do 
     if c[i] < i then 
      if i is even then 
       swap(A[0], A[i]) 
      else 
       swap(A[c[i]], A[i]) 
      end if 
      output(A) 
      c[i] += 1 
      i := 0 
     else 
      c[i] := 0 
      i += 1 
     end if 
    end while