CODEWITHSUNDEEP
calgorithmcombinatorics
titan
titan

Reputation: 435

Finding all the unique permutations of a string without generating duplicates

Finding all the permutations of a string is by a well known Steinhaus–Johnson–Trotter algorithm. But if the string contains the repeated characters such as
AABB,
then the possible unique combinations will be 4!/(2! * 2!) = 6

One way of achieving this is that we can store it in an array or so and then remove the duplicates.

Is there any simpler way to modify the Johnson algorithm, so that we never generate the duplicated permutations. (In the most efficient way)

Upvotes: 21

Views: 13004

Answers (5)

mukta
mukta

Reputation: 79

This is a tricky question and we need to use recursion to find all the permutations of a String, for example "AAB" permutations will be "AAB", "ABA" and "BAA". We also need to use Set to make sure there are no duplicate values.

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

    }

}

Upvotes: 0

Gangnus
Gangnus

Reputation: 24484

Use the following recursive algorithm:

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

As you see, it is very easy

Upvotes: 5

gcbenison
gcbenison

Reputation: 11963

First convert the string to a set of unique characters and occurrence numbers e.g. BANANA -> (3, A),(1,B),(2,N). (This could be done by sorting the string and grouping letters). Then, for each letter in the set, prepend that letter to all permutations of the set with one less of that letter (note the recursion). Continuing the "BANANA" example, we have: 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))

Here is a working implementation in 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))

Upvotes: 5

asaelr
asaelr

Reputation: 5456

In my solution, I generate recursively the options, try every time to add every letter that I didn't use as many times I need yet.

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

use example:

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

Upvotes: 1

Kris
Kris

Reputation: 1398

I think this problem is essentially the problem of generating multiset permutations. this paper seems to be relevant: J. F. Korsh P. S. LaFollette. Loopless array generation of multiset permutations. The Computer Journal, 47(5):612–621, 2004.

From the abstract: This paper presents a loopless algorithm to generate all permutations of a multiset. Each is obtained from its predecessor by making one transposition. It differs from previous such algorithms by using an array for the permutations but requiring storage only linear in its length.

Upvotes: 3

Related Questions