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

Utiliser 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, c'est très facile

je pense que ce problème est essentiellement le problème de la génération permutations multiset. cet article semble pertinent: J. F. Korsh P. S. LaFollette. Génération de réseaux sans boucle de permutations multisets. Le Journal De L'Ordinateur, 47(5):612-621, 2004.

à Partir du résumé: Ce papier présente une loopless algorithme pour générer toutes les permutations d'un multiset. Chacun est obtenu à partir de son prédécesseur en faisant une transposition. Il diffère des algorithmes précédents en utilisant un tableau pour les permutations, mais nécessitant un stockage linéaire dans sa longueur.

convertissez D'abord la chaîne en un ensemble de caractères uniques et de numéros d'occurrences 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, préimprimer cette lettre à toutes les permutations de l'ensemble avec une moins de cette lettre (noter la récursion). La poursuite de la "BANANE", par exemple, 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))

Ici est un travail de mise 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))

dans ma solution, je génère récursivement les options, essayer à chaque fois d'ajouter chaque lettre que je n'ai pas utilisé autant de fois que j'ai besoin encore.

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

exemple d'utilisation:

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

c'est une question délicate et nous devons utiliser la récursion pour trouver toutes les permutations d'une chaîne, par exemple les permutations "AAB" seront "AAB", "ABA" et "BAA". Nous avons également besoin d'utiliser Set pour s'assurer qu'il n'y a pas de valeurs dupliquées.

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

    }

}