如何实现这样的分组和排列组合？
假定有3个人 有3种职业和姓名
String[] nameArray = {"小王", "小张", "小赵"};String[] occupationArray = {"经商", "学生", "士兵"};
然后有一个Person的对象 里面包含了name 和 occupation
我现在想把所有可能性都列出来 并且分组
因为每个人只能有一个名字和一种职业 而且别人不能重复 我发现这样的双重for循环好像很难实现
List<List<Person>> 如何最终能保存成我想要的结果
想要的结果大概是这样：
[[{"name":"小王","occupation":"经商"},{"name":"小张","occupation":"学生"},{"name":"小赵","occupation":"士兵"}],//这是第一组
[{"name":"小王","occupation":"学生"},{"name":"小张","occupation":"经商"},{"name":"小赵","occupation":"士兵"}],//这是第二组
....
]
如果2组中的姓名和职业是一样的 不管位置 只能算一组 因为位置在这里是要忽略的因素
回答：
public class Test { static class Person {
String name;
String occupation;
}
public static void main(String[] args) {
String[] nameArray = {"小王", "小张", "小赵"};
String[] occupationArray = {"经商", "学生", "士兵"};
assert nameArray.length == occupationArray.length;
List<List<String>> nameLists = permutation(ListUtil.toList(nameArray));
List<List<Person>> personLists = new ArrayList<>();
for (int i = 0; i < nameLists.size(); i++) {
List<Person> personList = new ArrayList<>();
List<String> nameList = nameLists.get(i);
for (int j = 0; j < nameList.size(); j++) {
Person person = new Person();
person.name = nameList.get(j);
person.occupation = occupationArray[j];
personList.add(person);
}
personLists.add(personList);
}
for (List<Person> personList : personLists) {
System.out.println(personList.stream().map(p -> p.name + ":" + p.occupation).collect(Collectors.joining(",")));
}
}
public static List<List<String>> permutation(List<String> list) {
Stream<List<String>> hashSetStream = list.stream().distinct().map((str) -> new ArrayList<>(Collections.singleton(str)));
for (int n = 1; n < list.size(); n++) {
hashSetStream = hashSetStream.flatMap(arrayList -> list.stream()
.filter((temp) -> !arrayList.contains(temp))
.map((v) -> {
List<String> newList = new ArrayList<>(arrayList);
newList.add(v);
return newList;
}));
}
return hashSetStream.collect(Collectors.toList());
}
}
尝试一下该用法。
思路是将 occupation 分别排列组合，再将排练组合的结果与 原始的 name 合并成 person。
回答：
主要是对职业全排列
不含重复项的全排列：全排列
含重复项的全排列：全排列 II
下面假设不含重复职业
方法一：选择法，基于回溯（深搜） / 广搜
最常见的做法
所有职业组成一个集合，每次从中拿走一个放到列表末尾，拿完就得到一个排列，然后回溯，把刚放在列表末尾的职业拿走放回集合中，再拿下一个重复操作即可
使用回溯法模拟该过程，或者使用广搜维护每一层操作的所有状态：
维护集合方法很多，只要保证不重复拿即可，可用 暴力判断 / 标记数组 / 哈希表 / 交换法
不考虑输出顺序的话，推荐交换法，性能最佳，代码最简
交换法+回溯法 参考代码：
import java.util.*;public class Main {
public static void main(String[] args) {
backtrack(Arrays.asList("经商", "学生", "士兵"), 0);
}
private static <T> void backtrack(List<T> list, int first) {
int last = list.size() - 1;
if (first == last) {
System.out.println(list);
return;
}
for (int i = first; i <= last; ++i) {
Collections.swap(list, first, i);
backtrack(list, first + 1);
Collections.swap(list, first, i);
}
}
}
[经商, 学生, 士兵][经商, 士兵, 学生]
[学生, 经商, 士兵]
[学生, 士兵, 经商]
[士兵, 学生, 经商]
[士兵, 经商, 学生]
方法二：放置法，基于回溯（深搜） / 广搜
初始化一个临时数组，开始时全部位置空着，每次把职业放到一个空位置，全部放完就得到了一个排列，然后回溯，移到下一个空位置重复操作即可
一样可用回溯法模拟该过程，或者使用广搜维护每一层操作的所有状态
回溯法 参考代码：
import java.util.*;public class Main {
public static void main(String[] args) {
backtrack(new String[] { "经商", "学生", "士兵" }, 0, new String[3]);
}
private static <T> void backtrack(T[] items, int i, T[] tmp) {
int n = items.length;
if (i == n) {
System.out.println(List.of(tmp));
return;
}
T item = items[i++];
for (int j = 0; j < n; ++j) {
if (tmp[j] != null) continue;
tmp[j] = item;
backtrack(items, i, tmp);
tmp[j] = null;
}
}
}
[经商, 学生, 士兵][经商, 士兵, 学生]
[学生, 经商, 士兵]
[士兵, 经商, 学生]
[学生, 士兵, 经商]
[士兵, 学生, 经商]
方法三：迭代
nextPermutation() 用于获取下一个字典序更大的排列，参考：下一个排列
反复调用即可得到全排列
输出按索引字典序排列的全排列 参考代码：
import java.util.*;import java.util.stream.*;
public class Main {
public static void main(String[] args) {
List<String> list = Arrays.asList("经商", "学生", "士兵");
List<Integer> indices = IntStream.range(0, list.size()).boxed().collect(Collectors.toList());
int count = 1;
for (int i = list.size(); i > 1; count *= i--);
for (;;) {
System.out.println(indices.stream().map(list::get).collect(Collectors.toList()));
if (--count == 0) break;
nextPermutation(indices);
}
}
public static <T extends Comparable<T>> void nextPermutation(List<T> list) {
int n = list.size(), i = n - 1, j;
for (;;) {
j = i--;
if (i < 0) break;
if (list.get(i).compareTo(list.get(j)) < 0) {
int k = n;
while (list.get(i).compareTo(list.get(--k)) >= 0);
Collections.swap(list, i, k);
break;
}
}
Collections.reverse(list.subList(j, n));
}
}
[经商, 学生, 士兵][经商, 士兵, 学生]
[学生, 经商, 士兵]
[学生, 士兵, 经商]
[士兵, 经商, 学生]
[士兵, 学生, 经商]
回答：
要想明白这个问题，其实需要先在数学上弄清楚。
这个问题可以转换为 全排列的问题，其实可以固定人或者职业（那个数量少固定那个），看另外一个有哪些排列可能。比如这里可以是职业数大于人数的。
这样对人数和职业数不同也可以处理了，只是前面先取组合而已。
而排列有很多处理方法，找一个即可。
以3人（甲、乙、丙），4职业为例（A、B、C、D）
比如把人(固定为对应位置)，这里有3个就是 0，1，2 位置（从左到右），
把职业原始数据对应为索引编号0，1，2，3
则从4个职业中取3个来排列有P（4，3）可能(共24)。分别为
0 1 2 -> 甲A 乙B 丙C0 2 1 -> 甲A 乙C 丙B
1 0 2 -> 甲B 乙A 丙C
1 2 0 -> 甲B 乙C 丙A
2 0 1 -> 甲C 乙A 丙B
2 1 0 -> 甲C 乙B 丙A
0 1 3 -> 甲A 乙B 丙D
0 3 1 -> 甲A 乙D 丙B
1 0 3 -> 甲B 乙A 丙D
1 3 0 -> 甲B 乙D 丙A
3 0 1 -> 甲D 乙A 丙B
3 1 0 -> 甲D 乙B 丙A
0 2 3 -> 甲A 乙C 丙D
0 3 2 -> 甲A 乙D 丙C
2 0 3 -> 甲C 乙A 丙D
2 3 0 -> 甲C 乙D 丙A
3 0 2 -> 甲D 乙A 丙C
3 2 0 -> 甲D 乙C 丙A
1 2 3 -> 甲B 乙C 丙D
1 3 2 -> 甲B 乙D 丙C
2 1 3 -> 甲C 乙B 丙D
2 3 1 -> 甲C 乙D 丙B
3 1 2 -> 甲D 乙B 丙C
3 2 1 -> 甲D 乙C 丙B
所以问题降为获取职业数的排列情况。即有N个不重复元素的数组，选M个进行排列的情况。
即求A(N,M),A(N,M)=N!/(N-M)!,A(4,3)=24
以上是 如何实现这样的分组和排列组合？ 的全部内容， 来源链接： utcz.com/p/944685.html
