Repräsentieren Reihenfolge der Permutation mit einer ganzen Zahl?

Question

Angenommen, es gibt N (N = 10) Buchstaben A, B, ..., J. String S ist eine Instanz der Permutation.

ich die Reihenfolge der Permutation speichern möchten durch eine 32-Bit-Integer p und zwischen dem String S und der Reihenfolge p und zu validieren den Integer-Wert, ich habe so etwas wie dies geschrieben zu konvertieren:

int S2P(char *s) { 
    unsigned int p = 0; 
    char c; 
    while (c = *s++) { 
     c -= 'A'; 
     p *= 10; 
     p += c; 
    } 
    return p; 
} 

char *P2S(unsigned int p, char *buf) { 
    char *s = buf + 10; 
    char used[20], *t; 
    int i, j, c; 
    strcpy(used, "ABCDEFGHIJ"); 
    *s-- = '\0'; 
    for (i = 1; i < 10; i++) { 
     *s-- = c = 'A' + (p % 10); 
     p /= 10; 
     t = strchr(used, c); 
     if (t) 
      *t = '-'; 
    } 
    for (i = 0; i < 10; i++) 
     if (used[i] != '-') 
      *s = used[i]; 
    return buf; 
} 

int PCheck(int p) { 
    char tmp[20]; 
    int q = S2P(P2S(p, tmp)); 
    return p == q; 
} 

Es funktioniert nicht so effizient. Das bedeutet,

1. Es ist nicht möglich, einen weiteren Buchstaben hinzuzufügen. (max (N) = 10)
2. In P2S wird eine zusätzliche Nachschlagetabelle verwendet, um den 10. Buchstaben herauszufinden.
3. PCheck(int) ist zu langsam.

Wie macht man es besser? Ein gerades Stück Code wird geschätzt.

Answer 1

Gibt es einen besseren Algorithmus?

Check out Knuth's TAOCP Volume 4 Faszikel 2, generieren Alle Tupeln und Permutationen (ich glaube, es sehr bald in physischen Buchform heraus sein wird, obwohl). Er spricht dieses Problem dort an.

Answer 2

Ich glaube, Sie sind an der factoradic interessiert. Dies ermöglicht es Ihnen, zu finden, was die n lexikographische Permutation von 0 1 ... n - 1 ist und welche Position eine gegebene Permutation des gleichen Satzes in der lexikographischen Ordnung aller Permutationen hat, und es ist auch effizient.