[Java twigs] Enumerate combinations

Enumeration of combinations

Such I will write an article because there must be demand for combinations as well as permutations. Within our company, this small code is used for products that combine several financial products to create a portfolio, and then select the one with good properties. The operating principle is almost the same as the above.

Combination.java


	private enum Operation {add, remove};
	private static<T> Set<T> apply(Set<T> src, Operation operation, T item) {
		Set<T> result = new HashSet<T>(src);
		if (Operation.add == operation) result.add(item);
		if (Operation.remove == operation) result.remove(item);
		return result;
	}
	
	private static<T> Set<Set<T>> _combination(Set<T> selected, int depth, Set<T> pool) {
		if (depth == 0) return apply(new HashSet<>(), Operation.add, selected); //Returns the set that only the selected ones have in the element
		Set<Set<T>> result = new HashSet<Set<T>>();
		for (T item : pool) {
			result.addAll(
					_combination(
							apply(selected, Operation.add, item), //Change item to selected
							depth - 1, 
							apply(pool, Operation.remove, item)  //Remove from pool
					)
			);
		}
		return result;
	}
	public static<T> Set<Set<T>> combination(Set<T> src, int k) {return _combination(new HashSet<T>(), k, src);}

How to use

Like this.

Main.java


	public static void main(String[] args) {

		Set<Integer> src = new HashSet<Integer>() {{
				add(0); add(1); add(2); add(3); add(4); add(5);
		}};
		
		System.out.println(combination(src, 2)); //List all the sets obtained by extracting two from the above set
		
	}

Recommended Posts

[Java twigs] Enumerate combinations
Implement math combinations in Java
Enumeration of all combinations Java
Java
Java