Algorithm to list all pairings of two sets fitting criteria

Question

I have 2 finite sets:

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

They could be of the same or different lengths. I'm trying to pair them up so that each element in Set A is paired to exactly one element in Set B.

Note: the converse may or may not be true. An element in Set B could be paired to zero, one, or all of the elements in Set A. Because of this, this is not a bijection.

I've been trying for hours to come up with an algorithm to list all possible sets of pairings that fit these rules. I've tried iteration and recursion but neither seem to give much ground.

I've also looked at this SO Q&A but that solution doesn't work for me because it does not allow an element in the second set to be paired with multiple in the first.

Any direction would be much appreciated!

P.S. In case anyone accuses me, this is NOT a school assignment. It's for a personal project I'm starting.

Examples of two valid pairings:

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

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

EDIT: ANSWER! Thank you to @Vincent

NOTE: Accidentally reversed the definitions of the domain (Set A) and codomain (Set B) in this. Now, each element of the codomain maps to exactly one element on the domain, but not ncessarily the reverse.

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

}

Prints out:

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

I suggest that you process using recursion on the set A: Enumerate all the pairings that could be done on the first element and combine that with the enumeration of the remainder of the set A and the remainder of the set B.

In the end of the recursion on the set A, you can group the pairs by element in the set B like you did in your question.

Answer 2

Looks like you are looking for all functions from SetA to SetB. Here is a sample Python solution.

from itertools import combinations_with_replacement

SetA = {'A', 'B', 'C', 'D'}
SetB = {1, 2, 3, 4, 5}

res = (list(zip(SetA, comb))
        for comb in combinations_with_replacement(SetB, len(SetA)))

Edit: I mean function in a sense of a collection of tuples.

Answer 3

Isn't there a simpler approach?

In each pairing, each element of A is mapped to one of the elements in B. We therefore need to generate all permutations of |A| things from |B| indexes. There will be |B|^|A| such pairings, where ^ is the power operator and || denotes the size of the set.

Here's some very simple code to illustrate, where we just use Strings to gather the elements of A assigned to an element of B.

public class Pairings
{
    public static void main(String[] args)
    {
        String[] a = { "A", "B", "C", "D" };
        String[] b = { "1", "2", "3" };
        pairs(a, b);
    }

    static void pairs(String[] a, String[] b)
    {
        int asize = a.length;
        int bsize = b.length;
        int[] idx = new int[asize];

        int c = 1;
        String[] pairings = new String[bsize];
        while (true)
        {
            // gather the pairings of a to b
            Arrays.fill(pairings, "");
            for (int i = 0; i < asize; i++)
            {
                pairings[idx[i]] += a[i] + " ";
            }

            System.out.print(c++ + ": ");
            for (int i = 0; i < bsize; i++)
            {
                if (!pairings[i].isEmpty())
                    pairings[i] = pairings[i].substring(0, pairings[i].length() - 1);
                System.out.print(b[i] + "=[" + pairings[i] + "] ");
            }
            System.out.println();

            // generate the next permutation
            int k = idx.length - 1;
            for (; k >= 0; k--)
            {
                idx[k]++;
                if (idx[k] < bsize) break;                  
                idx[k] = 0;
            }

            // if the first index wrapped around then we're done
            if (k < 0) break;               
        }
    }
}

Output:

1: 1=[A B C D] 2=[] 3=[] 
2: 1=[A B C] 2=[D] 3=[] 
3: 1=[A B C] 2=[] 3=[D] 
4: 1=[A B D] 2=[C] 3=[] 
5: 1=[A B] 2=[C D] 3=[] 
6: 1=[A B] 2=[C] 3=[D] 
7: 1=[A B D] 2=[] 3=[C] 
8: 1=[A B] 2=[D] 3=[C] 
9: 1=[A B] 2=[] 3=[C D] 
.
.
.
74: 1=[C] 2=[D] 3=[A B] 
75: 1=[C] 2=[] 3=[A B D] 
76: 1=[D] 2=[C] 3=[A B] 
77: 1=[] 2=[C D] 3=[A B] 
78: 1=[] 2=[C] 3=[A B D] 
79: 1=[D] 2=[] 3=[A B C] 
80: 1=[] 2=[D] 3=[A B C] 
81: 1=[] 2=[] 3=[A B C D]