modifying algorithm to generate unique permutations in a string that contains duplicates

Question

I'm aware of handling the issue with duplicates if I were to use a swap and permute method for generating permutations as shown here.

However, I'm using a different approach where I place current character between any two characters, at the beginning and at the end, of all of the permutations generated without the current character.

How can I modify my code below to give me only unique permutations in a string that contains duplicates

import java.util.ArrayList;

public class Permutations {
    public static void main(String[] args) {
        String str = "baab";
        System.out.println(fun(str, 0));
        System.out.println("number of Permutations =="+fun(str, 0).size());
    }

    static ArrayList<String> fun(String str, int index)
    {
        if(index == str.length())
        {
            ArrayList<String> al = new ArrayList<String>();
            al.add("");
            return al;
        }

        /* get return from lower frame */
        ArrayList<String> rec = fun(str, index+1);

        /* get character here */
        char c = str.charAt(index);

        /* to each of the returned Strings in ArrayList, add str.charAt(j) */
        ArrayList<String> ret = new ArrayList<String>();
        for(int i = 0;i<rec.size();i++)
        {
            String here = rec.get(i);
            ret.add(c + here);
            for(int j = 0;j<here.length();j++)
                ret.add(here.substring(0,j+1) + c + here.substring(j+1,here.length()));
        }
        return ret;
    }
}

At the moment, a string such as "bab" generates the following output, which contain abb and bba multiple times.

[bab, abb, abb, bba, bba, bab]
number of Permutations ==6

PS : I do not want to use a hashmap/Set to keep track of my duplicates and see whether they were encountered previously.

@VaibhavBajaj, hi. As I said, I'm aware of a solution to solve the problem as such, I'm looking for a modification for this particular implementation. — saltandwater
– saltandwater, Commented Jul 29, 2016 at 22:27

samgak · Accepted Answer · 2016-07-30 00:19:52Z

2

When you're iterating through the string and adding the character at each position, if you find a character in the string that is the same as the one you are inserting, break after inserting the new character immediately before it. This means that strings with the same character more than once can only be formed one way (by inserting in reverse order) so duplicates can't happen.

for(int j = 0;j<here.length();j++)
{
    if(here.charAt(j) == c)
        break;  
    ret.add(here.substring(0,j+1) + c + here.substring(j+1,here.length()));
}

A general approach to solving these problems involving generating sets without duplicates is to think of a property that only one of each set of duplicates will have, and then enforce that as a constraint. For example in this case the constraint is "all duplicated characters are added in reverse order" (forward order would work just as well, but you'd have to flip the loop direction). For a combination problem where the order isn't important, the constraint could be "items in each list are in ascending order". And so on.

edited Jul 30, 2016 at 0:19

answered Jul 29, 2016 at 23:55

samgak

24.5k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

saltandwater Over a year ago

this is so elegant. Abs awesome!

saltandwater Over a year ago

just had a question. Say, our string is babcd. Say, I have generated all 24 permutations with abcd and am now, at the step where I'm going to insert b at each of the locations. According to your logic, for a string like abcd, upon adding 'b' we generate 1)babcd and 2)abbcd, but break after that. My question is, it makes sense to ignore a permutation like ab + 'b' + cd == abbcd again. But how can we ignore the combinations ahead such as abc + b + d == abcbd. I drew the recursion and see that these are generated in some other frame. But how is it that all of these are taken care of ?

samgak Over a year ago

That would be taken care of by generating acbd and then inserting b in the second position, which doesn't break the rule.

samgak Over a year ago

It means that a character can only be added to a string before existing instances of that character in the string. E.g. adding b to abcd to make babcd is ok. Adding b to abcd to make abcbd is not ok.

samgak Over a year ago

Another way to look at it: suppose you permute the string abb and get two duplicates of bab. One would have been formed by adding b to the start of ab. One would have been formed by adding b to the end of ba. Disallowing the second removes the duplicate.

|

Collectives™ on Stack Overflow

modifying algorithm to generate unique permutations in a string that contains duplicates

1 Answer 1

10 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Related