정수를 사용하여 순열을 표현 하시겠습니까?

Question

N (N = 10) 문자 A, B, ..., J가 있다고 가정합니다. S은 순열의 인스턴스입니다.

내가 32 비트 정수 p에 의해 순열의 순서를 저장하고, 문자열 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

더 좋은 알고리즘이 있습니까?

체크 아웃 Knuth's TAOCP 4 권 분책 2, 생성 모든 튜플과 순열은 (비록 그것이 매우 곧 종이 책 형태가 될 것이라 생각합니다). 그는이 문제를 거기에서 다룹니다.

Answer 2

나는 factoradic에 관심이 있다고 생각합니다. 이것은 n 사전 순열이 0 1 ... n - 1이고, 동일한 집합의 주어진 순열이 모든 순열의 사전 식 순서에 포함되어 있는지를 확인할 수있게하며, 또한 효율적입니다.