当前位置： 面试刷题>> 排列序号Ⅰ (经典算法题500道)
### 题目描述补充
**题目：排列序号Ⅰ**
给定一个整数 n，返回从 1 到 n 的所有整数的排列序号。每个数字都有唯一的序号，序号的规则是基于字典序的排列。即，第一个排列是 "123..."，最后一个排列是 "n(n-1)...321"，并据此为它们分配序号从 1 到 n!。
**示例**：
输入：n = 3
输出：[1, 2, 3, 4, 5, 6]
解释：对于 n = 3，有6种排列：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。它们对应的序号分别为：[1, 2, 3, 4, 5, 6]。
**要求**：
- 编写一个函数来计算给定整数 n 的所有排列的序号。
- 考虑到效率，不要直接生成所有排列然后排序。
### PHP 示例代码
```php
function factorial($n) {
$result = 1;
for ($i = 2; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
function permutationIndex($nums) {
$n = count($nums);
$factorialCache = array_fill(0, $n, 0);
$factorialCache[0] = 1;
for ($i = 1; $i < $n; $i++) {
$factorialCache[$i] = $factorialCache[$i - 1] * ($i + 1);
}
$index = 1;
for ($i = 0; $i < $n; $i++) {
$smaller = 0;
for ($j = $i + 1; $j < $n; $j++) {
if ($nums[$j] < $nums[$i]) {
$smaller++;
}
}
$index += $smaller * $factorialCache[$n - $i - 1];
}
return $index;
}
// 示例用法
$nums = [1, 2, 3];
$n = count($nums);
$totalPermutations = factorial($n);
for ($i = 0; $i < $totalPermutations; $i++) {
$perm = permute($nums); // 假设permute函数可以生成下一个排列
echo permutationIndex($perm) . " ";
// 注意：这里需要实现permute函数来生成下一个排列，但题目主要关注的是排列序号计算
}
// 注意：上述代码示例中的permute函数未给出，因为它不是本题的重点。
// 实际面试中，可能需要你专注于permutationIndex函数的实现。
```
### Python 示例代码
```python
def factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
def permutationIndex(nums):
n = len(nums)
factorial_cache = [1] * n
factorial_cache[0] = 1
for i in range(1, n):
factorial_cache[i] = factorial_cache[i - 1] * (i + 1)
index = 1
for i in range(n):
smaller = sum(1 for j in range(i + 1, n) if nums[j] < nums[i])
index += smaller * factorial_cache[n - i - 1]
return index
# 示例用法
nums = [1, 2, 3]
total_permutations = factorial(len(nums))
# 这里省略了生成所有排列的代码，因为它不是本题的重点
```
### JavaScript 示例代码
```javascript
function factorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result *= i;
}
return result;
}
function permutationIndex(nums) {
const n = nums.length;
const factorialCache = new Array(n).fill(0);
factorialCache[0] = 1;
for (let i = 1; i < n; i++) {
factorialCache[i] = factorialCache[i - 1] * (i + 1);
}
let index = 1;
for (let i = 0; i < n; i++) {
let smaller = 0;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[i]) {
smaller++;
}
}
index += smaller * factorialCache[n - i - 1];
}
return index;
}
// 示例用法
const nums = [1, 2, 3];
const totalPermutations = factorial(nums.length);
// 注意：这里同样省略了生成所有排列的代码
```
**码小课网站中有更多相关内容分享给大家学习**，包括算法基础、数据结构与算法进阶等内容，可以帮助大家更好地掌握编程技能。