如何实现这样的分组和排列组合？

Question

假定有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组中的姓名和职业是一样的 不管位置 只能算一组 因为位置在这里是要忽略的因素

Answer 1

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。

Answer 2

主要是对职业全排列

不含重复项的全排列：全排列
含重复项的全排列：全排列 II

下面假设不含重复职业

方法一：选择法，基于回溯（深搜） / 广搜

最常见的做法

所有职业组成一个集合，每次从中拿走一个放到列表末尾，拿完就得到一个排列，然后回溯，把刚放在列表末尾的职业拿走放回集合中，再拿下一个重复操作即可
使用回溯法模拟该过程，或者使用广搜维护每一层操作的所有状态：

graph LR
empty[ ] --> 经商
empty --> 学生
empty --> 士兵
经商 --> 经商,学生 --> 经商,学生,士兵
经商 --> 经商,士兵 --> 经商,士兵,学生
学生 --> 学生,经商 --> 学生,经商,士兵
学生 --> 学生,士兵 --> 学生,士兵,经商
士兵 --> 士兵,经商 --> 士兵,经商,学生
士兵 --> 士兵,学生 --> 士兵,学生,经商

维护集合方法很多，只要保证不重复拿即可，可用 暴力判断 / 标记数组 / 哈希表 / 交换法
不考虑输出顺序的话，推荐交换法，性能最佳，代码最简

交换法+回溯法 参考代码：

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));
    }

}

[经商, 学生, 士兵]
[经商, 士兵, 学生]
[学生, 经商, 士兵]
[学生, 士兵, 经商]
[士兵, 经商, 学生]
[士兵, 学生, 经商]

Answer 3

要想明白这个问题，其实需要先在数学上弄清楚。

这个问题可以转换为 全排列的问题，其实可以固定人或者职业（那个数量少固定那个），看另外一个有哪些排列可能。比如这里可以是职业数大于人数的。

这样对人数和职业数不同也可以处理了，只是前面先取组合而已。

而排列有很多处理方法，找一个即可。

以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 丙C
0 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