如何实现寻找集合上所有双射的Java方法？

需要编写一个方法 public static <T> Set<Function<T,T>> bijectionsFinder(Set<T> d)，要求输入集合d={1,2,3}时，找出所有从d到自身的双射函数，并返回这些函数的集合。

给出的主方法代码如下：

public static void main(String... args) {
    Set<Integer> a_few = Stream.of(1, 2, 3).collect(Collectors.toSet());
    Set<Function<Integer, Integer>> bijections = bijectionsFinder(a_few);
    bijections.forEach(aBijection -> {
       a_few.forEach(n -> System.out.printf("%d --> %d; ", n, aBijection.apply(n)));
       System.out.println();
    });
}

输入{1,2,3}时的预期输出为6种双射（对应集合元素的全排列）：

1 --> 1; 2 --> 2; 3 --> 3; 
1 --> 1; 2 --> 3; 3 --> 2; 
1 --> 2; 2 --> 1; 3 --> 3; 
1 --> 2; 2 --> 3; 3 --> 1; 
1 --> 3; 2 --> 1; 3 --> 2; 
1 --> 3; 2 --> 2; 3 --> 1; 

实现思路 #

集合到自身的双射等价于集合元素的全排列：每个排列对应一个双射函数，将原集合的元素映射到排列后对应位置的元素。实现分为三步：

1. 生成输入集合所有元素的全排列
2. 将每个排列转换为Function<T,T>类型的映射函数
3. 收集所有函数到Set中返回

完整代码实现 #

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class BijectionFinder {

    // 核心方法：找出集合到自身的所有双射
    public static <T> Set<Function<T, T>> bijectionsFinder(Set<T> d) {
        List<T> elementList = new ArrayList<>(d);
        // 生成所有元素的全排列
        List<List<T>> permutations = generateAllPermutations(elementList);
        Set<Function<T, T>> bijectionSet = new HashSet<>();

        // 将每个排列转换为映射函数
        for (List<T> permutation : permutations) {
            Map<T, T> mapping = new HashMap<>();
            for (int i = 0; i < elementList.size(); i++) {
                mapping.put(elementList.get(i), permutation.get(i));
            }
            // 通过方法引用将Map转换为Function
            bijectionSet.add(mapping::get);
        }

        return bijectionSet;
    }

    // 递归生成全排列的工具方法
    private static <T> List<List<T>> generateAllPermutations(List<T> elements) {
        List<List<T>> result = new ArrayList<>();
        if (elements.isEmpty()) {
            result.add(new ArrayList<>());
            return result;
        }
        T firstElement = elements.get(0);
        List<T> restElements = elements.subList(1, elements.size());
        // 递归生成剩余元素的排列，再插入第一个元素到所有可能位置
        for (List<T> perm : generateAllPermutations(restElements)) {
            for (int i = 0; i <= perm.size(); i++) {
                List<T> newPerm = new ArrayList<>(perm);
                newPerm.add(i, firstElement);
                result.add(newPerm);
            }
        }
        return result;
    }

    public static void main(String... args) {
        Set<Integer> a_few = Stream.of(1, 2, 3).collect(Collectors.toSet());
        Set<Function<Integer, Integer>> bijections = bijectionsFinder(a_few);
        bijections.forEach(aBijection -> {
            a_few.forEach(n -> System.out.printf("%d --> %d; ", n, aBijection.apply(n)));
            System.out.println();
        });
    }
}

代码说明 #

• generateAllPermutations：通过递归方式生成所有元素的全排列，每次将第一个元素插入到剩余元素排列的所有可能位置，最终得到所有排列组合。
• bijectionsFinder：将每个排列转换为Map存储映射关系，再通过mapping::get方法引用得到Function实例，确保每个函数都是合法的双射（每个原元素对应唯一目标元素，且覆盖所有目标元素）。
• 运行主方法后，会输出所有6种双射，与预期结果一致。

内容的提问来源于stack exchange，提问作者Saurav Sharma