集合元素的排列與組合

最近因?yàn)樗惴荚嚕恢本褪怯锌臻e了刷刷題。 刷的題多了，也就發(fā)現(xiàn)很多基礎(chǔ)算法在一些較復(fù)雜的題中都有應(yīng)用，比如這篇文章中將要提到的排列和組合。

排列

排列，一般地，從m個(gè)不同元素中取出n（n≤m）個(gè)元素，按照一定的順序排成一列，叫做從m個(gè)元素中取出n個(gè)元素的一個(gè)排列(permutation)。

組合

組合，一般地，從m個(gè)不同的元素中，任取n（n≤m）個(gè)元素為一組，叫作從m個(gè)不同元素中取出n個(gè)元素的一個(gè)組合。

區(qū)別

以上兩個(gè)概念在高中數(shù)學(xué)中就學(xué)習(xí)，此處就不過(guò)多的闡述。 唯一強(qiáng)調(diào)一下二者的差異，排列是有序的，組合是無(wú)序的

代碼實(shí)現(xiàn)樣例

import?java.util.ArrayList;
import?java.util.Collection;
import?java.util.HashSet;

/**
?*?排列與組合的基本算法
?*/
public?class?ArrangeAndCombination?{

????private?static?int?m,?n,?COUNT;

????/**
?????*?測(cè)試入口
?????*/
????public?static?void?main(String[]?args)?{
????????m?=?10;
????????n?=?3;

????????//?從10個(gè)元素中取三個(gè)元素有多少種取法？
????????COUNT?=?0;
????????nCm(1,?new?HashSet<>());
????????System.out.println("===?組合?===");
????????System.out.println(COUNT);

????????//?從10個(gè)元素中取三個(gè)并排序有多少種情況？
????????COUNT?=?0;
????????nAm(new?ArrayList<>());
????????System.out.println("===?排列?===");
????????System.out.println(COUNT);
????}

????/**
?????*?組合算法
?????*?@param?start?元素選擇的起始位置
?????*?@param?selected?已選中的元素
?????*/
????private?static?void?nCm(int?start,?Set<Integer>?selected)?{
????????if?(selected.size()?==?n)?{?//?已選中的數(shù)量滿足要求，打印結(jié)果并退出函數(shù)
????????????printResult(selected);
????????????return;
????????}
????????//?已選中的數(shù)量不足，則繼續(xù)選擇元素
????????for?(int?i?=?1;?i?<=?m;?i++)?{
????????????selected.add(i);?//?選擇當(dāng)前元素
????????????nCm(i?+?1,?selected);?//?下一個(gè)元素的選擇從當(dāng)前元素的下一個(gè)開(kāi)始
????????????selected.remove(i);?//?移除當(dāng)前元素
????????}
????}

????/**
?????*?排列算法
?????*?@param?selected?已選中的元素
?????*/
????private?static?void?nAm(List<Integer>?selected)?{
????????if?(selected.size()?==?n)?{?//?已選中的數(shù)量滿足要求，打印結(jié)果并退出函數(shù)
????????????printResult(selected);
????????????return;
????????}
????????//?已選中的數(shù)量不足，則繼續(xù)選擇元素
????????for?(int?i?=?1;?i?<=?m;?i++)?{
????????????if?(!selected.contains(i))?{?//?已選中的元素不能再次選擇
????????????????selected.add(i);?//?選中當(dāng)前元素
????????????????nAm(selected);?//?選擇下一個(gè)元素
????????????????selected.remove((Object)?i);?//?移除當(dāng)前元素。注意List#remove(Object)才是移除元素的函數(shù)，變量i要強(qiáng)轉(zhuǎn)
????????????}
????????}
????}

????/**
?????*?打印結(jié)果并計(jì)數(shù)
?????*?@param?selected?已選中的元素
?????*/
????private?static?void?printResult(Collection<Integer>?selected)?{
????????StringBuilder?sb?=?new?StringBuilder();
????????selected.forEach(x?->?sb.append(",").append(x));
????????System.out.println(sb.substring(1));?//?移除第一個(gè),號(hào)
????????COUNT++;
????}
}

原文：https://www.jeremysong.cn/cn/arrange-and-combination/

歡迎關(guān)注我的公眾號(hào)“須彌零一”，更多技術(shù)文章第一時(shí)間推送。