目錄

一、前言

①全排列

②組合

題目描述

二、解題思路

①確定所用演算法

三、深搜的最終代碼

①進行全排列

最終實作①

②進行組合

最終實作③

兩個深搜的總結

四、位運算組合演算法

①水話

②思路產生

位運算組合的完整代碼

③最終實作

④位運算內的細節講解

五、子集的位運算實作

①水話

②思路產生

位運算子集的完整代碼

③最終實作

新年祝語以及愿景（2022年）

一、前言

今天是元旦節，首先祝大家元旦節快樂鴨！組合以及全排列相信大家在高中的時候就有所耳聞了，那么在程式設計中呢，經常會遇到組合與全排列的相關問題，首先先簡單的介紹一下組合和全排列的相關概念，

①全排列

如果老師讓編號為1，2，3的三個人進行排隊，試問這三個人排隊的順序是怎么樣的？大家關注到，對于這三個人來說，因為每個人都是不同的，因此1在前，2在后和1在后，2在前就是兩種不同的順序，在這題里面，也就是說有：123，132，213，231，312，321六種不同的順序，而這6個便是大家所熟悉的公式A33=6（種），

②組合

那如果是組合呢，如果老師讓你從編號為1，2，3的三個人里面任意選擇兩個人進行pk，請問一共可以進行多少輪不一樣的1v1比賽呢？大家肯定會知道那不就是：12，13，23各自進行一輪，一共有三輪嘛，這里的三輪，便是C32=3得出的結果，至此我們發現了全排列和組合的區別就在于兩者是否在選擇上分先后順序，也就是說12和21是算一個結果還是算兩個結果？

題目描述

有一個陣列a，請你從螢屏中輸入兩個整型n，m（n>=m）,并輸入任意n個數字到a陣列里面，最后按照下面兩種方式輸出相應的所有可能（沒有順序上的要求），

①在n個數字里面選擇m個進行全排列的所有可能，

②在n個數字里面選擇m個進行組合的所有可能，

二、解題思路

①確定所用演算法

熟悉排列組合演算法的同學在本處會很自然的想到利用深度優先搜索的演算法，也就是大名鼎鼎的DFS，但是其實在計算組合的可能性的時候，還可以利用到位運算的方法，后續會提到，

②深搜的模板

void dfs(int x)
{
    if(......)   //終止條件
    {
        操作1；
        操作2；
        ......;
        return;   //回傳上一層，否則會進行很多重復步驟甚至無法走出遞回，
    }
    else
    {
        操作1；
        操作2；
        vis【】=1；   //代表某位置被訪問，
        dfs（x+1）；
        vis【】=0；   //回溯操作，便于產生更多的可能性，
    }
}

以上是深搜的簡單模板，其實主要利用的是回溯的思想，其中的操作需要根據題目來進行，其實這樣看下來，是不是覺得會很簡單呢？其實不然，在深搜里需要注意很多終止條件的使用，以及操作的可行性還有的就是及時的記錄下答案和答案的坐標噢，以后會通過相關的題目進行此處的注意，

三、深搜的最終代碼

①進行全排列

#include<bits/stdc++.h>
using namespace std;
int a[100005],vis[100005],ans[100005];  //a代輸入的數字存盤,vis代表訪問陣列，ans記錄訪問的答案
int n,m;  //n代表輸入陣列的總長度，m代表選取多少個數字進行排列
 
//進行全排列的深搜
void dfs_qpl(int x)  //x代表搜索到的一個寬度
{
 	 if(x>m)
	  {
	  	for(int i=1;i<=m;i++)
	  	{
		 cout<<ans[i]<<" ";
		  }
		  cout<<endl;
		  return;
	  }
	  for(int i=1;i<=n;i++)
	  {
	  	if(!vis[i])
	  	{
		    vis[i]=1;
	  		ans[x]=a[i];
		    dfs_qpl(x+1);
			vis[i]=0; 
		  }
	  }	
} 

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dfs_qpl(1);
	return 0;
}

最終實作①

②進行組合

#include<bits/stdc++.h>
using namespace std;
int a[100005],vis[100005],ans[100005];  //a代輸入的數字存盤,vis代表訪問陣列，ans記錄訪問的答案
int pos[100005];    //邊搜索邊記錄下已經搜索過的位置 
int n,m;  //n代表輸入陣列的總長度，m代表選取多少個數字進行排列
 
//進行全排列的深搜
void dfs_qpl(int x)  //x代表搜索到的一個寬度
{
 	 if(x>m)
	  {
	  	for(int i=1;i<=m;i++)
	  	{
		 cout<<ans[i]<<" ";
		  }
		  cout<<endl;
		  return;
	  }
	  for(int i=1;i<=n;i++)
	  {
	  	if(!vis[i]&&i>pos[x-1])  //代表循壞到的下標要比搜索的前一個大 
	  	{
	  		pos[x]=i;
		    vis[i]=1;
	  		ans[x]=a[i];
		    dfs_qpl(x+1);
			vis[i]=0; 
		  }
	  }	
} 

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dfs_qpl(1);  //從下標為1的地方開始搜索 
	return 0;
}

最終實作③

兩個深搜的總結

大家可以在實踐的時候，或者觀看此篇博客的時候認真地對比一下兩個代碼之間的差別，大家可以發現，其實只是很細微上的差別，但是卻導致了兩個代碼在執行上的不同，這也就是搜索上需要我們進行各種操作的基本功，然后大家一定要多練習幾遍噢，這個其實已經相當于模板類的題目了，下面，想要就組合展開進一步的位運算優化，這個優化的思想也是通過洛谷官網自己出的一本新手程式書上學到的哦，那本書真的挺不錯的，所以在這里就進行一個廣告啦！

四、位運算組合演算法

①水話

只能說位運算其實一直是一個程式設計上優化各種時間復雜度的良藥了，因為很多人包括蒟蒻在內的同學們，對二進制利用或者了解的不夠多，因此在使用起來會感覺到乏力，因此就從這一刻開始吧，希望同學們還有自己能夠在遇到位運算相關的題目的時候，能夠多多積累這樣類似的演算法，至于一些位運算的操作，大家可以關注一些神犇寫的博客，在利用位運算的時候一定要關注題目的資料大小，畢竟int只能存32位的數嘛！

②思路產生

還是以1，5，8為例子，這里存在了三個數字，如果我們利用1代表“有”，0代表“無”，那么也就是說，若1，5，8均存在，我們便利用111代表全集，而如果要在里面找兩個進行組合，如圖所示，便有110，101，011三種可能，而這三種可能所代表的數比111小，也就是說如果我們利用一個回圈從0到111（這里均是二進制的意思）進行搜索，那么我們一定會搜到這三種可能，然后再利用其他變數記錄1出現的次數，如果出現了兩次，我們就把那一次回圈所記錄下來的結果輸出就可以了，下面大家先看一下代碼！

位運算組合的完整代碼

#include<bits/stdc++.h>
using namespace std;
int a[100005],ans[100005]; 
int n,m;  //n代表輸入陣列的總長度，m代表選取多少個數字進行排列
 
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int U=(1<<n)-1;  //U代表全集
	int k=0; //k記錄是否滿足輸出條件m
	int p=1; //用p為1下標便于記錄下答案
	for(int i=0;i<=U;i++)  //從0一直列舉到全集 
	{
		for(int j=0;j<=n;j++)
		{
			if((1<<j)&i)   //代表這個數字是“有”
			{
				k++;
				ans[p++]=a[j];
			 } 
		}
		if(k==m)
		{
			for(int s=1;s<=p-1;s++)
			cout<<ans[s]<<" ";
			cout<<endl;
			k=0;
			p=1;   //k和p同時進行復原，便于下一個答案的查找， 
		}
		k=0;   //外層回圈也別忘了重置k和p 
		p=1;   //k和p同時進行復原，便于下一個答案的查找， 
	 } 
}

③最終實作

④位運算內的細節講解

1.全集U的來歷：因為158是三個數，那么我們讓1左移三位以后會從0001變成1000，然后我們再進行減1的操作便可以得到0111（也就是111）的全集我們想要的結果，

2.if進行篩選的操作（if((1<<j)&i)），這一句話是什么意思呢，讓一個j從0到n進行循壞，不斷的讓1左移j位，其實就相當于產生了001，010，100三個可能之后在&U，就是可以知道，在循壞到i的時候，哪一個位置上是1（也就是“有”），例如在回圈到110的時候，我們便可以讓if里面進行兩次的操作，最后的k=2，就滿足輸出的條件了，

3.k，p的重置，兩個變數的重置也是很關鍵的，如果沒有及時的重置，我們便不會得到更多的可能性，當然在STL庫里面對于查找一個i中有多少個1是有相對應的函式的，但是為了讓大家了解這個程序，在這里就不多加贅述了，感興趣的讀者可以閱讀洛谷上的那本書進行相關的學習！

五、子集的位運算實作

①水話

其實看到此處并好好理解了上面演算法的實作的讀者，相信已經發現了位運算可能會在子集上有妙用，因為子集也是經常考的演算法題目，如果我們把題目變成，請輸出a陣列里面包含的所有子集，相信讀者能夠利用位運算的思想很好的解決，而且后續會有相關的題目利用到這樣的思想，盡情期待哦！

②思路產生

因為全集是111，那么在0-111的程序中，1的數量和位置都是不固定的，但是我們驚奇的發現，在回圈的程序中永遠不會出現一個重復的二進制，這是很顯然的，因為每個數的二進制是不同的，而子集其實就是在查找從n個數選0-n的組合，所以很顯然少了很多的約束條件，也就是我們在回圈中，不斷的輸入“有”的數就好了！

位運算子集的完整代碼

#include<bits/stdc++.h>
using namespace std;
int a[100005]; 
int n,m;  //n代表輸入陣列的總長度，m代表選取多少個數字進行排列
 
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int U=(1<<n)-1;  //U代表全集
	for(int i=0;i<=U;i++)  //從0一直列舉到全集 
	{
		for(int j=0;j<=n;j++)
		{
			if((1<<j)&i)   //代表這個數字是“有”
			{
				cout<<a[j]<<" ";
			 } 
		}
		cout<<endl;
	 } 
}

③最終實作

至于這里的158下面為什么會多一行呢？因為一個集合的子集包含空集呢！

新年祝語以及愿景（2022年）

新的2022年，雖然感覺并沒有跨年的氣氛了，但是確實在頭一天寫這篇博客的時候充滿了斗志，而且本蒟蒻認為此篇也能夠順利幫助在剛接觸相關演算法的讀者們順利度過這一段迷惑期，因為自己也是這么過來的！我堅持了下來，并且能夠坐在電腦之前寫著以前我壓根就不會寫的題目和演算法，雖然自己現在的水平還是很低很低，但是我覺得自己很充實，新的一年里，我希望自己能夠忘掉2021年的不愉快，忘記很多情感上的傷痛，然后因為自己是計算機的學生，當然希望自己不要掉太多的頭發，然后希望新的一年能夠接觸到更多的演算法和資料結構，自己能夠變得越來越強，讓一些可能開始覺得我不行的那一些人，讓他們刮目相看，然后希望今年交大的校賽能夠取得好的成績，順利的以一個合格的身份進入到校ACM隊里面，為我們的學校取得更多的榮譽，希望自己身邊的人都健健康康，開開心心每一天，希望今年生日的時候能夠親手把禮物送給和我同一天生日的學姐手上去，向她表示這么多年來的感謝，希望跟她成為好朋友，而她的存在也必將作為我的動力，繼續讓我朝著一個更好的方向邁進，希望新的一年能夠結識到更多一路同行的兄弟們，在2021年的尾聲，遇到了很多很多很好的人，雖然有的人來了又離開，但是還是非常感謝這一份遇見，因為遇見，也許我們也成為了更好的我們，最后當然就是希望自己能夠不忘初心，繼續堅持學演算法和資料結構，繼續堅持寫博客，繼續提升自己，繼續開開心心地過好2022年的每一天，繼續在開心中get到更多更多的新技能，也祝愿所有看到此篇文章的人新年快樂，天天開心！并且表示本蒟蒻由衷的感謝嘻嘻！最后：再見2021年，我來了2022年！