Trovare tutte le permutazioni univoche di una stringa senza generare duplicati

Question

La ricerca di tutte le permutazioni di una stringa avviene tramite un algoritmo ben noto di Steinhaus-Johnson-Trotter. Ma se la stringa contiene i caratteri ripetuti
AABB,
quindi le possibili combinazioni uniche saranno 4!/(2 * 2!) = 6

Un modo per ottenere questo risultato è che siamo in grado di conservarlo in un array o così e quindi rimuovere i duplicati.

Esiste un modo più semplice per modificare l'algoritmo di Johnson, in modo da non generare mai permutazioni duplicate. (Nel modo più efficiente)

Answer 1

Nella mia soluzione, generi in modo ricorsivo le opzioni, provo ogni volta ad aggiungere tutte le lettere che non ho usato tutte le volte che mi servono ancora.

#include <string.h> 

void fill(char ***adr,int *pos,char *pref) { 
    int i,z=1; 
    //loop on the chars, and check if should use them 
    for (i=0;i<256;i++) 
     if (pos[i]) { 
      int l=strlen(pref); 
      //add the char 
      pref[l]=i; 
      pos[i]--; 
      //call the recursion 
      fill(adr,pos,pref); 
      //delete the char 
      pref[l]=0; 
      pos[i]++; 
      z=0; 
     } 
    if (z) strcpy(*(*adr)++,pref); 
} 

void calc(char **arr,const char *str) { 
    int p[256]={0}; 
    int l=strlen(str); 
    char temp[l+1]; 
    for (;l>=0;l--) temp[l]=0; 
    while (*str) p[*str++]++; 
    fill(&arr,p,temp); 
} 

uso esempio:

#include <stdio.h> 
#include <string.h> 

int main() { 
    char s[]="AABAF"; 
    char *arr[20]; 
    int i; 
    for (i=0;i<20;i++) arr[i]=malloc(sizeof(s)); 
    calc(arr,s); 
    for (i=0;i<20;i++) printf("%d: %s\n",i,arr[i]); 
    return 0; 
} 

Answer 2

Utilizzare il seguente algoritmo ricorsivo:

PermutList Permute(SymArray fullSymArray){ 
    PermutList resultList=empty; 
    for(each symbol A in fullSymArray, but repeated ones take only once) { 
     PermutList lesserPermutList= Permute(fullSymArray without A) 
     for (each SymArray item in lesserPermutList){ 
      resultList.add("A"+item); 
     } 
    } 
    return resultList; 
} 

Come si vede, è molto facile

Answer 3

Penso che questo problema è essenzialmente il problema di generazione delle permutazioni multiset . questo articolo sembra essere pertinente: J. F. Korsh P. S. LaFollette. Generazione di array loopless di permutazioni multiset. The Computer Journal, 47 (5): 612-621, 2004.

Dall'estratto: Questo documento presenta un algoritmo senza loop per generare tutte le permutazioni di un multiset. Ognuno è ottenuto dal suo predecessore effettuando una trasposizione. Si differenzia dai precedenti algoritmi usando una matrice per le permutazioni, ma richiede memoria solo lineare nella sua lunghezza.

Answer 4

Prima converti la stringa in un set di caratteri univoci e numeri di occorrenza, ad es. BANANA -> (3, A), (1, B), (2, N). (Questo può essere fatto ordinando la stringa e raggruppando le lettere). Quindi, per ogni lettera dell'insieme, anteponi quella lettera a tutte le permutazioni dell'insieme con una lettera in meno di quella lettera (nota la ricorsione). Continuando l'esempio "BANANA", abbiamo: permutazioni ((3, A), (1, B), (2, N)) = A: (permutazioni ((2, A), (1, B), (2 , N)) ++ B: (permutazioni ((3, A), (2, N)) ++ N: (permutazioni ((3, A), (1, B), (1, N))

Ecco un'implementazione di lavoro in Haskell:

circularPermutations::[a]->[[a]] 
circularPermutations xs = helper [] xs [] 
          where helper acc [] _ = acc 
           helper acc (x:xs) ys = 
            helper (((x:xs) ++ ys):acc) xs (ys ++ [x]) 

nrPermutations::[(Int, a)]->[[a]] 
nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))] 
nrPermutations xs = concat (map helper (circularPermutations xs)) 
    where helper ((1,x):xs) = map ((:) x)(nrPermutations xs) 
     helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs)) 

Answer 5

Questa è una domanda difficile e abbiamo bisogno di usare la ricorsione per trovare tutte le permutazioni di una stringa, ad esempio "AAB" permutazioni saranno "AAB", " ABA "e" BAA ". Abbiamo anche bisogno di usare Set per assicurarci che non ci siano valori duplicati

import java.io.*; 
import java.util.HashSet; 
import java.util.*; 
class Permutation { 

    static HashSet<String> set = new HashSet<String>(); 
    public static void main (String[] args) { 
    Scanner in = new Scanner(System.in); 
     System.out.println("Enter :"); 
     StringBuilder str = new StringBuilder(in.nextLine()); 
     NONDuplicatePermutation("",str.toString()); //WITHOUT DUPLICATE PERMUTATION OF STRING 
     System.out.println(set); 
    } 


    public static void NONDuplicatePermutation(String prefix,String str){ 
     //It is nlogn 
     if(str.length()==0){ 
      set.add(prefix); 
     }else{ 
      for(int i=0;i<str.length();i++){ 

       NONDuplicatePermutation(prefix+ str.charAt(i), str.substring(0,i)+str.substring(i+1)); 
      } 
     } 

    } 

}