//Michael Lawrence
//B00152049
//CSCI 2113
//Feb 6 2002
//Method that prints all subsets of size k from a set of size n
//containg values: 1,2,3,4,......,n  in lexicographical order


//=======================================================================

public class Subsets
{
	public static void main(String[] args)
	{
		subsets(15,5);
	}
	
//======================================================================	
		
	public static void subsets(int n, int k)
	{
		final int MAX_COMPARE = 1000000;
        int numSets = 0;
		
		if(k>n)
		{
			System.out.println("No subsets size "+k+" from set size "+n);
		    return;
		}
		
		if(k == 1)
		{
			for(int i = 1; i <= n; i++)
				System.out.println(i);

			System.out.println("Total number of subsets :"+n);
				
			return;	
		}
		
		System.out.println("All subsets of size "+k+" from set size "+n+":");
		   
		int[] set = new int[k+1];

//fills array with 1,2....k at indices 1,2....k
		
		for(int i = 1; i <= k ; i++)
		{
			set[i] = i;
		}		
		
		printSet(set,k);
		numSets++;
				
//main loop, continues until the last subset is reached, namely: n-k+1, n-k+2, n-k+3 ...... n		
		
		for(int x = 0; x<MAX_COMPARE ; x++)  
		{
			
//increments last digit until is equals n
			
			if(set[k] != n)
			{
				set[k] = set[k] + 1;
			
            	printSet(set,k);
            	numSets++;
            }
            
//when set[k] = n, we move backwards down the list, until a difference > 1 is found
//between an element and it's predecessor (set[m-1]).  This element is incremented,
//and the other m-1 to k elements are filled inrementally from set[m-1].

            else		
			{
				int m = k;

//finds violating element

				while(set[m] - set[m-1] == 1)
				{
					if(m-1 == 1)
					{
						//equal to nCk
						System.out.println("Total number of subsets :"+numSets); 
					    return;
					}
				
					m--;   
				}

//increments it				
				set[m-1] = set[m-1] + 1;				
			
				int p = set[m-1];

//fills the rest of the array with incrementing values from set[m-1]			

				while(m <= k)
				{
					p++;
					set[m] = p;
					m++;
				}
                
                printSet(set,k);
                numSets++;				
			}
		}	
	}
	

//============================================================================
	
//method that prints the values in an array of length size, beginning with the
//element at index 1	

	public static void printSet(int[] a, int size)
	{
		for(int i = 1; i<= size ; i++)
		{
			System.out.print(a[i]);
			if(i != size)
				System.out.print(",");
		} 
		
		System.out.println();  
	}

}