Permutation von String-Buchstaben: Wie entfernt man wiederholte Permutationen?

Question

Hier ist eine Standardfunktion, die die Permutationen von Zeichen einer Zeichenkette ausgibt:

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

Es funktioniert gut, aber es gibt ein Problem, es druckt auch einige doppelte Permutationen, exapmle:

wenn die Zeichenkette "AAB" ist

ist die Ausgabe:

AAB
ABA
AAB
ABA
BAA
BAA

Auch hier gibt es 3 doppelte Einträge.

Gibt es eine Möglichkeit, dies zu verhindern?

--

Gracias

Alok Kr.

Answer 1

Es wäre ganz einfach, wenn Sie es als ein Problem betrachten, bei dem Sie alle Permutationen für eine spätere Verwendung speichern müssen.

SO erhalten Sie ein Array von permutierten Strings.

Stellen Sie sich nun ein neues Problem vor, das auch ein Standardproblem ist, bei dem Sie die Duplikate aus dem Array entfernen müssen.

Ich hoffe, das hilft.

Answer 2

@Kumar, ich denke, was Sie wollen, ist etwas wie das Folgende:

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

Dieser Code ist, wie gewünscht, in C. Er ist ziemlich schnell und tut, was Sie wollen. Natürlich enthält er einen möglichen Pufferüberlauf, weil der Offset-Puffer eine feste Größe hat, aber das ist nur ein Beispiel, richtig?

EDIT: Hat das jemand ausprobiert? Gibt es eine einfachere oder schnellere Lösung? Es ist enttäuschend, dass niemand einen weiteren Kommentar abgegeben hat!

Answer 3

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

Und verwenden Sie es einfach als permute("Wort");

Answer 4

Permutieren Sie nicht dasselbe Zeichen an verschiedenen Positionen der 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]

Answer 5

Schritte des Algorithmus:

1. Speichert die angegebene Zeichenkette in der temporären Zeichenkette "temp".
2. Duplikate aus der temporären Zeichenfolge entfernen
3. Und schließlich rufen Sie die Funktion "void permute(char *a, int i, int n)" auf, um alle Permutationen der angegebenen Zeichenkette ohne Duplikate zu drucken

Ich denke, das ist die beste und effizienteste Lösung.