java排列组合（递归算法）_java排列组合算法

一、排列

1、计算公式如下：

2、使用方法，例如在1，2，3，4，5中取3个数排列：

3、全排列
当m=n时，结果为全排列。例如1，2，3，4的全排列如下：
4、代码实现求无重复数组的全排列

	/**
	 * 循环递归获取给定数组元素(无重复)的全排列
	 *
	 * @param oriList 原始数组
	 * @param oriLen 原始数组size
	 * @param arrayCombResult 数组排列结果集，可传null或空Set
	 * @param preList 记录排列参数，可传null或空List
	 * @return 排列结果
	 */
	public static Set<String> getArrange(List oriList, int oriLen, Set<String> arrayCombResult, List preList){
		if (oriList == null){
			return arrayCombResult;
		}
		if (arrayCombResult == null){
			arrayCombResult = new HashSet<>();
		}
		if (preList == null){
			preList = new ArrayList();
		}
		for (int i = 0; i < oriList.size(); i++){
			while(preList.size() > 0 && oriList.size() + preList.size() > oriLen){
				preList.remove(preList.size() - 1);
			}
			List arrList = new ArrayList(oriList);
			preList.add(arrList.get(i));
			arrList.remove(i);
			if (arrList.isEmpty()){
				arrayCombResult.add(getStrFromList(preList));
			}else {
				getArrange(arrList, oriLen, arrayCombResult, preList);
			}
		}
		return arrayCombResult;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

二、组合

1、计算公式如下：

2、使用方法，例如在1，2，3，4，5中取3个数组合：

3、代码实现求无重复数组的所有组合

	/**
	 * 循环递归获取给定数组元素(无重复)的所有组合
	 *
	 * @param oriList 原始数组
	 * @param resultSet 元素组合结果，可传null或空set
	 * @return 组合结果
	 */
	public static Set<String> getCombination(List oriList, Set<String> resultSet) {
		if (oriList == null) {
			return resultSet;
		}
		if (resultSet == null){
			resultSet = new HashSet<>();
		}
		for (int i = 0; i < oriList.size(); i++) {
			List copyList = new ArrayList(oriList);
			resultSet.add(getStrFromList(copyList));
			List removeIList = new ArrayList();
			copyList.remove(i);
			removeIList.addAll(copyList);
			getCombination(removeIList, resultSet);
		}
		return resultSet;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、开发应用

1、场景1：直接输出1，2，3，4的所有组成可能。
①思路：循环递归，直接打印
②代码实现（本地创建名为EffArrange的class文件后，复制粘贴可直接执行）:

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * 数组所有排列
 * 
 * @author ansel
 * @date 2020/5/26 1:08 PM
 */
public class EffArrange {
	public static void main(String[] args) {
		String[] array = new String[] {"1", "2", "3", "4"};
		arrangeAll(Arrays.asList(array), "");
	}
	public static void arrangeAll(List array, String prefix){
		System.out.println(prefix);
		for (int i = 0; i < array.size(); i++) {
			List temp = new LinkedList(array);
			arrangeAll(temp, prefix + temp.remove(i));
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、场景2：列出 ”我“ ”爱“ ”编“ ”码“ 四个字所有的组成可能，并返回。
①思路：先求四个字的所有组合可能，再对每种可能全排列。
②代码实现（本地创建名为Arrange的class文件后，复制粘贴可直接执行）：

import java.util.*;
/**
 * 对给定数组元素(无重复)进行排列
 *
 * @author ansel
 *
 * @date 2020/5/26 1:23 PM
 */
public class Arrange {
	public static void main(String[] args) {
		String[] array = new String[] {"我", "爱", "编", "码"};
		List arrayList = Arrays.asList(array);
		Set<String> resultSet = new HashSet<>();
		getCombination(arrayList, resultSet);
		System.out.println("组合数 = " + resultSet.size());
		System.out.println("所有组合 : " + resultSet);
		Set<String> arrayCombResult = new HashSet<>();
		Iterator<String> iterator = resultSet.iterator();
		while (iterator.hasNext()){
			List arrList = Arrays.asList(iterator.next().split(","));
			getArrange(arrList, arrList.size(), arrayCombResult, null);
		}
		System.out.println("排列数 = " + arrayCombResult.size());
		System.out.println("所有排列 : " + arrayCombResult);
	}
	/**
	 * 循环递归获取给定数组元素(无重复)的全排列
	 *
	 * @param oriList 原始数组
	 * @param oriLen 原始数组size
	 * @param arrayCombResult 数组排列结果集，可传null或空Set
	 * @param preList 记录排列参数，可传null或空List
	 * @return 排列结果
	 */
	public static Set<String> getArrange(List oriList, int oriLen, Set<String> arrayCombResult, List preList){
		if (oriList == null){
			return arrayCombResult;
		}
		if (arrayCombResult == null){
			arrayCombResult = new HashSet<>();
		}
		if (preList == null){
			preList = new ArrayList();
		}
		for (int i = 0; i < oriList.size(); i++){
			while(preList.size() > 0 && oriList.size() + preList.size() > oriLen){
				preList.remove(preList.size() - 1);
			}
			List arrList = new ArrayList(oriList);
			preList.add(arrList.get(i));
			arrList.remove(i);
			if (arrList.isEmpty()){
				arrayCombResult.add(getStrFromList(preList));
			}else {
				getArrange(arrList, oriLen, arrayCombResult, preList);
			}
		}
		return arrayCombResult;
	}
	/**
	 * 循环递归获取给定数组元素(无重复)的所有组合
	 *
	 * @param oriList 原始数组
	 * @param resultSet 元素组合结果，可传null或空set
	 * @return 组合结果
	 */
	public static Set<String> getCombination(List oriList, Set<String> resultSet) {
		if (oriList == null) {
			return resultSet;
		}
		if (resultSet == null){
			resultSet = new HashSet<>();
		}
		for (int i = 0; i < oriList.size(); i++) {
			List copyList = new ArrayList(oriList);
			resultSet.add(getStrFromList(copyList));
			List removeIList = new ArrayList();
			copyList.remove(i);
			removeIList.addAll(copyList);
			getCombination(removeIList, resultSet);
		}
		return resultSet;
	}
	/**
	 * 将数组元素转化为逗号分隔的字符串
	 *
	 * @param oriList 原始数组
	 * @return 字符串
	 */
	public static String getStrFromList(List oriList){
		StringBuffer result = new StringBuffer();
		if (oriList == null){
			return result.toString();
		} else {
			for (int i = 0; i < oriList.size(); i++){
				result.append(oriList.get(i));
				if (i != (oriList.size() - 1)){
					result.append(",");
				}
			}
		}
		return result.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

—— Copyright © 2020 Ansel. All rights reserved.