public class SocketProbability {

	public static int MAX_SOCKETS = 5; // 5 to max socket
	public static int DOMAIN = 10; // 10 different sockets
	public static double SOCKET_PROBABILITY = 0.1; // 1/10 chance for one specific socket

	public static void main(String[] args) {

		System.out.print("       ");
		for (int i = 1; i <= MAX_SOCKETS; i++) {
			System.out.print(i + "        ");
		}
		System.out.println();
		for (int i = 0; i < 50; i++) {
			System.out.print("-");
		}
		System.out.println();
		for (int i = 30; i <= 120; i = i + 5) {
			System.out.print("    " + i + "     ");
			for (int j = 1; j <= 4; j++) {
				System.out.print(String.format("%.3f", socketProbability(i, j)) + "    ");
			}
			System.out.println();
		}

	}

	public static double socketProbability(int copies, int slots) {
		return 1 - inclusionFormula(copies, slots);
	}

	private static double inclusionFormula(int copies, int slots) {
		double probability = 0;
		for (int i = 0; i < slots; i++) {
			probability += unionSize(MAX_SOCKETS, copies) / Math.pow(DOMAIN, copies);
		}
		// probability now: P({Y0 = 0}) + P({Y0 = 1}) + P({Y0 = 2}) + P({Y0 = 3}) + P({Y0 = 4}) + P({Y1 = 0}) + ... + P({Yi = 4})
		// now subtract intersection sizes
		int prefix = 1;
		for (int i = 0; i < slots * MAX_SOCKETS; i++) {
			prefix = (int) Math.pow(-1, i);
			probability = probability + (prefix * probabilityOfIntersectionsSum(i + 1, copies, slots));
		}
		return probability;
	}

	private static double probabilityOfIntersectionsSum(int intersectionCount, int copies, int slots) {
		// base lists
		List<Map<String, Integer>> Yis = new ArrayList<Map<String, Integer>>();
		for (int i = 0; i < slots; i++) {
			for (int j = 0; j < MAX_SOCKETS; j++) {
				Map<String, Integer> randomVariable = new HashMap<String, Integer>();
				randomVariable.put("Y", i);
				randomVariable.put("x", j);

				Yis.add(randomVariable);
			}
		}

		// create sublists based on intersectionCount
		List<List<Map<String, Integer>>> sublists = new ArrayList<List<Map<String, Integer>>>();
		permutation(Yis, sublists, intersectionCount, new ArrayList<Map<String, Integer>>(), 0);

		double intersectionProbabilitySum = 0; // P({Ai1 n ... n Aik}) for 0 <= i1 < ... < ik <= n
		for (int i = 0; i < sublists.size(); i++) {
			if (sublists.get(i).size() <= 1) {
				return 0;
			}

			intersectionProbabilitySum += intersectionProbability(copies, sublists.get(i));
		}

		return intersectionProbabilitySum;
	}

	private static double intersectionProbability(int copies, List<Map<String, Integer>> list) {
		// check first if intersection over same random variable with different realization => intersection is empty
		Set<Integer> is = new HashSet<Integer>();
		int reservedDomains = list.size();
		int reservedDimensions = 0;
		for (int i = 0; i < list.size(); i++) {
			if (is.contains(list.get(i).get("Y"))) {
				// intersection over same random variable is empty set
				return 0;
			} else {
				reservedDimensions += list.get(i).get("x");
				is.add(list.get(i).get("Y"));
			}
		}

		// fixed positions for fixed results
		double fixedDistributedPossibilities = 1;
		int temp = reservedDimensions;
		for (int i = 0; i < list.size(); i++) {
			if (temp >= 2) {
				fixedDistributedPossibilities = fixedDistributedPossibilities * coefficient(temp, list.get(i).get("x"));
				temp -= list.get(i).get("x");
			}
		}

		return (fixedDistributedPossibilities * coefficient(copies, reservedDimensions) * Math.pow(DOMAIN - reservedDomains, copies - reservedDimensions)) / Math.pow(DOMAIN, copies);
	}

	// cardinality possibilities for P({X < x}) <=> P({X = 0} u {X = 1} u ... u {X = x - 1})
	public static double unionSize(int x, int dimensions) {
		double possibilities = 0;
		for (int i = 0; i < x; i++) {
			possibilities += coefficient(dimensions, i) * Math.pow(DOMAIN - 1, dimensions - i);
		}
		return possibilities;
	}

	public static double binomialProbability(int copies, int socket_ups) {
		double prob = 0;
		double result = 0;
		for (int i = socket_ups; i < copies; i++) {
			result = binomial(copies, i);
			prob += result;
		}
		return prob;
	}

	public static double binomial(int copies, int socket_ups) {
		return coefficient(copies, socket_ups) * Math.pow(SOCKET_PROBABILITY, socket_ups)
				* Math.pow((1 - SOCKET_PROBABILITY), copies - socket_ups);
	}

	public static double coefficient(double n, double k) {
		if (k == 0) {
			return 1;
		} else if (k > n || k < 0 || n < 0) {
			return 0;
		} else {
			double denominator = facculty(n, n - k + 1);
			double counter = facculty(k, 1);

			return denominator / counter;
		}
	}

	public static double facculty(double start, double end) {
		if (start > end) {
			return start * facculty(start - 1, end);
		} else {
			return end;
		}
	}

	public static void permutation(List<Map<String, Integer>> originalList, List<List<Map<String, Integer>>> subLists, int sublistSize, List<Map<String, Integer>> currentSubList, int startIndex) {
		if (sublistSize == 0) {
			subLists.add(currentSubList);
		} else {
			sublistSize--;
			for (int i = startIndex; i < originalList.size(); i++) {
				List<Map<String, Integer>> newSubList = new ArrayList<Map<String, Integer>>(currentSubList);
				newSubList.add(originalList.get(i));
				permutation(originalList, subLists, sublistSize, newSubList, i + 1);
			}
		}
	}

	public static void toString(List<List<Map<String, Integer>>> inputList) {
		System.out.println(inputList.size());
		System.out.print("(");
		for (int i = 0; i < inputList.size(); i++) {
			System.out.print("(");
			for (int j = 0; j < inputList.get(i).size(); j++) {
				System.out.print("{Y" + inputList.get(i).get(j).get("Y"));
				System.out.print(" = " + inputList.get(i).get(j).get("x") + "}");
			}
			if (i == inputList.size() - 1) {
				System.out.print(")");
			} else {
				System.out.print("), ");
			}
		}
		System.out.println(")");
	}



}