package utils;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutation {
	
	public static <T> List<List<T>> permutation(Collection<T> list, int n) {
		List<List<T>> res = new ArrayList<>();
		permutation(list, n, new ArrayList<>(), new HashSet<>(), res);
		return res;
	}
	
	public static List<List<Integer>> permutation(int i) {
		return permutation(0, i);
	}
	
	public static List<List<Integer>> permutation(int i, int j) {
		List<Integer> perms = new ArrayList<>();
		for (int ii = i; ii < j; ii++) {
			perms.add(ii);
		}
		return permutation(perms, j - i);
 	}
	
	private static <T> void permutation(Collection<T> all, int n, List<T> current, Set<T> used, List<List<T>> result) {
		if (current.size() == n) {
			result.add(new ArrayList<>(current));
			return;
		}
		for (T elem : all) {
			if (! used.contains(elem)) {
				current.add(elem);
				used.add(elem);
				permutation(all, n, current, used, result);
				current.remove(current.size() - 1);
				used.remove(elem);
			}
		}
	}
	
}