一、無(wú)重復(fù)數(shù)字排列

1.1 題目描述

?把 $1～n$ 這 $n$ 個(gè)整數(shù)排成一行后隨機(jī)打亂順序，輸出所有可能的次序。

輸入格式：
一個(gè)整數(shù) $n$。$1\le n\le 9$。
輸出格式：
按照從小到大的順序輸出所有方案，每行 $1$ 個(gè)。
首先，同一行相鄰兩個(gè)數(shù)用一個(gè)空格隔開(kāi)。
其次，對(duì)于兩個(gè)不同的行，對(duì)應(yīng)下標(biāo)的數(shù)一一比較，字典序較小的排在前面。

1.2 用dfs方法

1.2.1 思路分析

?1. 這個(gè)問(wèn)題其實(shí)就是求無(wú)重復(fù)元素的全排列，經(jīng)典的 $dfs$ 題。$dfs$ 最重要的是搜索順序，用什么順序遍歷所有方案。對(duì)于全排列問(wèn)題，以 $n=3$ 為例，可以這樣進(jìn)行搜索：

?假設(shè)有 3 個(gè)空位，從前往后填數(shù)字，每次填一個(gè)位置，填的數(shù)字不能和前面一樣。

?最開(kāi)始的時(shí)候，三個(gè)空位都是空的：__ __ __

?首先填寫(xiě)第一個(gè)空位，第一個(gè)空位可以填 1，填寫(xiě)后為：1 __ __

?填好第一個(gè)空位，填第二個(gè)空位，第二個(gè)空位可以填 2，填寫(xiě)后為：1 2 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 3，填寫(xiě)后為： 1 2 3

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：1 2 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 3 ，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：1 __ __。第二個(gè)空位上除了填過(guò)的 2，還可以填 3。第二個(gè)空位上填寫(xiě) 3，填寫(xiě)后為：1 3 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 2，填寫(xiě)后為： 1 3 2

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：1 3 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 2，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：1 __ __。第二個(gè)空位上除了填過(guò)的 2，3，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：__ __ __。第一個(gè)空位上除了填過(guò)的 1，還可以填 2。第一個(gè)空位上填寫(xiě) 2，填寫(xiě)后為：2 __ __

?填好第一個(gè)空位，填第二個(gè)空位，第二個(gè)空位可以填 1，填寫(xiě)后為：2 1 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 3，填寫(xiě)后為：2 1 3

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：2 1 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 3，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：2 __ __。第二個(gè)空位上除了填過(guò)的 1，還可以填 3。第二個(gè)空位上填寫(xiě) 3，填寫(xiě)后為：2 3 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 1，填寫(xiě)后為：2 3 1

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：2 3 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 1，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：2 __ __。第二個(gè)空位上除了填過(guò)的 1，3，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：__ __ __。第一個(gè)空位上除了填過(guò)的 1，2，還可以填 3。第一個(gè)空位上填寫(xiě) 3，填寫(xiě)后為：3 __ __

?填好第一個(gè)空位，填第二個(gè)空位，第二個(gè)空位可以填 1，填寫(xiě)后為：3 1 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 2，填寫(xiě)后為：3 1 2

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：3 1 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 2，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：3 __ __。第二個(gè)空位上除了填過(guò)的 1，還可以填 2。第二個(gè)空位上填寫(xiě) 2，填寫(xiě)后為：3 2 __

?填好第二個(gè)空位，填第三個(gè)空位，第三個(gè)空位可以填 1，填寫(xiě)后為：3 2 1

?這時(shí)候，空位填完，無(wú)法繼續(xù)填數(shù)，所以這是一種方案，輸出。

?然后往后退一步，退到了狀態(tài)：3 2 __ 。剩余第三個(gè)空位沒(méi)有填數(shù)。第三個(gè)空位上除了填過(guò)的 1，2，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：3 __ __。第二個(gè)空位上除了填過(guò)的 1，2，沒(méi)有其他數(shù)字可以填。

?因此再往后退一步，退到了狀態(tài)：__ __ __。第一個(gè)空位上除了填過(guò)的 1，2，3，沒(méi)有其他數(shù)字可以填。

?此時(shí)深度優(yōu)先搜索結(jié)束，輸出了所有的方案。

輸入樣例：
3
輸出樣例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

時(shí)間復(fù)雜度為 $O(n?n!)$。

1.2.2 代碼編寫(xiě)

?用 $path$ 數(shù)組保存排列，當(dāng)排列的長(zhǎng)度為 $n$ 時(shí)，是一種方案，輸出。
?用 $state$ 數(shù)組表示數(shù)字是否用過(guò)。當(dāng) $state[i]$ 為 $1$ 時(shí)：$i$ 已經(jīng)被用過(guò)，$state[i]$ 為 $0$ 時(shí)，$i$ 沒(méi)有被用過(guò)。
?$dfs(i)$ 表示的含義是：在 $path[i]$ 處填寫(xiě)數(shù)字，然后遞歸的在下一個(gè)位置填寫(xiě)數(shù)字。
?回溯：第 $i$ 個(gè)位置填寫(xiě)某個(gè)數(shù)字的所有情況都遍歷后， 第 $i$ 個(gè)位置填寫(xiě)下一個(gè)數(shù)字。

#include<iostream>
using namespace std;
const int N = 10;
int path[N];  //保存序列
int state[N]; //數(shù)字是否被用過(guò)
int n;
void dfs(int u)
{
    if(u > n)//數(shù)字填完了，輸出
    {
        for(int i = 1; i <= n; i++) //輸出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++) //空位上可以選擇的數(shù)字為:1 ~ n
    {
        if(!state[i])    //如果數(shù)字 i 沒(méi)有被用過(guò)
        {
            path[u] = i; //放入空位
            state[i] = 1;//數(shù)字被用，修改狀態(tài)
            dfs(u + 1);  //填下一個(gè)位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
    return 0;
}

1.3 用交換法

?交換法思想就是定下一個(gè)前綴，然后將后面的數(shù)全排列。

#include<iostream>
using namespace std;
int n;
//int cnt = 0; cnt用來(lái)計(jì)數(shù)的 
void Permutation(int *s,int p) //從數(shù)組s的第p個(gè)位置開(kāi)始全排列
{
    if(p==n)
    {
        for(int i=0;i<n;i++) 
        {
        	cout<<s[i];
	    }
	    cout<<endl;
        //可計(jì)數(shù)有多少種排序cnt++;
    }
    for(int i=p;i<n;i++)
    {
        swap(s[i],s[p]);  //每個(gè)字符都有成為當(dāng)前起始字符的機(jī)會(huì)
        Permutation(s,p+1);
        swap(s[i],s[p]);  //返回初始狀態(tài)，才能保證后面的交換是正確的，回溯
    }
}
int main()
{
	cin>>n;
    int s[n];
    for(int i=0;i<n;i++) 
    {
    	s[i]=i+1;
	}
    Permutation(s,0);
    //cout <<cnt << endl; 可輸出有多少中排序 
    return 0;
}

1.4 STL秒解

1.4.1 所用函數(shù)

?1. next_permutation的功能是生成給定序列的下一個(gè)字典序排列。這個(gè)函數(shù)在C++ STL中，對(duì)于解決排列組合問(wèn)題和迭代遍歷所有可能排列時(shí)非常有用。
?2. prev_permutation的功能是生成給定序列的前一個(gè)字典序排列。這個(gè)函數(shù)在C++ STL中，可以用于迭代遍歷所有可能的排列，與next_permutation相反，它是從大到小的順序生成排列。

1.4.2 代碼編寫(xiě)

#include <iostream>
#include<algorithm> //頭文件
using namespace std;
int main()
{
	int n;
	cin>>n;
    int s[n];
    for(int i=0;i<n;i++) 
    {
    	s[i]=i+1;
	}
    //int cnt = 0;
    do
    {
        for(int i=0;i<n;i++) 
        {
        	cout<<s[i];
	    }
	    cout<<endl;
    }while(next_permutation(s,s+n));//起始位置，左閉右開(kāi)
    
    //cout<<"總共有："<<cnt<<" 種排列"<<endl;
    return 0;
}

二、有重復(fù)數(shù)字排列

2.1 思路分析

?1. 看到這個(gè)題目首先能想到的一點(diǎn)就是：(1) 我們要求元素的所有全排列。(2) 我們要對(duì)求出的全排列去重。

?2. 求全排列用交換遞歸；去重我們可以設(shè)計(jì)一個(gè)函數(shù)來(lái)判斷這個(gè)元素是否前面已經(jīng)用到過(guò)了。

2.2 代碼編寫(xiě)

#include <iostream>
using namespace std;
int count=0;
void swap(char &a,char &b)
{
	char temp;
	temp=a;
	a=b;
	b=temp;
}
int finish(char list[],int k,int i)
{   //第i個(gè)元素是否在前面元素[k...i-1]中出現(xiàn)過(guò)
	if(i>k)
	{
		for(int j=k;j<i;j++)
			if(list[j]==list[i])
				return 0;
	}
	return 1;
}
void perm(char list[],int k,int m)
{
	if(k==m)    //當(dāng)只剩下一個(gè)元素時(shí)則輸出
	{
		count++;
		for(int i=0;i<=m;i++)
			cout<<list[i];
		cout<<endl;
	}
	for(int i=k;i<=m;i++)  //還有多個(gè)元素待排列，遞歸產(chǎn)生排列
	{
		if(finish(list,k,i))
		{
			swap(list[k],list[i]);
			perm(list,k+1,m);
			swap(list[k],list[i]);
		}
	}
}
int main()
{
	int i,n;
	cout<<"請(qǐng)輸入元素個(gè)數(shù): "<<endl;
	cin>>n;
	cout<<"請(qǐng)輸入待排列的元素: "<<endl;
	//getchar();
	char *a=new char[n];
 
	for(i=0;i<n;i++)
		cin>>a[i];
	cout<<"所有不同排列為: "<<endl;
	perm(a,0,n-1);
	cout<<"排列總數(shù)為： "<<count<<endl;
	return 0;
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-739909.html

到了這里，關(guān)于【C++】無(wú)重復(fù)數(shù)字全排列(三種方法)和有重復(fù)數(shù)字全排列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！