#include <iostream>
#include <stdio.h>
#include <cstdlib> //Для паузы.
#include <fstream> //Для файла.

using namespace std; //Будем много пользоваться стандартными именами, поэтому подключаем всё их пространство.

int main() {
	setlocale(LC_ALL, "Russian"); //Подключили русский язык в консоли
	system("color 70"); //Белый фон, чёрный текст.
	system("title Apriori"); //Заголовок для консольного приложения.

	ofstream fout("AprioriResult.txt"); //Связали с файлом, куда будем выводить.
	/*Используем сразу упорядоченную матрицу, где 0 - i-того товара нет, 1 - есть в чеке. Строки = транзакции.
	При необходимости можно реализовать через структуру отдельно таблицу, а сюда передавать ID продуктов.*/
	cout << "***APRIORI***" << endl << "Примечание: Для учебных задач обычно хватает трёх шагов." << endl << "Введите количество транзакций:" << endl;
	int TransCount; //Кол-во транзакций
	cin >> TransCount;
	cout << "Введите количество товаров:" << endl;
	int PrCount; //Кол-во товаров
	cin >> PrCount;
	fout << "Было " << TransCount << " транзакций с " << PrCount << " разными товарами." << endl; //Вывели в файл.
	int T[TransCount][PrCount]; //Матрица наличия
	cout << "Внесите данные о транзакциях, используя 0 для отсутствия товара, 1 для наличия." << endl;
	for (int i = 0; i < TransCount; i++){
		cout << "Введите позиции для чека №" << i + 1 << " :" << endl;
		fout << "Чек №" << i + 1 << ":" << endl;
		for (int j = 0; j < PrCount; j++){ cin >> T[i][j]; fout << T[i][j] << " "; }; //Заполяются "почеково".
		fout << endl;
	};
	int temp = 0; //Временная переменная
	cout << "Введите значение минимальной поддержки:" << endl;
	int minsup;  //мин.поддержка.
	cin >> minsup; //Ввели значение минимальной поддержки.
	fout << "Минимальная поддержка равна " << minsup << "." << endl; //Выписываем в файл значение минимальной поддержки.
	cout << endl;
	/*Первый шаг.*/
	int C1[PrCount]; /*Кандидаты - все одноэлементные.*/
	for (int i = 0; i < PrCount; i++) { C1[i] = i + 1; }; //Заполнили одноэлеметными.
	int sup1[PrCount]; //Для каждого выделим место под поддержку.
	for (int i = 0; i < PrCount; i++){ sup1[i] = 0; }; //Очистили от мусора.
	for (int i = 0; i < PrCount; i++){ //Проверяем по товарам
		for (int j = 0; j < TransCount; j++){ //Для каждого товара каждую строку
			if (T[j][i] == 1) sup1[i]++; // если нашли 1, то поддержка увеличилась
		};
	};
	int num[PrCount]; //сохраним номера столбцов для будущего расчёта.
	for (int i = 0; i < PrCount; i++){ num[i] = 0; }; //Сохраним потом номера всех кандидатов.
	cout << "Поддержка на первом шаге у элементов:" << endl;
	fout << "Поддержка на первом шаге у элементов:" << endl;
	for (int i = 0; i < PrCount; i++){ cout << "{" << C1[i] << "} sup=" << sup1[i] << endl; fout << "{" << C1[i] << "} sup=" << sup1[i] << endl; }; //Выведем мн-ва с k=1 и их поддержку.
	for (int i = 0; i < PrCount; i++){ if (sup1[i] >= minsup) temp++; }; //Подсчитываем количество будущих часто встречающихся мн-в.
	int F1[temp]; //Выделяем память под часто встречающиеся мн-ва размерности k=1.
	cout << "Удовлетворяющих элементов: " << temp << endl;
	fout << "Удовлетворяющих элементов: " << temp << endl;
	if (temp == 0) {
		cout << "Больше часто встречающихся множеств не найдено." << endl;
		cout << "Результаты записаны в файл AprioriResult.txt." << endl;
		fout.close(); //Закрыли файл.
		system("pause");
	}; //Если таких нет, то выводим сообщение и останавливаем программу, закрываем текстовый файл.
	cout << "Эти элементы:" << endl;
	fout << "Эти элементы:" << endl;
	temp = 0; //Сбросим счётчик.
	for (int i = 0; i < PrCount; i++){
		if (sup1[i] >= minsup) { //Найдём эти часто встречающиеся множества.
			F1[temp] = C1[i]; //Если условие (поддержка больше или равна минимальной) выполнено, то заносим в память.
			num[temp] = i; // Сохраняем номер столбца из таблицы для данного элемента.
			cout << " {" << F1[temp] << "}, "; //Выводим на экран.
			fout << " {" << F1[temp] << "}, "; //Выводим в файл.
			temp++;
		} //Увеличиваем счётсчик для часто встречающихся множеств.
	};
	cout << endl;

	/*Второй шаг.*/
	cout << "Перейдём ко второму шагу, кандидаты: ";
	fout << endl << "Кандидаты на втором шаге:";
	int temp2=temp*2;; // Мы будем использовать одномерный массив. Но нам нужны 2-элементные множества.
	//Значит, используем пары соседних ячеек.
	int C2[temp2]; //Выделим память для описанного выше массива кандидатов.
	int sup2[temp]; // Для пар нам понадобится подсчитать поддержку. Для пар, а не элементов пар!
	for (int i = 0; i < 100; i++){ sup2[i] = 0; };
	temp2 = 0; // Временные переменные.
	int temp3 = 0;
	for (int i = 0; i < temp - 1; i++) { //Мы рассматриваем пары различных элементов,
		//поэтому нам не надо смотреть последний элемент массива.
		for (int j = i + 1; j < temp; j++){ //Т.к. пары различных элементов, на второй позиции не смотрим первый элемент.
			if (F1[i] < F1[j]){ //Чтобы не было, например, {2,3} и {3,2}. Нужны различные множества.
				C2[temp2] = F1[i]; //Переводим в первый элемент кандидата часто встречающееся (k-1)-элементное множество.
				C2[temp2 + 1] = F1[j]; //Аналогично поступаем со второй позицией в кандидате.
				cout << endl << " {" << C2[temp2] << "," << C2[temp2 + 1] << "}"; //Выводим получившееся 2-элеметное множество.
				fout << endl << " {" << C2[temp2] << "," << C2[temp2 + 1] << "}";
				for (int z = 0; z < TransCount; z++){ //Сразу подсчитаем поддержку. Проверяем все чеки.
					if (T[z][num[i]] == 1 && T[z][num[j]] == 1){ //Используем запомненные номера столбиков.
						sup2[temp3]++;
					}; // Если в обоих столбиках 1, то увеличиваем поддержку.
				};
				cout << " sup=" << sup2[temp3]; //Выводим поддержку для данного 2-элементного множества.
				fout << " sup=" << sup2[temp3];
				temp2 = temp2 + 2; //Чтобы продолжить работать со следующей парой, т.е. следующими двумя позициями.
				temp3++; //Чтобы считать поддержку для следующей пары.
			}
		}
	}
	if (temp2 == 0){ cout << " не удалось составить множества." << endl; fout << " не удалось составить множества." << endl; };
	temp = 0; //Временная переменная
	for (int i = 0; i <= temp3; i++){ if (sup2[i] >= minsup) temp++; }; //Подсчитываем количество часто встречающихся для k=2.
	cout << endl<<  "Удовлетворяющих элементов: " << temp << endl;
	fout << endl<<  "Удовлетворяющих элементов: " << temp << endl;
	if (temp == 0){
		cout << "Больше часто встречающихся множеств не найдено." << endl;
		cout << "Результаты записаны в файл AprioriResult.txt." << endl;
		fout.close(); //Закрыли файл.
		system("pause");
	}
	else{ //Выводим сообщение,если таковых нет, останавливаем программу и закрываем файл. Иначе продолжаем:
		cout << "Эти элементы:" << endl;
		fout << "Эти элементы:" << endl;
		temp3 = 0;
		int temp4 = 0;
		int F2[temp2]; //Здесь temp2 отлично от прошлой размерности массива, оно получило новое значение
		// при работе с кандидатами. Отводит место под часто встречающиеся пары.
		int num2[temp2 << 1]; // Нам снова придётся запоминать номера столбцов, одна пара - один номер.
		//Для экономии использован побитовый сдвиг.
		for (int i = 0; i < temp2; i = i + 2){ //"Шагаем" через пару элементов, т.к. в С2 они тоже расположены парно.
			if (sup2[temp3] >= minsup) { //Если поддержка пары больше или равна минимальной,
				F2[temp4] = C2[i]; // то сохраняем первую позицию,
				num2[temp4] = int(i/2); // номер столбца для этого элемента,
				F2[temp4 + 1] = C2[i + 1]; // вторую позициюв паре
				num2[temp4 + 1] = int(i/2) + 1; // и номер столбца для второго элемента.
				cout << " {" << F2[temp4] << "," << F2[temp4 + 1] << "}" << endl; //Выводим на экран полученные двухэлементные множества.
				fout << " {" << F2[temp4] << "," << F2[temp4 + 1] << "}" << endl;
				temp4 = temp4 + 2; //Увеличиваем на два, т.к. заполняли парой.
			};
			temp3++; //На один, т.к. у пары одно значение поддержки, а не два.

		};

		/*Третий шаг*/
		cout << "Перейдём к третьему шагу, кандидаты: ";
		fout << "Кандидаты на третьем шаге:" << endl;
		int C3[temp3*3]; // Теперь k=3, т.е. будут рассматриваться тройки, поэтому для отведения памяти
		// количество двуэлементных множеств, которые станут здесь кандидатами, умножили втрое. На самом деле,
		// работать будет в основном количестве случаев, но не всегда, т.к. связано с комбинаторикой.
		int sup3[temp3]; //Этого количества вполне должно хватить для большинства случаев. Мы не оставляем константу,
		// чтобы не использовать избыток памяти. С другой стороны, мы ограничиваем себя в решениях.
		for (int i = 0; i < 100; i++){ sup3[i] = 0; }; // Очищаем от "мусора".
		temp2 = 0;

		/*Отсортируем массив, чтобы исключить повторения во множествах в дальнейшем.*/
		int tmp = 0;
		for (int i = 0; i < temp4 - 1; ++i) {   //Здесь используется обычная сортировка "пузырьком".
			for (int j = 0; j < temp4 - 1; ++j)
			{
				if (C2[j + 1] < C2[j])  //Если элемент меньше соседа, меняем их местами.
				{
					tmp = C2[j + 1];  //Это одна из причин, почему взят одномерный массив - удобство работы.
					C2[j + 1] = C2[j]; // Мы используем самые простые действия и операторы.
					C2[j] = tmp;
				}
			}
		};

		temp3 = 0;
		tmp = 0;
		bool flag = false; //Он понадобится всего лишь один раз, чтобы отделить первый проход.
		for (int i = 0; i < temp4 - 2; i++) {  //Аналогично со вторым шагом. Мы рассматриваем различные тройки,
			for (int j = i + 1; j < temp4 - 1; j++){ // поэтому на первой позиции никогда не будет два последних
				for (int g = i + 2; g < temp4; g++){ //кандидата и т.д. Используем сразу три ячейки и счётчика для них.
					if ((F2[i] < F2[j]) && (F2[j] < F2[g])){ //Будем рассматривать только те тройки, где элементы
						// в порядке возрастания. Чтобы все тройки были различными.
						if ((flag == true) && tmp == F2[i] + F2[j] + F2[g]){ goto rep; }; //Если проход не первый и сумма элементов
						// предыдущей тройки равна сумме элементов текущей, то "прыгаем" на метку.
						//Т.к. у нас идут по возрастанию, то суммы различных троек будут отличаться хотя бы на 1.
						// При учёте суммы нас не интересует положение чисел внутри множеств.
						C3[temp2] = F2[i];  //Сохранили первый элемент тройки, выбрав число из множества
						//из часто встречающихся 2-элементных множеств.
						C3[temp2 + 1] = F2[j]; // Сохранили второй элемент тройки.
						C3[temp2 + 2] = F2[g]; // Аналогично поступили с третьим элементов.
						tmp = F2[i] + F2[j] + F2[g]; //Подсчитали сумму, вес всей тройки.
						cout << endl << " {" << C3[temp2] << "," << C3[temp2 + 1] << "," << C3[temp2 + 2] << "}"; // Вывели полученное
						fout << endl << " {" << C3[temp2] << "," << C3[temp2 + 1] << "," << C3[temp2 + 2] << "}"; //трёхэлементное множество на экран.
						for (int z = 0; z < TransCount; z++){ // Подсчитаем для него поддержку.
							if (T[z][num2[i]] == 1 && T[z][num2[j]] == 1 && T[z][num2[g]] == 1){ //Используя сохранённые номера
								// столбцов, смотрим соответствующие значения в каждом чеке. Если все три 1, то
								sup3[temp3]++; // увеличиваем значение поддержки множества.
							};
						};
						cout << " sup=" << sup3[temp3]; //Вывели окончательно значение поддержки для данной тройки.
						fout << " sup=" << sup3[temp3];
						flag = true; //При первом проходе флаг меняется здесь с false на true.
					rep:		temp2 = temp2 + 3; //Метка. Увеличиваем индекс ячеек, чтобы перейти к следующей тройке
						//(через два элемента от первого в данной тройке).
						temp3++; //Подсчитываем количество троек. Увеличиваем на один.

					}
				}
			}
		}
		if (temp2 == 0){ cout << " не удалось составить множества." << endl; fout << " не удалось составить множества." << endl; };
		temp = 0;
		for (int i = 0; i <= temp3; i++){ //Меньше или равно, т.к. индексы начинались с нуля, а место в массиве - от 1.
			if (sup3[i] >= minsup) temp++;
		}; // Подсчитываем, сколько выделить памяти под часто встречающиеся трёхэлементные мн-ва.
		cout << endl<< "Удовлетворяющих элементов: " << temp << endl;
		fout << endl<<  "Удовлетворяющих элементов: " << temp << endl;
		if (temp == 0){
			cout << "Больше часто встречающихся множеств не найдено." << endl;
			cout << "Результаты записаны в файл AprioriResult.txt." << endl;
			fout.close(); //Закрыли файл.
			system("pause");
		}
		else{ //Сообщение об ошибке и пауза, иначе ищем эти элементы.
			cout << "Эти элементы:" << endl;
			fout << "Эти элементы:" << endl;
			temp3 = 0;
			temp4 = 0;
			temp = temp * 3; //Т.к.это количество троек, т.е. самих ячеек надо в три раза больше.
			int F3[temp]; // Отводим память для самих элементов.
			int num3[temp];  // Отводим память для номеров столбцов для расчётов в будущем, четвёртом шаге.
			for (int i = 0; i < temp; i = i + 3){ //"Шагаем" по три. Мы работаем сразу со всеми позициями в каждом
				// трёхэлементном множестве.
				if (sup2[temp3] >= minsup) { // Если поддержка тройки больше или равна минимальной, то
					F3[temp4] = C3[i];  //Запомнили первый элемент тройки часто встречавшихся.
					num3[temp4] = i; // Номер столбца для этого элемента.
					F3[temp4 + 1] = C3[i + 1]; //Второй элемент
					num3[temp4 + 1] = i + 1; // и его номер,
					F3[temp4 + 2] = C3[i + 2]; // третий элемент,
					num3[temp4 + 2] = i + 2; // номер третьего элемента.
					cout << " {" << F3[temp4] << "," << F3[temp4 + 1] << "," << F3[temp4 + 2] << "}" << endl; //Вывели трёхэлементное множество.
					temp4 = temp4 + 3; //Увеличили индекс, чтобы перейти к следующей часто встречающейся тройке.
				};
				temp3++; //Увеличили номер рассматриваемой тройки. Понадобилось бы для следующего шага.
			};
		};
	};
	cout << "Работа программы закончена." << endl<<endl;
	fout.close(); //Закрыли файл.
}