全排列 订阅
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。公式:全排列数f(n)=n!(定义0!=1) 展开全文
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。公式:全排列数f(n)=n!(定义0!=1)
信息
外文名
Full Permutation
分    类
数学
中文名
全排列
解    释
组合数学术语
全排列简介
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。公式:全排列数f(n)=n!(定义0!=1),如1,2,3三个元素的全排列为:1,2,31,3,22,1,32,3,13,1,23,2,1共3*2*1=6种。
收起全文
精华内容
下载资源
问答
  • 全排列

    千次阅读 多人点赞 2019-09-17 11:54:35
    所谓全排列,就是打印出序列中所有可能的排列。例如输入序列123,则打印出能排列出来的所有序列123、132、213、231、312和321。 一、模板 C++的algorithm库里面有一个函数next_permutation(start,end)。作用就是求...


    前言

    所谓全排列,就是打印出序列中所有可能的排列。例如输入序列123,则打印出能排列出来的所有序列123、132、213、231、312和321。

    一、模板

    C++的algorithm库里面有一个函数next_permutation(start,end)。作用就是求一个排序的下一个排列,可以遍历全排列。注意如果不结束会一直循环,结果出现相同的排列。与之完全相反的函数还有prev_permutation(start,end),就是求一个排序的上一个排列的函数。

    对于next_permutation函数,其函数原型为:

    include <algorithm>

    bool next_permutation(iterator start, iterator end)
    // 当前序列不存在下一个排列时,函数返回false,否则返回true。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int n;	// n表示序列中数的个数
    int a[10005];
    int main() 
    {
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    	do
    	{
    		for (int i = 0; i < n; i++)  // 打印
    			cout << a[i] << " ";
    		cout << endl;
    	}while (next_permutation(a, a + n));
    	return 0;
    }
    

    需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。


    二、非模板

    2.1 非递归实现全排列

    通过交换来得到下个全排列,交换的前提是交换左边的数要小于交换右边的数。

    先从右往左找到左边小于相邻右边的数的位置k,再从右往左找到大于该数的数(可能会有多个),然后交换这两个数,最后要让k位置后的数排列成升序。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int m, n, k;  // m表示取几次全排列,n表示序列个数,k表示当前选取到第几个数
    int a[10005];
    
    void permutation()
    {
    	for (k = n - 1; k >= 1; k--)  // 找到最后可增加的位,即定位 
    	{
    		if (a[k] < a[k + 1])
    			break;
    	}
    	for (int i = n; i > k; i--)  // 找到最小可增加的数字 
    	{
    		if (a[i] > a[k]) 
    		{
    			swap(a[i], a[k]);  // 交换
    			break;
    		}
    	}
    	sort(a + k + 1, a + n + 1);  // 交换后让后面的序列升序
    }
    
    int main()
    {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++)
    		cin >> a[i];
    	while (m--)
    	{
    		permutation();	// 求下次排列
    		for (int i = 1; i <= n; i++)  // 打印
    			cout << a[i] << " ";
    		cout << endl;
    	}
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,717
精华内容 10,286
关键字:

全排列