c++字典序

### C++ 中字典序的实现与用法 #### 1. 使用 `strcmp` 函数比较字符串字典序 在 C++ 中，可以通过标准库函数 `strcmp()` 来比较两个以 `\0` 结尾的字符数组（即 `char*` 类型）的字典序。该函数返回值的意义如下： - 如果第一个字符串的字典序小于第二个字符串，则返回负整数值。 - 如果第一个字符串的字典序大于第二个字符串，则返回正整数值。 - 如果两者相等，则返回零。 以下是示例代码展示其用法： ```cpp #include <iostream> #include <cstring> // 包含 strcmp 函数声明 int main() { const char s1[] = "apple"; const char s2[] = "banana"; if (strcmp(s1, s2) < 0) { std::cout << "\"" << s1 << "\" 的字典序小于 \"" << s2 << "\"." << std::endl; } else if (strcmp(s1, s2) > 0) { std::cout << "\"" << s1 << "\" 的字典序大于 \"" << s2 << "\"." << std::endl; } else { std::cout << "\"" << s1 << "\" 和 \"" << s2 << "\" 的字典序相同." << std::endl; } return 0; } ``` 此方法适用于基本的字符数组比较[^1]。 --- #### 2. 使用 `.compare()` 方法比较 `std::string` 对象 对于现代 C++ 编程中的字符串对象 (`std::string`)，可以直接调用成员函数 `.compare()` 进行字典序比较。`.compare()` 返回的结果与 `strcmp()` 完全一致。 下面是一个简单的例子来说明这一功能： ```cpp #include <iostream> #include <string> int main() { std::string str1 = "hello"; std::string str2 = "world"; if (str1.compare(str2) < 0) { std::cout << "\"" << str1 << "\" 的字典序小于 \"" << str2 << "\"." << std::endl; } else if (str1.compare(str2) > 0) { std::cout << "\"" << str1 << "\" 的字典序大于 \"" << str2 << "\"." << std::endl; } else { std::cout << "\"" << str1 << "\" 和 \"" << str2 << "\" 的字典序相同." << std::endl; } return 0; } ``` 这种方法更加灵活且推荐用于处理动态分配内存的情况。 --- #### 3. 下一个字典序排列的生成 为了计算给定序列的下一个字典序排列，可以采用以下步骤： 1. 找到最右侧的一个较小元素 A[k]，使得存在某个更大的元素位于它的右边； 2. 寻找右半部分中最小的大于 A[k] 的元素并与之交换位置； 3. 将原 k 后面的部分反转成升序状态即可得到新的次序。 下面是完整的实现代码片段： ```cpp #include <algorithm> #include <vector> #include <iostream> void next_permutation(std::vector<int>& nums) { int n = static_cast<int>(nums.size()); int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) --i; if (i >= 0) { int j = n - 1; while (j >= 0 && nums[j] <= nums[i]) --j; std::swap(nums[i], nums[j]); } std::reverse(nums.begin() + i + 1, nums.end()); } int main(){ std::vector<int> v{1, 2, 3}; do{ for(auto e : v){ std::cout<<e<<" "; } std::cout<<"\n"; next_permutation(v); }while(v != std::vector<int>{3, 2, 1}); return 0; } ``` 上述程序展示了如何通过循环迭代打印出所有可能的不同组合形式，并利用 STL 提供的功能简化操作过程[^2]^。 --- #### 4. 康托展开求解特定索引下的字典序排列 康托展开是一种将线性表映射至自然数集合上的双射关系技术，在解决某些涉及枚举或者查找指定排名的问题时非常有用。它基于阶乘权重体系构建起来的一套编码机制。 具体做法是从左往右依次考察每一位数字所处的位置编号 p_i ，并累加相应权值 w_i=(p_1)*(k−1)!+(p_2)*(k−2)!+…+(p_(m−1))*(1!) 。最终结果便是目标串在整个有序列表里的绝对定位号 r=w+m! 。 这里给出一段简单演示代码帮助理解原理: ```cpp long long cantor_expansion(const std::string& perm) { long long res = 0; int fact = 1; for(int i=perm.length()-1;i>=0;--i,fact*=perm.length()-i){ int smaller = 0; for(int j=i+1;j<perm.length(); ++j) if(perm[j]<perm[i]) ++smaller; res +=fact * smaller ; } return res; } ``` 这段逻辑能够快速判定任意长度固定字母组成的单词处于整体排序方案里哪个确切位子之上[^5]。 ---