字典序算法与下一个排列问题算法推导

柔情只为你懂 2022-12-20 03:16 179阅读 0赞

### 字典序算法 ###

*  一.字典序基础
 *  二.字典序算法相关
 *  下一个排列问题
 *   *  算法推导
     *  算法过程
 *  求字典序全排列
 *   *  递归方法

# 一.字典序基础 #

**字典序（dictionary order）**，又称 **字母序（alphabetical order）**，原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

英文中的 **字母表（Alphabet）** 按照如下的顺序排列：

ABCDEFG HIJKLMN OPQRST UVWXYZ

abcdefg hijklmn opqrst uvwxyz

在字典中，单词是按照首字母在字母表中的顺序进行排列的，比如 alpha 在 beta 之前。而第一个字母相同时，会去比较两个单词的第二个字母在字母表中的顺序，比如 account 在 advanced 之前，以此类推。下列单词就是按照字典序进行排列的：

aster

astrolabe

astronomy

astrophysics

ataman

attack

baa

在绝大多数语言中，都提供了比较两个字符串大小的方法，比较的实际上就是两个字符串的字典序。例如C++ 语言中：

cout << ("ah1x" < "ahb") << endl;

这个数是两个字符串第一个不一样的位置的两个字符的 ASCII 值之差，如果小于零则说明第一个字符串小于第二个字符串。

除此之外，大多数语言也都有对应的字符串比较方法，而背后的核心都是字符串的字典序。理解并掌握这个重要的概念，对今后计算机专业课程的学习和程序开发有很大帮助

# 二.字典序算法相关 #

1.字典序全排列问题

示例：`1 2 3`的全排列如下：

> 1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1

*  我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找`124653`的下一个排列）

*  如果当前排列是`124653`，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
 *  如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
 *  本例中将找到`46`，计`4`所在的位置为`i`,找到后不能直接将`46`位置互换，而又要从右到左到第一个比`4`大的数
 *  本例找到的数是`5`，其位置计为`j`，将`i`与`j`所在元素交换`125643`
 *  然后将`i+1`至最后一个元素从小到大排序得到`125346`，这就是`124653`的下一个排列

下图是用字典序法找`1 2 3`的全排列（全过程）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]

# 下一个排列问题 #

“下一个排列”的定义是：**给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。**

我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。

## 算法推导 ##

如何得到这样的排列顺序？我们可以这样来分析：

*  我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
 *  我们还希望下一个数增加的**幅度尽可能的小**，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
    
     *  在尽可能靠右的低位进行交换，需要**从后向前查找**，将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
 *  将「大数」换到前面后，需要将「大数」后面的所有数**重置为升序**，**升序排列就是最小的排列**。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

以上就是求“下一个排列”的分析过程。

## 算法过程 ##

标准的“下一个排列”算法可以描述为：

1.  从后向前查找第一个相邻升序的元素对 (i,j)，满足 A\[i\] < A\[j\]。此时 \[j,end) 必然是降序
2.  在 \[j,end) 从后向前查找第一个满足 A\[i\] < A\[k\] 的 k。A\[i\]、A\[k\] 分别就是上文所说的「小数」、「大数」
3.  将 A\[i\] 与 A\[k\] 交换
4.  可以断定这时 \[j,end) 必然是降序，逆置 \[j,end)，使其升序
5.  如果在步骤 1 找不到符合的相邻元素对，说明当前 \[begin,end) 为一个降序顺序，则直接跳到步骤 4

该方法支持数据重复，且在 C++ STL 中被采用。

void nextPermutation(vector<int>& nums) {
        
            int i=0;
            for (i=nums.size()-2; i >= 0; -- i) {
         // 从后往前找到第一个相邻升序对
                if (nums[i] < nums[i+1]) break;
            }
            if (i == -1) reverse(nums.begin(),nums.end()); // 无相邻升序对，必定为非递减序列
            else {
        
                for (int j=nums.size()-1; j >= i+1; -- j) {
         // 从后往前[i+1,end)找第一个大于a[i+1]的值
                    if (nums[i] < nums[j]) {
        
                        swap(nums[i],nums[j]); // 交换二者
                        reverse(nums.begin()+i+1,nums.end()); // 反转[i+1,end)，变成升序
                        break;
                    }
                }
            }
        }

# 求字典序全排列 #

## 递归方法 ##

第一个数分别以后面的数进行交换

#include<iostream>
    #include<algorithm>
    using namespace std;
    //去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换
    bool IsSwap(char *pszStr, int nBegin, int nEnd)
    {
        
    	for (int i = nBegin; i < nEnd; i++)
    		if (pszStr[i] == pszStr[nEnd])
    			return false;
    	return true;
    }
    //需要三个参数，k表示当前的数，m表示数的个数
    void myPerm(char *pszStr, int k, int m)
    {
        
    	if (k == m)
    	{
        
    		//使用了递归，用static可以保存数据
    		static int s_i = 1;
    		cout << "第 " << s_i++ << " 个排列 " << pszStr << endl;
    	}
    	else
    	{
        
    		for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
    		{
        
    			if (IsSwap(pszStr, k, i))   //添加的判断语句，判断是否相等
    			{
        
    				swap(*(pszStr + k), *(pszStr + i));
    				myPerm(pszStr, k + 1, m);
    				swap(*(pszStr + k), *(pszStr + i));
    			}
    		}
    	}
    }
    int main() {
        
    	char str[]  = "123";
    	myPerm(str, 0, strlen(str)-1);
    	return 0;
    }
    /*
    结果：
    第 1 个排列 123
    第 2 个排列 132
    第 3 个排列 213
    第 4 个排列 231
    第 5 个排列 321
    第 6 个排列 312
    */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/01bc22146d744aa1afffc9947d901f0d.png