GiftDistribution.java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class GiftDistribution {

	public static void main(String args[]) throws IOException {

		// String fileName = "Noel_Amis.txt";
		String fileName = "Noel_Amis_test.txt";
		// String fileName = "Noel_Famille.txt";

		// findAGoodDistribution(fileName);

		int nbIterations = 10000000;
		int nbRepetitions = 3;
		makeBigStatistics(fileName, nbIterations, nbRepetitions);

	}

	public static class Distribution {

		public List<Person> personInOrder;
		public List<Person> personShuffled;
		public boolean isValid;
		public double totalNumberOfSteps;

		private Distribution(List<Person> personInOrder) {
			super();
			this.personInOrder = personInOrder;
		}

		public void generateDistributionAndCheckIt(int methodId) {
			switch (methodId) {
			case 1:
				generateFullDistributionAndCheckIt();
				break;
			case 2:
				pickStepByStep();
				break;
			default:
				break;
			}
		}

		private void pickStepByStep() {
			isValid = true;

			personShuffled = new ArrayList<>(personInOrder);
			Random r = new Random();

			for (int i = 0; i < personInOrder.size(); i++) {
				Person giftReceiver = personShuffled.remove(r.nextInt(personShuffled.size()));
				totalNumberOfSteps++;
				if (personInOrder.get(i).noGiftList.contains(giftReceiver)) {
					isValid = false;
					personInOrder.get(i).isValid = false;
					break;
				}
			}

		}

		private void generateFullDistributionAndCheckIt() {

			isValid = true;

			personShuffled = new ArrayList<>(personInOrder);
			Collections.shuffle(personShuffled);

			for (int i = 0; i < personInOrder.size(); i++) {
				personInOrder.get(i).isValid = true;
				totalNumberOfSteps++;
				if (personInOrder.get(i).noGiftList.contains(personShuffled.get(i))) {
					isValid = false;
					personInOrder.get(i).isValid = false;
					break;
				}
			}
		}

		private Person getPersonByName(String name) {
			Person result = null;

			for (Person person : personInOrder) {
				if (person.name.equals(name)) {
					result = person;
					break;
				}

			}

			return result;
		}

		public String getPickOrder() {
			String result = "";
			for (Person person : personInOrder) {
				result += person + " ";
			}
			return result;
		}

		public void print() {

			if (isValid) {
				err("Distribution, c'est tout bon :");
			} else {
				out("Distribution, c'est raté :");
			}

			int prettyPrint = -getMaxNameLength();
			for (int i = 0; i < personInOrder.size(); i++) {
				String output = String.format("%" + prettyPrint + "s", personInOrder.get(i)) + " offre à " + personShuffled.get(i) + " !";
				if (personInOrder.get(i).isValid) {
					out(output);
				} else {
					err(output);
				}
			}
			out("--------------------------------------------");
		}

		private int getMaxNameLength() {
			int result = 0;

			for (Person person : personInOrder) {
				if (person.name.length() > result) {
					result = person.name.length();
				}
			}

			return result;
		}

		public static Distribution initDistributionFromFile(String fileName) throws IOException {
			return initDistributionFromFile(fileName, false);
		}

		public static Distribution initDistributionFromFile(String fileName, boolean shuffleInitialOrder) throws IOException {

			Distribution result = null;

			File dir = new File(".");
			File fin = new File(dir.getCanonicalPath() + File.separator + fileName);
			BufferedReader br = new BufferedReader(new FileReader(fin));
			String line = null;

			List<Person> personInOrder = new ArrayList<>();

			String[] personNames = br.readLine().split(" ");
			for (String name : personNames) {
				personInOrder.add(new Person(name));
			}

			if (shuffleInitialOrder) {
				Collections.shuffle(personInOrder);
			}

			result = new Distribution(personInOrder);

			while ((line = br.readLine()) != null) {
				String[] noGiftList = line.split(" ");
				for (int i = 1; i < noGiftList.length; i++) {
					result.getPersonByName(noGiftList[0]).noGiftList.add(result.getPersonByName(noGiftList[i]));
				}

			}

			br.close();

			return result;

		}

	}

	public static void makeBigStatistics(String fileName, int nbIterations, int nbRepetitions) throws IOException {

		// Once with method 1
		makeStatistics(fileName, nbIterations, false, 1);
		out("-------------------------------------------------------------------------");

		// Once with method 2 and order from the file
		makeStatistics(fileName, nbIterations, false, 2);
		out("-------------------------------------------------------------------------");

		// Several times with method 2 and random order
		for (int i = 0; i < nbRepetitions; i++) {
			makeStatistics(fileName, nbIterations, true, 2);
			out("-------------------------------------------------------------------------");
		}

	}

	public static void makeStatistics(String fileName, int nbIterations, boolean shuffleInitialOrder, int methodId) throws IOException {

		Distribution distribution = Distribution.initDistributionFromFile(fileName, shuffleInitialOrder);

		int failures = 0;
		int success = 0;
		int iterations = 0;

		out("Starting to run " + nbIterations + " iterations with method " + methodId + ".");

		while (iterations < nbIterations) {
			distribution.generateDistributionAndCheckIt(methodId);
			if (distribution.isValid) {
				success++;
			} else {
				failures++;
			}
			iterations++;
		}

		out("Finished to run " + iterations + " iterations with method " + methodId + ", got " + success + " success and " + failures + " failures.");
		if (methodId == 2) {
			out("Picking order used was: " + distribution.getPickOrder());
		}

		out("Average number of steps to check a distribution: " + String.format("%.2f", distribution.totalNumberOfSteps / (double) iterations));

		out("Overall sucess ratio: " + String.format("%.2f", 100 * success / (double) iterations));

	}

	public static void findAGoodDistribution(String fileName) throws IOException {

		Distribution distribution = Distribution.initDistributionFromFile(fileName);

		int failures = -1;

		while (!distribution.isValid) {
			distribution.generateDistributionAndCheckIt(1);
			failures++;
		}

		out("Nombre d'échecs avant de trouver : " + failures);
		distribution.print();
	}

	public static void out(String s) {
		System.out.println(s);
	}

	public static void err(String s) {
		System.err.println(s);
	}

	public static class Person {

		public String name;
		public List<Person> noGiftList;
		public boolean isValid;

		public Person(String name) {
			super();
			this.name = name;
			noGiftList = new ArrayList<>();
			noGiftList.add(this);
			isValid = true;
		}

		@Override
		public String toString() {
			return name;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((name == null) ? 0 : name.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Person other = (Person) obj;
			if (name == null) {
				if (other.name != null)
					return false;
			} else if (!name.equals(other.name))
				return false;
			return true;
		}

	}

}

Noel_Amis.txt

Alex Christophe Sylvie Maryline Loic Aurélie Matt
Christophe Sylvie
Sylvie Christophe
Maryline Loic
Loic Maryline
Aurélie Matt
Matt Aurélie