Представлять порядок перестановки, используя целое число?

Question

Предположим, что есть N (N = 10) букв A, B, ..., J. String S является экземпляром перестановки.

Я хочу сохранить порядок перестановок 32-разрядным целым числом p и преобразовать строку String S в порядок p, а для проверки целочисленного значения я написалкак то так:

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

Работает не так эффективно.Это значит,

1. Невозможно добавить еще одну букву.(max (N) = 10)
2. В P2S используется дополнительная таблица поиска для определения 10-й буквы.
3. PCheck(int) слишком медленно.

Как сделать лучше?Прямой кусок кода приветствуется.

Answer 1

Я думаю, что вы заинтересованы в факторальном .Это позволяет вам определить, что такое n-я лексикографическая перестановка 0 1 ... n - 1 и какую позицию занимает данная перестановка того же набора в лексикографическом порядке всех перестановок, и это также эффективно.

Answer 2

Есть ли лучший алгоритм?

Ознакомьтесь с TAOCP Кнута Том 4, глава 2, Генерация всех кортежей и перестановок (хотя я думаю, что он скоро выйдет в виде физической книги). Он решает эту проблему там.