package nai5;

import java.util.*;

public class OrderedPowerSet<E>{
  private static final int ELEMENT_LIMIT=12;
  private List<E> inputList;
  public int N;
  private Map<Integer, List<LinkedHashSet<E>>> map=new HashMap<>();

  public OrderedPowerSet(List<E> list){
    inputList=list;
    N=list.size();
    if(N>ELEMENT_LIMIT){
      throw new RuntimeException(
              "List with more then "+ELEMENT_LIMIT+" elements is too long...");
    }
  }

  public List<LinkedHashSet<E>> getPermutationsList(int elementCount){
    if(elementCount<1||elementCount>N){
      throw new IndexOutOfBoundsException(
              "Can only generate permutations for a count between 1 to "+N);
    }
    if(map.containsKey(elementCount)){
      return map.get(elementCount);
    }

    ArrayList<LinkedHashSet<E>> list=new ArrayList<>();

    if(elementCount==N){
      list.add(new LinkedHashSet<>(inputList));
    }else{
      if(elementCount==1){
        for(int i=0;i<N;i++){
          LinkedHashSet<E> set=new LinkedHashSet<>();
          set.add(inputList.get(i));
          list.add(set);
        }
      }else{
        list=new ArrayList<>();
        for(int i=0;i<=N-elementCount;i++){
          @SuppressWarnings("unchecked")
          ArrayList<E> subList=(ArrayList<E>)((ArrayList<E>)inputList).clone();
          for(int j=i;j>=0;j--){
            subList.remove(j);
          }
          OrderedPowerSet<E> subPowerSet=new OrderedPowerSet<>(subList);

          List<LinkedHashSet<E>> pList=
                                 subPowerSet.getPermutationsList(elementCount-1);
          for(LinkedHashSet<E> s : pList){
            LinkedHashSet<E> set=new LinkedHashSet<>();
            set.add(inputList.get(i));
            set.addAll(s);
            list.add(set);
          }
        }
      }
    }

    map.put(elementCount, list);

    return map.get(elementCount);
  }
}