title: Algorithm to list all pairings of two sets fitting criteria
body: <p><strong>I have 2 finite sets:</strong></p>
  
  <pre><code>Set A: {A, B, C, D, ...}
  Set B: {1, 2, 3, 4, ...}
  </code></pre>
  
  <p>They could be of the <strong>same or different lengths.</strong> I'm trying to pair them up so that <strong>each element in Set A is paired to exactly one element in Set B.</strong></p>
  
  <p>Note: the converse may or may not be true. <strong>An element in Set B could be paired to zero, one, or all of the elements in Set A.</strong> Because of this, this is not a bijection.</p>
  
  <p>I've been trying for hours to come up with an <strong>algorithm to list all possible sets of pairings that fit these rules</strong>. I've tried iteration and recursion but neither seem to give much ground.</p>
  
  <p>I've also looked at <a href="https://stackoverflow.com/questions/12737650/is-there-an-algorithm-to-output-all-possible-combinations-of-two-sets-of-element">this SO Q&amp;A</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.</p>
  
  <p>Any direction would be much appreciated!</p>
  
  <p>P.S. In case anyone accuses me, this is NOT a school assignment. It's for a personal project I'm starting.</p>
  
  <p>Examples of two valid pairings:</p>
  
  <pre><code>1:A
  2:C
  3:B
  4:D
  
  1:A,C
  2:D
  3:
  4:B
  </code></pre>
  
  <p>EDIT: ANSWER! Thank you to @Vincent</p>
  
  <p><strong>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.</strong></p>
  
  <pre><code>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&lt;String&gt; domain = new ArrayList&lt;String&gt;() {
  
              {
                  for (String s : domainArr)
                      add(s);
              }
          };
  
          //Sample codomain
          Integer[] codomainArr = { 1, 2, 3 };
          List&lt;Integer&gt; codomain = new ArrayList&lt;Integer&gt;() {
  
              {
                  for (Integer i : codomainArr)
                      add(i);
              }
          };
  
          map(domain, codomain);
      }
  
      //Each of codomain maps to exactly one on domain, not necessarily the converse
      static &lt;A, B&gt; void map(List&lt;A&gt; domain, List&lt;B&gt; codomain) {
          //This is the list of all combinations
          List&lt;Map&lt;B, List&lt;A&gt;&gt;&gt; listOfAllMaps = new ArrayList&lt;Map&lt;B, List&lt;A&gt;&gt;&gt;();
  
          Map&lt;B, List&lt;A&gt;&gt; map = new HashMap&lt;B, List&lt;A&gt;&gt;();
          listOfAllMaps = map(domain, codomain, map);
  
          int count = 0; //just for fun. count will always go to codomain.size()^domain.size()
          ListIterator&lt;Map&lt;B, List&lt;A&gt;&gt;&gt; listIterator = listOfAllMaps.listIterator();
          while (listIterator.hasNext()) {
              Map&lt;B, List&lt;A&gt;&gt; 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 &lt;A, B&gt; List&lt;Map&lt;B, List&lt;A&gt;&gt;&gt; map(List&lt;A&gt; domain, List&lt;B&gt; codomain, Map&lt;B, List&lt;A&gt;&gt; map) {
          //Base case
          //If every element in the codomain has been mapped, return our map inside of a list
          if (codomain.size() == 0) {
              List&lt;Map&lt;B, List&lt;A&gt;&gt;&gt; finalAnswer = new ArrayList&lt;Map&lt;B, List&lt;A&gt;&gt;&gt;();
              finalAnswer.add(map);
              return finalAnswer;
          }
  
          //Holds our partial answers
          List&lt;Map&lt;B, List&lt;A&gt;&gt;&gt; listOfAllMaps = new ArrayList&lt;Map&lt;B, List&lt;A&gt;&gt;&gt;();
  
          //List of the indices of all subsets of the given domain
          List&lt;List&lt;Integer&gt;&gt; indexSuperList = listAll(domain.size());
  
          //For each subset of the given domain
          for (List&lt;Integer&gt; 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&lt;A&gt; workingDomain = new ArrayList&lt;A&gt;(domain);
              List&lt;B&gt; workingCodomain = new ArrayList&lt;B&gt;(codomain);
              Map&lt;B, List&lt;A&gt;&gt; workingMap = new HashMap&lt;B, List&lt;A&gt;&gt;(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&lt;A&gt;());
              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&lt;List&lt;Integer&gt;&gt; listAll(int N) {
          List&lt;List&lt;Integer&gt;&gt; allLists = new ArrayList&lt;List&lt;Integer&gt;&gt;();
          allLists.add(new ArrayList&lt;Integer&gt;());
          int allMasks = (1 &lt;&lt; N);
          for (int i = 1; i &lt; allMasks; i++) {
              List&lt;Integer&gt; oneList = new ArrayList&lt;Integer&gt;();
              for (int j = 0; j &lt; N; j++)
                  if ((i &amp; (1 &lt;&lt; j)) &gt; 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;
      }
  
  }
  </code></pre>
  
  <p>Prints out:</p>
  
  <pre><code>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=[]}
  </code></pre>