字典序

说在前面

字典序(dictionary order)，又称字母序(alphabetical order)，原意是表示英文单词在字典中的先后顺序，后引申为任意两个字符串的大小关系

那么大家就清楚了这指的是一种大小关系，一种序，正如我们数学分析中的有序集的序有类似的概念，这里大家需要与字典树(Tire)区分开来，字典树实质上是一种数据结构中的用于存储和查找单词的一种树状结构，详情可以看这个tire。(在我的另一篇blog可以看到哦)

字典序算法相关

字典序全排列问题


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//交换两个字符，注意这里传过去的是地址，改变的是地址对应的值
void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}
//将一个字符串begin到end的部分逆序
void reverse(char *str, int begin, int end) {
    while (begin < end) {
        swap(&str[begin], &str[end]);
        begin++;
        end--;
    }
}
int next_permutation(char *str, int n) {
    int i;
    for (i = n - 2; i >= 0; i--) {
        if (str[i] < str[i + 1]) {
            break;
        }
    }
//从后往前找到第一个正序的
    if (i < 0) {		//表示找完了，已经全部是逆序了
        return 0;
    }
//从i开始找到前面的第一个比str[i]大的，那么就进行交换
//再把i+1以后的逆序一遍
    int j;
    for (j = n - 1; j > i; j--) {
        if (str[j] > str[i]) {
            break;
        }
    }
    swap(&str[i], &str[j]);
    reverse(str, i + 1, n - 1);
    return 1;
}
int main() {
    char str[] = "abd";
    int len = strlen(str);
    do {
        printf("%s\n", str);
    } while (next_permutation(str, len));
    return 0;
}