Permutation of String letters: How to remove repeated permutations?_问答_开发者

Here is a standard function to print the permutations of characters of a string:

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j < n; j++) //check till end of string
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

It works fine but there is a problem, it also prints some duplicate permutations, exapmle:

if string is "AAB"

the output is:

AAB
ABA
AAB
ABA开发者_如何转开发
BAA
BAA

This is having 3 duplicate entries as well.

Can there be a way to prevent this to happen?

Thanks

Alok Kr.

Take notes which chars you swapped previously:

 char was[256];
 /*
 for(j = 0; j <= 255; j++)
    was[j] = 0;
 */
 bzero(was, 256);
 for (j = i; j <= n; j++)
 {
    if (!was[*(a+j)]) {
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
      was[*(a+j)] = 1;
    }
 }

This has to be the fastest one from the entries so far, some benchmark on a "AAAABBBCCD" (100 loops):

native C             - real    0m0.547s
STL next_permutation - real    0m2.141s

Standard library has what you need:

#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
using namespace std;

void print_all_permutations(const string& s)
{
    string s1 = s;
    sort(s1.begin(), s1.end()); 
    do {
        cout << s1 << endl;
    } while (next_permutation(s1.begin(), s1.end()));
}

int main()
{
    print_all_permutations("AAB");
}

Result:

$ ./a.out
AAB
ABA
BAA

Another approach could be:

Presort the array.
This will ensure that all duplicate are now consecutive.
So, we just need to see the previous element which we we fixed (and permuted others)
if current element is same as previous, don't permute.

I would do it the following way: First, I generate "groups" of characters (i.e. AABBBC yields two groups: (AA) and (BBB) and (C).

First, we iterate over all distributions of AA onto the n characters. For each distribution found, we iterate over all distributions of BBB onto the n-2 remaining characters (not occupied by an A). For each of these distributions involving As and Bs, we iterate over all distributions of C onto the remaining free character positions.

You can use std::set to ensure uniqueness of the results. That is if it is C++ (because you tagged it as such).

Otherwise - go through the list of the results manually and remove duplicates.

You'll have to save the results and post-process them of course, not print immediately as you do now.

It would quite simple if you just think it as a problem where you need to store all the permutations for some future use.

SO you'll have an array of permuted strings.

Now think of a new problem, which is also an standard one where you need to remove the duplicates from array.

I hope that helps.

@Kumar, I think what you want is something like the following:

#include <stdio.h>
#include <string.h>

/* print all unique permutations of some text. */
void permute(int offset, int* offsets, const char* text, int text_size)
{
    int i;

    if (offset < text_size) {
            char c;
            int j;

            /* iterate over all possible digit offsets. */
            for (i=0; i < text_size; i++) {
                    c=text[i];
                    /* ignore if an offset further left points to our
                       location or to the right, with an identical digit.
                       This avoids duplicates. */
                    for (j=0; j < offset; j++) {
                            if ((offsets[j] >= i) &&
                                (text[offsets[j]] == c)) {
                                    break;
                            }
                    }

                    /* nothing found. */
                    if (j == offset) {
                            /* remember current offset. */
                            offsets[offset]=i;
                            /* permute remaining text. */
                            permute(offset+1, offsets, text, text_size);
                    }
            }
    } else {
            /* print current permutation. */
            for (i=0; i < text_size; i++) {
                    fputc(text[offsets[i]], stdout);
            }
            fputc('\n', stdout);
    }
}

int main(int argc, char* argv[])
{
    int i, offsets[1024];

    /* print permutations of all arguments. */
    for (i=1; i < argc; i++) {
            permute(0, offsets, argv[i], strlen(argv[i]));
    }

    return 0;
}

This code is C, as requested, it's pretty fast and does what you want. Of course it contains a possible buffer overflow because the offset buffer has a fixed size, but this is just an example, right?

EDIT: Did anyone try this out? Is there a simpler or faster solution? It's disappointing noone commented any further!

void permute(string set, string prefix = ""){
    if(set.length() == 1){
            cout<<"\n"<<prefix<<set;
    }
    else{
            for(int i=0; i<set.length(); i++){
                    string new_prefix = prefix;
                    new_prefix.append(&set[i], 1);
                    string new_set = set;
                    new_set.erase(i, 1);
                    permute(new_set, new_prefix);
            }
    }
}

And simply use it as permute("word");

Do not permute for same character at different position of the string.

In Python:

def unique_permutation(a, l, r):
    if l == r:
        print ''.join(a)
        return
    for i in range(l, r+1):
        if i != l and a[i] == a[l]:
            continue
        a[i], a[l] = a[l], a[i]
        unique_permutation(a, l+1, r)
        a[i], a[l] = a[l], a[i]

Algorithm steps:

Store the given string into temporary string say "temp"
Remove duplicates from temp string
And finally call "void permute(char *a, int i, int n)" function to print all permutation of given string without duplicates

I think, this is best and efficient solution.