python算法设计 - 下一组排列

python算法设计源码：https://github.com/MakerChen66/Python3Algorithm

版权声明：原创不易，本文禁止抄袭、转载，侵权必究！

• • 一、下一组排列
  • 二、源码下载
  • 三、作者Info

我们给定一个全序集，要找到当前结构的下一组排列，如：HIJT->HITJ->HJIT->HJTI……

尽管几乎每一个库里都提供了类似的功能，但若是想要提高算法速率的话，可以看看这个

这个算法本身是非常简单的：

• 从序列的末尾开始，找到递减的最长子序列（如：46975）且将它前面的项表示为一个支点（如：46975）
• 将此支点与找到的递减最长子序列中的次小项进行交换（如：47965）
• 将递减子序列转向（如：47569）

Python算法实现：

def permute(value):
    values = list(value)
    n = len(values)

    # i: 找到递减序列前的那一个支点
    for i in reversed(range(n - 1)):
        if values[i] < values[i + 1]:
            break
    else:
        # 否则逆转列表里的元素
        values[:] = reversed(values[:])
        return values

    # j: 要和i支点交换值的递减序列的次小项
    for j in reversed(range(i, n)):
        if values[i] < values[j]:
            # i支点和递减序列的次小项交换值，并且把交换后的递减序列逆转，也就是把i支点后的元素逆转
            values[i], values[j] = values[j], values[i]
            values[i + 1:] = reversed(values[i + 1:])
            break

    print(values)

permute('HIJT')

输出结果:

python算法设计源码下载：

• GitHub下载链接：传送门
• 原文链接：阅读原文
  
  

作者：小鸿的摸鱼日常，Goal：让编程更有趣！

原创微信公众号：『小鸿星空科技』，专注于算法、爬虫，网站，游戏开发，数据分析、自然语言处理，AI等，期待你的关注，让我们一起成长、一起Coding！

版权说明：本文禁止抄袭、转载 ，侵权必究！