Odnajdywanie wszystkich unikalnych permutacji ciągu bez generowania duplikatów

Question

Znalezienie wszystkich permutacji struny odbywa się za pomocą dobrze znanego algorytmu Steinhausa-Johnsona-Trottera. Ale jeśli ciąg zawiera powtarzające się znaki takie jak
AABB,
następnie ewentualne unikalne kombinacje będą 4!/(2! * 2!) = 6

Jednym ze sposobów osiągnięcia tego jest to, że można je przechowywać w tablicy, a następnie usuń duplikaty.

Czy istnieje prostszy sposób modyfikacji algorytmu Johnsona, abyśmy nigdy nie generowali zduplikowanych permutacji. (W najbardziej efektywny sposób)

Answer 1

W moim rozwiązaniu generuję rekursywnie opcje, próbuję za każdym razem dodawać każdą literę, której nie używałem tyle razy, ile potrzebuję. Przykładem

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

zastosowanie:

#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

Użyj następującego rekurencyjny algorytm:

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

Jak widać, jest to bardzo proste

Answer 3

myślę, problem ten jest w istocie problem generowania permutacji wielostopniowych . ten artykuł wydaje się mieć znaczenie: J. F. Korsh P. S. LaFollette. Bezpołączeniowa generacja macierzowa permutacji multiset. The Computer Journal, 47 (5): 612-621, 2004.

Z abstraktu: W niniejszym artykule przedstawiono algorytm bezkierunkowy do generowania wszystkich permutacji multiset. Każdy otrzymuje od swojego poprzednika, dokonując jednej transpozycji. Różni się od poprzednich takich algorytmów za pomocą tablicy dla permutacji, ale wymaga przechowywania tylko liniowy na swojej długości.

Answer 4

Najpierw skonwertuj ciąg znaków na zestaw unikatowych znaków i liczb wystąpienia, np. BANANA -> (3, A), (1, B), (2, N). (Można to zrobić, sortując ciąg i litery grupujące). Następnie, dla każdej litery w zbiorze, dodaj tę literę do wszystkich permutacji zestawu za pomocą jednej mniej tej litery (zwróć uwagę na rekursję). Kontynuując przykład "BANAN", mamy: permutacje ((3, A), (1, B), (2, N)) = A: (permutacje ((2, A), (1, B), (2 , N)) ++ B: (permutacje ((3, A), (2, N)) ++ N: (permutacje ((3, A), (1, B), (1, N))

Oto realizacja pracy w 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

jest to trudne pytanie i musimy użyć rekurencji do znalezienia wszystkich permutacji ciągiem znaków, na przykład „AAB” permutacje będzie „AAB”, " ABA”i«BAA». Musimy również użyć Ustaw aby upewnić się, że nie są zduplikowane wartości.

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

    } 

}