//
// Binomial search. To be used to illustrate the search tree and
// to consider nogood recording and how this might be efficiently used
// in a restarting strategy.
//
// NOTE: there may be a simple reduced method that only records
// and uses nogoods of restricted size, i.e. restricted or bounded learning.
//
// NOTE: we might start by having an array of arraylists where tried[i]
// is the set of values tried at this depth, where a call to expand
// clears out tried at that depth. Thefore looking to the left and above we
// might generate nogoods. When expanding we can then reduce recursive calls
// by exploiting those nogoods learned in previous restarts.
//

import java.util.*;

public class Binomial {

    int n;

    Binomial(int n){
	this.n = n;
    }

    void expand(ArrayList<Integer> C,ArrayList<Integer> P){
	System.out.println(C +" "+ P);
	while (!P.isEmpty()){
	    int i = P.get(0);
	    P.remove((Integer) i);
	    ArrayList<Integer> newP = new ArrayList<Integer>();
	    ArrayList<Integer> newC = new ArrayList<Integer>();
	    for (int x : P) newP.add(x);
	    for (int x : C) newC.add(x);
	    newC.add(i);
	    expand(newC,newP);
	}
    }


    public static void main(String[] args){
	Binomial b = new Binomial(Integer.parseInt(args[0]));
	ArrayList<Integer> C = new ArrayList<Integer>();
	ArrayList<Integer> P = new ArrayList<Integer>();
	for (int i=0;i<b.n;i++) P.add(i+1);
	b.expand(C,P);
    }
}