How do I get all possible matches between two lists?
For example, I have a list that contains some instances of Lecture, each lecture has a certain number of students attending that lecture, and another list that contains some instances of a class, each class has a maximum capacity.
Now I intend to assign each lecture in the lecture list to a classroom in a class, all lectures in a lecture class should have a class, and then create a map to keep this capability. And I want to return all these possible matches as 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 mappings:
{lecture1:classroom1, lecture2:classroom2, lecture3:classroom3} and
{lecture1:classroom1, lecture2:classroom3, lecture3:classroom2} and
{lecture1:classroom2, lecture2:classroom3, lecture3:classroom1}
After that, all possible cards should be stored in the set.
I'm new to programming and haven't learned the algorithm yet, maybe that's why I'm so scared of it, I would appreciate it if someone could help me solve this problem.
source to share
So I got sucked into this 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 a way out
{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)}
source to share
What you seem to be following is something known as a Cartesian product.
See https://en.wikipedia.org/wiki/Cartesian_product
You can do it 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 set objects will contain abstract input maps containing 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}
]
Combination groups
If you really want 3 items in your set, you can do an intermediate collection in the second stream to collect in a data structure of your choice. It is shown below that for the list, as I have already shown, is usedCollectors.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 "object" set will contain a list of abstract input cards containing 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 one functional expression. If you want to add any suggestions or exceptions, you can use filter
or any other higher order function to control the flow.
source to share
The code below will give you all the matches, you can use them however 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 separate maps, for example, for each 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 that you can create a map of maps. Never mind correcting me or adding something. Have a good day!
source to share
The algorithm itself might look something like this, using a nested one 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;
}
source to share
Here's 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;
}
source to share
Here's 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;
}
source to share