Поиск всех уникальных перестановок строки без генерации дубликатов

Question

Поиск всех перестановок строки осуществляется с помощью известного алгоритма Steinhaus-Johnson-Trotter. Но если строка содержит повторяющиеся символы, такие как
AABB,
то возможные уникальные комбинации будет 4!/(2! * 2!) = 6

Одним из способов достижения этого является то, что мы можем хранить его в массиве или так, а затем удалите дубликаты.

Есть ли более простой способ изменить алгоритм Джонсона, чтобы мы никогда не генерировали дублированные перестановки. (Наиболее эффективным способом)

Answer 1

В моем решении я генерирую рекурсивные параметры, каждый раз добавляя каждую букву, которую я не использовал столько раз, сколько мне нужно.

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

использование пример:

#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

Использовать следующий рекурсивный алгоритм:

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

Как вы видите, это очень легко

Answer 3

Я думаю, что эта проблема, по существу, проблема генерации многопозиционные перестановки. эта статья, по-видимому, актуальна: J. F. Korsh P. S. LaFollette. Генерация бесконечного массива многопозиционных перестановок. Computer Journal, 47 (5): 612-621, 2004.

Из статьи: Настоящий документ представляет собой алгоритм без петли для генерации всех перестановок мультимножества. Каждый из них получается из своего предшественника, делая одну транспозицию. Он отличается от предыдущих таких алгоритмов, используя массив для перестановок, но требующий хранения только линейного по своей длине.

Answer 4

Сначала преобразуйте строку в набор уникальных символов и номеров чисел, например. BANANA -> (3, A), (1, B), (2, N). (Это можно сделать путем сортировки строки и группировки букв). Затем для каждой буквы в наборе добавьте эту букву ко всем перестановкам набора с одним меньшим из этой буквы (обратите внимание на рекурсию). Продолжая пример «BANANA», мы имеем: перестановки ((3, A), (1, B), (2, N)) = A: (перестановки ((2, A), (1, B), (2 , N)) ++ B: (перестановки ((3, A), (2, N)) ++ N: (перестановки ((3, A), (1, B), (1, N))

Вот рабочая реализация в 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

Это сложный вопрос, и мы должны использовать рекурсию, чтобы найти все перестановки в строку, например, «AAB» перестановки будут «AAB», " ABA "и" BAA ". Нам также необходимо использовать Комплект, чтобы убедиться, что нет повторяющихся значений.

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

    } 

}