排列组合算法总结(含Java实现)
程序员文章站
2022-05-21 23:18:19
...
一. 排列组合
1. 排列
(1)排列:从n个元素中排列m个元素。
(2)全排列:把n个元素全部排列。
2. 组合
组合:从n个元素中选择m个元素(不考虑顺序)。
二.排列相关算法总结
1.全排列
题目一:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路:
1.把字符串分成两部分,一部分是字符串的第一个字符,另一部分是第一个字符以后的所有字符。递归求另一部分字符的排列。
2.拿第一个字符和它后面的字符逐个交换。注:交换完还要换回去
java实现如下:
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if(str == null || str.length() <= 0)
return res;
HashSet<String> set = new HashSet<String>(); //结果去重
dfs(set, str.toCharArray(), 0);
res.addAll(set);
Collections.sort(res);
return res;
}
public void dfs(HashSet<String> set, char [] str, int k){
if(k == str.length){ //得到结果
set.add(new String(str));
return ;
}
for(int i = 0; i < str.length; i ++){
swap(i, k, str);
dfs(set, str, k + 1);
swap(i, k, str); //回溯
}
}
public void swap(int i, int j, char [] str){
if(i != j){
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
}
上一篇: 算法基础:用递归解决排列组合问题
下一篇: 【算法】排列组合问题