Trouver toutes les permutations uniques d'une chaîne sans générer de doublons

Question

Trouver toutes les permutations d'une chaîne de caractères est un algorithme bien connu de Steinhaus-Johnson-Trotter. Mais si la chaîne contient des caractères répétés tels que
AABB,
alors les combinaisons uniques possibles seront 4!/(2 ! * 2 !) = 6

Une façon d'y parvenir est de les stocker dans un tableau, par exemple, puis de supprimer les doublons.

Existe-t-il un moyen plus simple de modifier l'algorithme de Johnson, afin de ne jamais générer les permutations dupliquées. (De la manière la plus efficace possible)

Answer 1

Utilisez l'algorithme récursif suivant :

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;
}

Comme vous le voyez, il est très facile

Answer 2

Commencez par convertir la chaîne de caractères en un ensemble de caractères uniques et de numéros d'occurrence, par exemple BANANA -> (3, A),(1,B),(2,N). (Cela peut être fait en triant la chaîne et en regroupant les lettres). Ensuite, pour chaque lettre de l'ensemble, ajoutez cette lettre à toutes les permutations de l'ensemble contenant une lettre de moins (notez la récursion). En poursuivant l'exemple de la "BANANE", nous avons : permutations((3,A),(1,B),(2,N)) = A :(permutations((2,A),(1,B),(2,N)) ++ B :(permutations((3,A),(2,N)) ++ N :(permutations((3,A),(1,B),(1,N))

Voici une implémentation fonctionnelle en 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 3

Je pense que ce problème est essentiellement le problème de générer permutations de multisets . ce document semble être pertinent : J. F. Korsh P. S. LaFollette. Loopless array generation of multiset permutations. The Computer Journal, 47(5):612-621, 2004.

Extrait du résumé : Cet article présente un algorithme sans boucle pour générer toutes les permutations d'un multiset. Chacune est obtenue à partir de son prédécesseur en effectuant une transposition. Il diffère des algorithmes précédents en utilisant un tableau pour les permutations mais ne nécessitant qu'un stockage linéaire dans sa longueur.

Answer 4

Dans ma solution, je génère récursivement les options, en essayant à chaque fois d'ajouter chaque lettre que je n'ai pas encore utilisée autant de fois que nécessaire.

#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);
}

utiliser un exemple :

#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 5

Il s'agit d'une question délicate et nous devons utiliser la récursion pour trouver toutes les permutations d'une chaîne de caractères. Par exemple, les permutations de "AAB" seront "AAB", "ABA" et "BAA". Nous devons également utiliser Définir pour s'assurer qu'il n'y a pas de valeurs en double.

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));
            }
        }

    }

}