#include <iostream>
using namespace std;
#include <apstring.h>

#include "apvector.h"

//	FILE: Combinations.cpp
//
//	AUTHOR:	Nii Noi Morton		   			
//	DATE  :	November 4, 2003		  				
//
//  Math 310 Assignment 7F & 8M Bonus Questions. Implementation for two of the algorithms
//  in Chapter 5.6, Applied Combinatorix, 4th Ed.
//  This file contains the C++ implementation for
//  1) An algorithm for Next Subset in Lexicographic Listing of Combinations- implemented
//     in function

void printArray (apvector<int> someArray, int n) {

	for(int i = 0; i < n; i++) {
		cout << someArray[i];
	}

	cout << "\n";
}

apvector<int> readArray (apvector<int> theArray, int r) {
//
	int t;		// the input integer

	for (int i = 0; i < r ; i++) {
		
		// Read in an input number and create a vector representing this number
		cout << "Please type next input ";
		cout << i;
		cout << ": ";
		cin >> t;
		
		theArray[i] = t;
	}

	return theArray;
}

apvector<int> function (apvector<int> my_Array, int n, int r) {
// given an r-subset of myArray, find the lexicographically next r-subset from
// 1, 2, 3, ..., n

		bool notfound = true;
		
		for(int i = r - 1 ; (i >= 0) && notfound; i--) {
			
			if(my_Array[i] < n - r + i + 1) {
				my_Array[i] = my_Array[i] + 1;
				
				for(int h = i + 1; h < r; h++)
				{
					my_Array[h] = my_Array[h-1] + 1;					
				}				
				notfound = false;		
			}		
		}

		return my_Array;	
}

void main() {
	
	int n;		// Size of the set entered by user
	int r;		// size of the subset entered by the user
	int k;		// the number of subsets the user wants to be listed
		
	apvector<int> theArray(100);
	
	// Read in an input number and create a vector representing this number
	cout << "Please type in the n (where n < 100): ";
	cin >> n;
	cout << "\n";
	
	cout << "Please type in the r (where r < n): ";
	cin >> r;
	cout << "\n";
	
	cout << "Please type in the k (the number of subsets to be printed): ";
	cin >> k;
	cout << "\n";
	
	theArray = readArray (theArray, r);
		
	cout << "The current permutation is: ";
	printArray(theArray, r);
	cout << "\n";
	
	for (int i = 0; i < k; i++) {

		// call the function function1 with this vector and its length as input values
		theArray = function (theArray, n, r);
		
		printArray(theArray, r);		
	}

	cout << "\n\n";
}