arrays - 列出两组拟合标准的所有配对的算法

Question

我有 2 个有限集:

Set A: {A, B, C, D, ...}
Set B: {1, 2, 3, 4, ...}

它们可以是相同或不同的长度。我正在尝试将它们配对，以便集合 A 中的每个元素都恰好与集合 B 中的一个元素配对。强>

注意:反之亦然。 集合 B 中的一个元素可以与集合 A 中的零个、一个或所有元素配对。因此，这不是双射。

我已经尝试了几个小时来想出一个算法来列出符合这些规则的所有可能的配对集。我已经尝试过迭代和递归，但似乎都没有太大的进展。

我也看过 this SO Q&A但该解决方案对我不起作用，因为它不允许第二组中的一个元素与第一组中的多个元素配对。

任何方向将不胜感激!

附言万一有人指责我，这不是学校作业。这是我开始的个人项目。

两个有效配对的示例:

1:A
2:C
3:B
4:D

1:A,C
2:D
3:
4:B

编辑:回答!感谢@Vincent

注意:不小心颠倒了域(A 组)和密码域(B 组)的定义。现在，codomain 的每个元素恰好映射到域中的一个元素，但不一定相反。

import java.util.*;

//My third attempt at a solution :)
public class MapStuff3 {

    public static void main(String[] args) {
        //Sample domain
        String[] domainArr = { "A", "B", "C", "D" };
        List<String> domain = new ArrayList<String>() {

            {
                for (String s : domainArr)
                    add(s);
            }
        };

        //Sample codomain
        Integer[] codomainArr = { 1, 2, 3 };
        List<Integer> codomain = new ArrayList<Integer>() {

            {
                for (Integer i : codomainArr)
                    add(i);
            }
        };

        map(domain, codomain);
    }

    //Each of codomain maps to exactly one on domain, not necessarily the converse
    static <A, B> void map(List<A> domain, List<B> codomain) {
        //This is the list of all combinations
        List<Map<B, List<A>>> listOfAllMaps = new ArrayList<Map<B, List<A>>>();

        Map<B, List<A>> map = new HashMap<B, List<A>>();
        listOfAllMaps = map(domain, codomain, map);

        int count = 0; //just for fun. count will always go to codomain.size()^domain.size()
        ListIterator<Map<B, List<A>>> listIterator = listOfAllMaps.listIterator();
        while (listIterator.hasNext()) {
            Map<B, List<A>> oneMap = listIterator.next();

            //count the number of elements in all of the lists to make sure that every element in the domain is paired to something
            int totalSize = 0;
            for (B key : oneMap.keySet())
                totalSize += oneMap.get(key).size();

            //if it is, it's valid
            if (totalSize == domain.size())
                System.out.println(++count + ": " + oneMap);
            else //remove invalid entries
                listIterator.remove();
        }

        //Because we removed invalid entires, listOfAllMaps will now contain the correct answer
    }

    /**
     * Recursive method to list all possible mappings, including ones where not every element in the
     * domain is mapped to, layer by layer
     */
    static <A, B> List<Map<B, List<A>>> map(List<A> domain, List<B> codomain, Map<B, List<A>> map) {
        //Base case
        //If every element in the codomain has been mapped, return our map inside of a list
        if (codomain.size() == 0) {
            List<Map<B, List<A>>> finalAnswer = new ArrayList<Map<B, List<A>>>();
            finalAnswer.add(map);
            return finalAnswer;
        }

        //Holds our partial answers
        List<Map<B, List<A>>> listOfAllMaps = new ArrayList<Map<B, List<A>>>();

        //List of the indices of all subsets of the given domain
        List<List<Integer>> indexSuperList = listAll(domain.size());

        //For each subset of the given domain
        for (List<Integer> indexList : indexSuperList) {
            //Make copies of our parameters so they can be mutated without affecting everything else
            //I always forget if this is necessary in Java, but I'm too tired too look it up right now. Better safe than sorry.
            List<A> workingDomain = new ArrayList<A>(domain);
            List<B> workingCodomain = new ArrayList<B>(codomain);
            Map<B, List<A>> workingMap = new HashMap<B, List<A>>(map);

            //Map all elements in the given subset of the domain to the first element in the given codomain
            //Also remove every element in the domain that has been used
            workingMap.put(workingCodomain.get(0), new ArrayList<A>());
            for (int i : indexList)
                workingMap.get(workingCodomain.get(0)).add(workingDomain.remove(i));

            //Remove the first element in the given codomain
            workingCodomain.remove(0);

            //Add on the next layer
            listOfAllMaps.addAll(map(workingDomain, workingCodomain, workingMap));
        }

        return listOfAllMaps; //This will only happen if the next layer of recursion hit the base case. Just return what we have
    }

    /**
     * Lists the indices corresponding to all subsets of a list of a certain size N, including the
     * empty set
     * Adapted from https://stackoverflow.com/a/7206478/7059012
     */
    static List<List<Integer>> listAll(int N) {
        List<List<Integer>> allLists = new ArrayList<List<Integer>>();
        allLists.add(new ArrayList<Integer>());
        int allMasks = (1 << N);
        for (int i = 1; i < allMasks; i++) {
            List<Integer> oneList = new ArrayList<Integer>();
            for (int j = 0; j < N; j++)
                if ((i & (1 << j)) > 0) //The j-th element is used
                    oneList.add(j);

            //Put in reverse order so that when we're removing them on lines 88-89, removing the first doesn't invalidate the indices of the others
            Collections.sort(oneList, Collections.reverseOrder());
            allLists.add(oneList);
        }
        return allLists;
    }

}

打印出来:

1: {1=[], 2=[], 3=[D, C, B, A]}
2: {1=[], 2=[A], 3=[D, C, B]}
3: {1=[], 2=[B], 3=[D, C, A]}
4: {1=[], 2=[B, A], 3=[D, C]}
5: {1=[], 2=[C], 3=[D, B, A]}
6: {1=[], 2=[C, A], 3=[D, B]}
7: {1=[], 2=[C, B], 3=[D, A]}
8: {1=[], 2=[C, B, A], 3=[D]}
9: {1=[], 2=[D], 3=[C, B, A]}
10: {1=[], 2=[D, A], 3=[C, B]}
11: {1=[], 2=[D, B], 3=[C, A]}
12: {1=[], 2=[D, B, A], 3=[C]}
13: {1=[], 2=[D, C], 3=[B, A]}
14: {1=[], 2=[D, C, A], 3=[B]}
15: {1=[], 2=[D, C, B], 3=[A]}
16: {1=[], 2=[D, C, B, A], 3=[]}
17: {1=[A], 2=[], 3=[D, C, B]}
18: {1=[A], 2=[B], 3=[D, C]}
19: {1=[A], 2=[C], 3=[D, B]}
20: {1=[A], 2=[C, B], 3=[D]}
21: {1=[A], 2=[D], 3=[C, B]}
22: {1=[A], 2=[D, B], 3=[C]}
23: {1=[A], 2=[D, C], 3=[B]}
24: {1=[A], 2=[D, C, B], 3=[]}
25: {1=[B], 2=[], 3=[D, C, A]}
26: {1=[B], 2=[A], 3=[D, C]}
27: {1=[B], 2=[C], 3=[D, A]}
28: {1=[B], 2=[C, A], 3=[D]}
29: {1=[B], 2=[D], 3=[C, A]}
30: {1=[B], 2=[D, A], 3=[C]}
31: {1=[B], 2=[D, C], 3=[A]}
32: {1=[B], 2=[D, C, A], 3=[]}
33: {1=[B, A], 2=[], 3=[D, C]}
34: {1=[B, A], 2=[C], 3=[D]}
35: {1=[B, A], 2=[D], 3=[C]}
36: {1=[B, A], 2=[D, C], 3=[]}
37: {1=[C], 2=[], 3=[D, B, A]}
38: {1=[C], 2=[A], 3=[D, B]}
39: {1=[C], 2=[B], 3=[D, A]}
40: {1=[C], 2=[B, A], 3=[D]}
41: {1=[C], 2=[D], 3=[B, A]}
42: {1=[C], 2=[D, A], 3=[B]}
43: {1=[C], 2=[D, B], 3=[A]}
44: {1=[C], 2=[D, B, A], 3=[]}
45: {1=[C, A], 2=[], 3=[D, B]}
46: {1=[C, A], 2=[B], 3=[D]}
47: {1=[C, A], 2=[D], 3=[B]}
48: {1=[C, A], 2=[D, B], 3=[]}
49: {1=[C, B], 2=[], 3=[D, A]}
50: {1=[C, B], 2=[A], 3=[D]}
51: {1=[C, B], 2=[D], 3=[A]}
52: {1=[C, B], 2=[D, A], 3=[]}
53: {1=[C, B, A], 2=[], 3=[D]}
54: {1=[C, B, A], 2=[D], 3=[]}
55: {1=[D], 2=[], 3=[C, B, A]}
56: {1=[D], 2=[A], 3=[C, B]}
57: {1=[D], 2=[B], 3=[C, A]}
58: {1=[D], 2=[B, A], 3=[C]}
59: {1=[D], 2=[C], 3=[B, A]}
60: {1=[D], 2=[C, A], 3=[B]}
61: {1=[D], 2=[C, B], 3=[A]}
62: {1=[D], 2=[C, B, A], 3=[]}
63: {1=[D, A], 2=[], 3=[C, B]}
64: {1=[D, A], 2=[B], 3=[C]}
65: {1=[D, A], 2=[C], 3=[B]}
66: {1=[D, A], 2=[C, B], 3=[]}
67: {1=[D, B], 2=[], 3=[C, A]}
68: {1=[D, B], 2=[A], 3=[C]}
69: {1=[D, B], 2=[C], 3=[A]}
70: {1=[D, B], 2=[C, A], 3=[]}
71: {1=[D, B, A], 2=[], 3=[C]}
72: {1=[D, B, A], 2=[C], 3=[]}
73: {1=[D, C], 2=[], 3=[B, A]}
74: {1=[D, C], 2=[A], 3=[B]}
75: {1=[D, C], 2=[B], 3=[A]}
76: {1=[D, C], 2=[B, A], 3=[]}
77: {1=[D, C, A], 2=[], 3=[B]}
78: {1=[D, C, A], 2=[B], 3=[]}
79: {1=[D, C, B], 2=[], 3=[A]}
80: {1=[D, C, B], 2=[A], 3=[]}
81: {1=[D, C, B, A], 2=[], 3=[]}

Answer 1

我建议您在集合 A 上使用递归处理:枚举所有可以在第一个元素上完成的配对，并将其与集合 A 的其余部分和集合 B 的其余部分的枚举相结合。

在集合 A 的递归结束时，您可以像在问题中所做的那样按集合 B 中的元素对对进行分组。