• Bước 1: tạo mảng qhđ \(F[i]\):số hoán vị độ dài \(i\)
  • \(F[0] = 1\);
  • \(F[i] = F[i – 1] * i\);

• Bước 2: xét ví dụ
  N = 4
  a: 3 4 1 2
  Ta đi tìm số hoán vị có thứ tự từ điển nhỏ hơn dãy \(a\) là res.

  • \(i = 1\): tìm số hoán vị có phần tử đầu tiên \(< a[1]\) các số
    nhỏ hơn \(a[1]\) gồm \(1\) và \(2\),cứ mỗi phần tử \(x\) nhỏ hơn này
    sẽ có \(F[n – 1]\) dãy hoán vị có phần tử đầu tiên bằng \(x\) và
    thứ tự từ điển của chúng luôn nhỏ hơn dãy \(a\) chẳng hạn với \(x = 1\) có : (1 2 3 4); (1 2 4 3); (1 3 2 4); (1 3 4 2); (1 4 2 3); (1 4 3 2)
    \(res := res + 2 * F[n – 1] = 12\);
  • \(i = 2\): Ta đi tìm số hoán vị có phần tử đầu tiên \(= 3\)
    mà có thứ tự từ điển nhỏ hơn \(a\).Những phần tử
    này phải có phần tử thứ \(2\) nhỏ hơn \(a[2]\) và cứ
    mỗi phần tử sẽ có \(F[n – 2]\) hoán vị thõa mãn. Ở đây có giá trị 1 và 2 thõa mãn \(res:=res + 2 * F[n – 2] = 16\);
  • \(i=3\):Không có phần tử nào nhỏ hơn nữa
  • Tương tự \(i=4\): Cũng không có phần tử nào

Vậy kết quả sẽ là \((res + 1)=17\);

• Bước 3: Cho \(p\), đi tìm dãy \(b\) có thứ tự từ điển \(p\)
  => Làm ngược lại bước 2 ta có kết quả

Nguồn: kbook3