Finding all the unique permutations of a string without generating duplicates

c algorithm combinatorics
titan picture titan · Feb 9, 2012 · Viewed 10k times · Source

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)

Answer

Gangnus picture Gangnus · Feb 9, 2012

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

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
How to reverse a singly linked list using only two pointers?

I wonder if there exists some logic to reverse a singly-linked list using only two pointers. The following is used to reverse the single linked list using three pointers namely p, q, r: struct node { int data; struct node *link; }; …

Read More
hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More