随笔 - 6, 文章 - 0, 评论 - 24, 引用 - 0
数据加载中……

Permutation—全排列

Permutation—全排列

l  简介

一个全排列是从一个有限集中选取元素,组成一个有序的序列,并且所有的元素出现且仅出现一次。

l  全排列的计数

n  当集合中元素互异时,显然全排列总共有n!个。

n  现在考虑集合中存在重复元素的情况:

1.     我们首先看一个简单的例子。

2.        设例子中的全排列数为P,那么我们将这P个排列中重复的元素1看成互异的,假设标记为11’,那么对于每种排列都能生成P(2) = 2!个惟一的新排列,而这些新排列恰好构成了3个互异元素的全排列,因此P = P(3) ÷P(2) = 3

3.        假设n个元素的多重集合中有m个互异的元素,各元素出现的次数分别为a1, a2, … , am,且满足(a1 + a2 + … + am) = n那么这个集合形成的全排列个数为

4.        m = n时,上式的结果即为n!

l  生成全排列

n  递推生成:每次输出当前序列的下个全排列,直到生成所有全排列。

1.     按字典序生成:生成输入序列按字典序的下个全排列。

l  寻找从序列A末尾开始的最长非增连续子列S。保存子列S之前的一个元素为a,在上图中,S = { 6, 5, 1 }a = 4

l  容易看出S是其元素的字典序最大全排列,如图中的{ 6, 5, 1 },因此无法通过在S内部交换元素得到A的下个字典序全排列,因此只需找出a + S,即序列{ 4, 6, 5, 1 }中的下个全排列。从序列末尾开始,寻找第一个大于a的元素b,如图中的5,交换ab。这样我们更新了S之前的一个元素,只要将S变为其元素的字典序最小全排列即可得到A的下个字典序全排列;

l  翻转S,由于S非增的(交换ab后还是如此),那么翻转后自然变成非减序列,即其元素的字典序最小全排列

l  以上算法即C++std::next_permutation函数的实现。

2.     无序生成:生成输入序列的下个全排列,各全排列间并不遵循特定的顺序。

未完,待续……

posted on 2009-03-30 20:56 yuyang7 阅读(2370) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理