How to get all the possible matches of two lists?

Question

For example, I have a list which contains some Lecture instances, each lecture has a certain number of students attending this lecture and another list which contains some Classroom instances, each classroom has a maximum capacity.

Now I intend to assign each lecture in lecture list with a classroom in classroom list, all lectures in lecture class should have a classroom, then create a map to store this possibility. And I want to return all these possible matches in the form of a set. For example:

Classroom List: [Classroom1(50),Classroom2(70),Classroom3(80)]
Lecture list:   [Lecture1(50), Lecture2(70), Lecture3(50)]

Then we have 3 possible maps, which are:

{lecture1:classroom1, lecture2:classroom2, lecture3:classroom3} and
{lecture1:classroom1, lecture2:classroom3, lecture3:classroom2} and
{lecture1:classroom2, lecture2:classroom3, lecture3:classroom1}

After that, all possible maps should be stored in a set.

I am new to programming and has not learned algorithm yet, maybe that's why I'm so struggled on this, I'd be grateful if someone could help me solve this problem.

Answer 1

What you seem to be after is something known as the cartesian product.

See https://en.wikipedia.org/wiki/Cartesian_product

You can do this with Java 8 streams

All permutations

// Just substitute the types and values for Lecture and Classroom instances
// I'm not going to do this for you
final List<String> first = Arrays.asList("foo","bar","baz");
final List<String> second = Arrays.asList("spam","ham","eggs");

final Set<Map.Entry<String,String>> objects = 
    first
      .stream()
      .flatMap(f -> 
         second
           .stream()
           .map(s -> new AbstractMap.SimpleEntry<>(f, s)))
      .collect(Collectors.toSet());

Your 'objects' set is going to contain Abstract entry maps which hold your combinations.

Set[
  Map{foo : spam}
  Map{foo : ham}
  Map{foo : eggs}
  Map{bar : spam}
  Map{bar : ham}
  Map{bar : eggs}
  Map{baz : spam}
  Map{baz : ham}
  Map{baz : eggs}
]

Groups of combinations

If you actually want 3 items in your set, you can do an intermediate collect on the second stream to collect into a data structure of your choice. Below shows that for a list, as I've already shown use of Collectors.toSet()

final Set<List<AbstractMap.SimpleEntry<String,String>>> objects = 
    first
      .stream()
      .map(f -> 
         second
           .stream()
           .map(s -> new AbstractMap.SimpleEntry<>(f, s))
           .collect(Collectors.toList()))
      .collect(Collectors.toSet());

Your 'objects' set is going to contain a list of Abstract entry maps which hold your combinations.

Set[
  List(
    Map{foo : spam}, Map{foo : ham}, Map{foo : eggs}
  ),
  List(
    Map{bar : spam}, Map{bar : ham}, Map{bar : eggs}
  ),
  List(
    Map{baz : spam}, Map{baz : ham}, Map{baz : eggs}
  )
]

This illustrates a simple cartesian product algorithm using Java 8 in a single functional statement. Should you wish to add any clauses or exclusions, you can use filter or any of the other higher order functions to manipulate the stream.

Answer 2

Here is an example with sorted data collections:

public Set<Map<Lecture, ClassRoom>> allocateRooms(List<Lecture> lectures, List<ClassRoom> classRooms){

    List<ClassRoom> sortedClassRooms = classRooms
        .stream().sorted(Comparator.comparingInt(a -> a.getId())).collect(Collectors.toList());

    List<Lecture> sortedLectures = lectures
        .stream().sorted(Comparator.comparingInt(a -> a.getId())).collect(Collectors.toList());

    Set<Map<Lecture, ClassRoom>> returnSet = new LinkedHashSet<>();

    for(Lecture l: sortedLectures){
      for (ClassRoom c: sortedClassRooms){
        Map<Lecture, ClassRoom> n = new HashMap<>();
        n.put(l,c);

      }
    }
     return returnSet;
  }

Answer 3

So i got sucked in to this one and wrote a working solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

class ClassMatcher {

        //The set of all possible matchings.
    static ArrayList<ArrayList<Pair>> set = new ArrayList<ArrayList<Pair>>(); 
        // The current matching being built
    static ArrayList<Pair> cur = new ArrayList<Pair>();

    public static void main(String[] args) {

        Lecture[] l = { new Lecture(50, 1), new Lecture(70, 2), new Lecture(50, 3)};
        ArrayList<Classroom> c = new ArrayList<>(Arrays.asList(
            new Classroom(50, 1), new Classroom(70, 2),
            new Classroom(100, 3)));

        for (int i = 0; i < l.length; i++) {
                    //Fill with dummy values
            cur.add(new Pair(new Classroom(-1, -1), new Lecture(-1, -1)));
        }

        // Sort the arrays to save work in rec()
        Arrays.sort(l);
                //Sort classrooms in descending order
        Collections.sort(c, new Comparator<Classroom>() {
            @Override
            public int compare(Classroom o1, Classroom o2) {
                return o1.compareTo(o2) * -1;
            }
        });

        recursive(l, c, 0);

        // Print all the sets
        for (int i = 0; i < set.size(); i++) {
            System.out.print("{");
            for (int j = 0; j < set.get(i).size(); j++) {
                System.out.print("Lecture " + set.get(i).get(j).l + ": "
                    + "Classroom " + set.get(i).get(j).c);
                if (j < set.get(i).size() - 1) {
                    System.out.print(", ");
                } else {
                    System.out.print("}");
                }
            }
            System.out.println();
        }

    }

    public static void recursive(Lecture[] lectureList,
            ArrayList<Classroom> classroomList, int curLecture) {

        for (int i = 0; i < classroomList.size(); i++) {
            // if the classroom is smaller than the lecture we cna stop as the
            // lists are sorted so all other lectures will be to big for the
            // current classroom
            if (lectureList[curLecture].size > classroomList.get(i).size) {
                return;
            }

            //Match the current classroom to the current lecture and add to the working matching
            cur.set(curLecture, new Pair(classroomList.get(i), lectureList[curLecture]));

                //If there are more lectures to do then remove the used classroom and recursively call.
            if (curLecture < lectureList.length - 1) {
                Classroom tmp = classroomList.remove(i);
                recursive(lectureList, classroomList, curLecture + 1);
                classroomList.add(i, tmp);
            } 
                // If no Lectures left then add this matching to the set of all matchings. 
            else {
                ArrayList<Pair> copy = (ArrayList<Pair>) cur.clone();
                set.add(copy);
            }
        }

    }

}

class Classroom implements Comparable<Classroom> {

    int size;
    int number;

    public Classroom(int s, int n) {
        size = s;
        number = n;
    }

    @Override
    public int compareTo(Classroom o) {

        return Integer.compare(this.size, o.size);
    }

    public String toString() {
        return number + " (" + size + ")";
    }
}

class Lecture implements Comparable<Lecture> {

    int size;
    int number;

    public Lecture(int s, int n) {
        size = s;
        number = n;
    }

    @Override
    public int compareTo(Lecture o) {

        return Integer.compare(this.size, o.size);
    }

    public String toString() {
        return number + " (" + size + ")";
    }
}

class Pair {

    Classroom c;
    Lecture l;

    public Pair(Classroom c, Lecture l) {
        this.c = c;
        this.l = l;
    }
}

This gives the output

{Lecture 1 (50): Classroom 3 (100), Lecture 3 (50): Classroom 1 (50), Lecture 2 (70): Classroom 2 (70)}
{Lecture 1 (50): Classroom 2 (70), Lecture 3 (50): Classroom 1 (50), Lecture 2 (70): Classroom 3 (100)}
{Lecture 1 (50): Classroom 1 (50), Lecture 3 (50): Classroom 3 (100), Lecture 2 (70): Classroom 2 (70)}
{Lecture 1 (50): Classroom 1 (50), Lecture 3 (50): Classroom 2 (70), Lecture 2 (70): Classroom 3 (100)}

Answer 4

Here is an answer using Maps instead of arrays:

  public Set<Map<Lecture, ClassRoom>> allocateRooms(List<Lecture> lectures, List<ClassRoom> classRooms){

        Set<Map<Lecture, ClassRoom>> returnSet = new LinkedHashSet<>();

        for(Lecture l: lectures){
          for (ClassRoom c: classRooms){
            Map<Lecture, ClassRoom> n = new HashMap<>();
            n.put(l,c);

          }
        }
         return returnSet;
      }

Answer 5

The algorithm in itself might look something like this using an nested for each loop:

 public Set<Object[]> allocateRooms(List<Lecture> lectures, List<ClassRoom> classRooms){

    Set<Object[]> returnSet = new LinkedHashSet<>();

    for(Lecture l: lectures){
      for (ClassRoom c: classRooms){
        Object[] n = new Object[2];
        n[0] = c;
        n[1] = l;
        returnSet.add(n);
      }
    }
     return returnSet;
  }

Answer 6

Code below will give you all the matches, you can use them like whatever you want

HasMap<Integer, Integer> match = new HashMap<Integer, Integer>();

for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
        if(classroom[i] >= lecture[j]) {
            match.add(lecture[j], classroom[i]);
        }
    }
}

if you want seperate maps like for every classroom or lecture you can try this(example for classrooms)

HashMap<Integer, Integer> classroom1 = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> classroom2 = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> classroom3 = new HashMap<Integer, Integer>();

for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
        if(i == 0) {
            if(classroom[i] >= lecture[j]) {
                classroom1.add(lecture[j], classroom[i]);
            }
        }

        if(i == 1) {
            if(classroom[i] >= lecture[j]) {
                classroom2.add(lecture[j], classroom[i]);
            }
        }

        if(i == 2) {
            if(classroom[i] >= lecture[j]) {
                classroom3.add(lecture[j], classroom[i]);
            }
        }
    }
}

After this you can create map of maps. Don't mind about correcting me or adding something. Have a good day!