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

Question

Нахождение всех перестановок строки осуществляется с помощью хорошо известного алгоритма Штайнхауса – Джонсона – Троттера.Но если строка содержит повторяющиеся символы, такие как
AABB,
, то возможные уникальные комбинации будут 4! / (2! * 2!) = 6

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

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

Answer 1

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

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 2

Сначала преобразуйте строку в набор уникальных символов и чисел вхождения, например, 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 3

Я думаю, что эта проблема, по сути, является проблемой генерации мультимножественных перестановок .эта статья кажется уместной: JF Korsh PS LaFollette.Генерация бесцикловых массивов мультимножественных перестановок.Компьютерный журнал, 47 (5): 612–621, 2004.

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

Answer 4

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

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

    }

}

Answer 5

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

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