Генерирование таблиц частями с ограничениями и соответствием условию. пошагово

Есть 3 таблицы T1, T2, T3. Нужно сгенерировать всевозможно таблицу UnionT2T3 (объединение информации T2 и T3), чтобы UnionT2T3 удовлетворяла таблице Т1.

Задача о распределении трудозатрат.

О таблицах. Строчки с названиями колонок не будет! ( xxx - этого нет)

T1 - опускаю о ней информацию, в итоге из нее получу сумму о каждой профессии за интервал.

T2 - ограничения

T3 еще есть колонка сколько человек работает, те на дом 2 слесаря и суммарно 34, но это для алгоритма не пригодиться, но я учитываю в Т1 .. (вывод суммы за определённый интервал)

Задача составить все таблицы UnionT2T3 Разбить сумму (За все интервалы) на конкретные интервалы, учитывая ограничения. Вот такой шаблон

Пояснение Сумму 45 на машина-слесарь разбить на три интервала, причем ограничение на машину ( 0, 25, 25). В первый интервал не работали, во второй не больше 25, в третий не больше 25. Если мы напишем комбинацию машина-слесарь 0 25 20, то машина-токарь получит обновлённое ограничение ( 0-0, 25-25, 25-20)= ( 0, 0, 5) и сумму 5, уже однозначно распределит в третий интервал. Проверка с таблицей Т1 состоит в сверке профессии и суммарно часов за определённый интервал. Те интервал1: 20 = рабСлесИнт1Маш + рабСлесИнт1Дом, 31 = рабСлесИнт2Маш + рабСлесИнт2Дом , 20 = рабСлесИнт3Маш + рабСлесИнт3Дом.

Идея реализации кода для эффективной генерации + появился момент, который не продумала (не знаю как реализовать)

// Сразу оговорюсь, что работаю в классе. Через конструктор получаю указатели на таблицы T1, T2, T3. + оттуда есть метод который выдает return значение нужной ячейки. В самом классе я создаю таблицу UnionT2T3, также создаю "копию" T2shape таблицы T2, а точнее колонки с числами, те T2shape выгладит так изначально

T2shape - находятся обновляемые ограничения, в зависимости от того, что уже было распределено.

Алгоритм создания полного варианта UnionT2T3

• Единоразово создаю UnionT2T3, где будут числа - пока пусто, но ячейки уже созданы. (возможно это надо отдельной функцией сделать).
• В T2shape помещаем ограничения, которые можно изменять.
• циклом бежим по профессиям
• таблица готова, выдать. Далее она нужна для другой генерации....

Моя идея по циклу, пишу как я начала делать, но необходима доработка... Об этом позже... "циклом бежим по профессиям"

• запускаю функцию первого заполнения комбинаций по профессии.
• далее идет бесконечный цикл.
• • сначала идет проверка по колонкам интервалов для профессии
• • • если числа из T1 и UnionT2T3 совпали, то счетчик увеличивается
• • • если число в одной из колонок не совпало, то нужно изменить таблицу UnionT2T3 (она не подходит)
• • если все колонки прошли тест, то вход их бесконечного цикла
• далее мы перейдем к другой профессии .

Проблема моей реализации, что если я составлю комбинации по профессиям и они удовлетворят условию из T1. То я пойду генерировать дальше. Но вдруг, если я продолжила изменять комбинации, я смогла бы найти еще вариант подходящий. Этого я не учла и прошу помощи.

Вот пример.

T2shape
0 25 25
53 36 30
20 20 0

Таблицу UnionT2T3 начинаю заполнять с токарей

5 с ограничением (0 25 25) разбиваю на комбинацию 0 5 0
65 с ограничением (53 36 30) разбиваю на комбинацию 53 12 0
Если проведем проверку, то 0+53!=25 (из Т1).

Пытаемся менять комбинации Найдем совокупность удовлетворяющую Т1 (пускай будет первую, смотря с как напишем код)

5: 0 5 0
65: 25 25 15
0+25==25 5+25==30 0+15==15

T2shape
0 25-5 25
53-25 36-25 30-15
20 20 0

Для токарей разбиение закончено.

Но если бы меняли далее, то есть еще вариант

5: 0 4 1
65: 25 26 14
0+25=25 4+26 ==30 1+14==15

T2shape
0 25-4 25-1
53-25 36-26 30-14
20 20 0

Тут всплывают две задачи.

1. Есть функция, которая при заданной сумме, ограничению и текущей комбинации меняет комбинацию на следующую. смотрим next (Функция которая за 1 вызов обновит разбиение суммы на кол-во ячеек с ограничением. с++) Теперь бы сделать функцию, которая делает одно изменение в таблице из комбинаций.

Про функцию, которая делает одно изменение:
Идем с конца.
Перебираю все варианты последней строки 

    Таблица 1          Таблица 2          Таблица 3
    Текст Текст 4 0 0    Текст Текст 4 0 0    Текст Текст 4 0 0
    Текст Текст 3 0 0    Текст Текст 3 0 0    Текст Текст 3 0 0
    Текст Текст 2 0 0    Текст Текст 2 0 0    Текст Текст 2 0 0
    Текст Текст 1 0 0 >  Текст Текст 0 1 0 >  Текст Текст 0 0 1

Далее изменяю предпоследнюю строку и прогоняю все варианты последней строки

    Текст Текст 4 0 0    Текст Текст 4 0 0    Текст Текст 4 0 0
    Текст Текст 3 0 0    Текст Текст 3 0 0    Текст Текст 3 0 0
    Текст Текст 1 1 0 >  Текст Текст 1 1 0 >  Текст Текст 1 1 0
    Текст Текст 1 0 0    Текст Текст 0 1 0    Текст Текст 0 0 1

Еще могу изменить предпоследнюю строку и прогоняю все варианты последней строки

    Текст Текст 4 0 0    Текст Текст 4 0 0     Текст Текст 4 0 0
    Текст Текст 3 0 0    Текст Текст 3 0 0    Текст Текст 3 0 0
    Текст Текст 1 0 1 >  Текст Текст 1 0 1 >  Текст Текст 1 0 1
    Текст Текст 1 0 0    Текст Текст 0 1 0    Текст Текст 0 0 1
и тд. Функцию запустила 9 раз

Наверно нужен признак, что больше перебирать не возможно.

2. Возвращаемся к задаче. Тут я генерирую относительно профессии. Пусть будет верхняя профессия, средняя, нижняя профессия. Зафиксировала верхнюю профессию, относительно того, что в нее записалось - поменялись ограничения T2shape для остальных профессий. С обновленным T2shape иду в среднюю профессию. Нашла удачный вариант, зафиксировала, обновляю T2shape для остальных профессий. Нашла в нижней профессии удачный вариант. Таблица закончена - выдаю таблицу. Далtе нужно при зафиксированном верхе и средине еще попроходить нижнюю профессию - вдруг я найду еще комбинации. Это делать до пока есть возможность (задача 1). Далее я должна забыть про низ и обновить разок в средней до хорошего варианта и если найдено, то низ начинать перебирать с учетом новой T2shape c нуля first. (смотри Функция которая за 1 вызов обновит разбиение суммы на кол-во ячеек с ограничением. с++)

Код

main

#include <QCoreApplication>
#include <QApplication>
#include <QFile>
#include <QVector>
#include <QTextStream>
#include "All.h"

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    All* pAll;
    pAll = new All();
    pAll->testgenerator();
    return a.exec();
}

All.cpp

#include "All.h"

All::All()
{
    pT1= new T1();
    pT2= new T2();
    pT3= new T3();
    pGenerator = new Generator (pT1, pT2, pT3);
}

void All::testgenerator()
{
    pGenerator->variantUnionT2T3();
}

All.h

#ifndef ALL_H
#define ALL_H
#include "t1t2t3.h"
#include "Generator.h"

class All
{
public:
    All();
    void testgenerator();
private:
    T1* pT1;
    T2* pT2;
    T3* pT3;
    Generator* pGenerator;

};

#endif // ALL_H

Generator.cpp

#include "Generator.h"

template<typename It1, typename It2>
bool first(It1 shape_b, It2 board_b, It2 board_e, double sum) {
    It1 q = shape_b;
    for (It2 p = board_b; p != board_e; ++p) {
        double term = std::min(sum, *q);
        *p = term;
        sum -= term;
        ++q;
    }
    return sum == 0;
}

template<typename It1, typename It2>
bool next(It1 shape_b, It2 board_b, It2 board_e) {
    if (board_b == board_e) {
        return false;
    }

    It2 p = board_e - 1;
    It1 q = shape_b + std::distance(board_b, p);

    int sum = 0;
    bool space = false;
    for (; ; ) {
        if (space && *p > 0) {
            --*p;
            return first(q + 1, p + 1, board_e, sum + 1);
        }
        sum += *p;
        if (*p < *q) {
            space = true;
        }
        if (p == board_b) {
            break;
        }
        --p;
        --q;
    }
    return false;
}

// Сократила комм для сайта
// Функция first строит первую комбимнацию board...
// first возвращает истину...
bool first(const QVector<double> &shape, QVector<double> &board, double sum) {
    return first(shape.begin(), board.begin(), board.end(), sum);
}

// Сократила комм для сайта
// next двигается по board...
bool next(const QVector<double> &shape, QVector<double> &board) {
    return next(shape.begin(), board.begin(), board.end());
}

Generator::Generator(T1* plT1, T2* plT2, T3* plT3)
{
    pT1=plT1;
    pT2=plT2;
    pT3=plT3;
}

void Generator::variantUnionT2T3()
{
    // Создание шаблона UnionT2T3
            pUnionT2T3 = new Table();
            QVector<QString> stemp; // времен вектор
            // Идем по строкам T3
            for(int i = 0; i < pT3->getSizeLine(); i++)
            {
                // Копируем три колонки T3
                stemp.push_back(pT3->stab(i,0));
                stemp.push_back(pT3->stab(i,1));
                stemp.push_back(pT3->stab(i,2));
                // Копируем интревалы из T2
                for(int i = 1; i < pT2->getSizeColumn(); i++)
                {
                    stemp.push_back("");
                }
                pUnionT2T3->fillLineTable(stemp);
                stemp.clear();
            }
     // Помещаем в T2shape, ограничения которые можно изменять
            QVector<double> dtemp; // времен вектор
            for (int i=0; i < pT2->getSizeLine(); i++)
            {
                for (int j=1; j < pT2->getSizeColumn(); j++)
                {
                    dtemp.push_back(pT2->dtab(i,j));
                }
                T2shape.push_back(dtemp);
                dtemp.clear();
            }

      // срез кода, пусть тут формир profession. Так мне надо
            for(int i=0; i < pT1->getSizeLine(); i++)
                profession.push_back(pT1->stab(i,0));

      // Идем по професс
            for(int prof = 0; prof < profession.size(); prof++)
            {
                initialFill(prof);
                while(1)
                {
                    int all = 0;
                    // Идем по интервалам
                    for(int inter=3; inter<pUnionT2T3->getSizeColumn(); inter++)
                    {
                        if(checkT1(profession[prof],inter-3)==1)
                            all++;
                        else
                        {
                            all=0;
                            oneChange(prof);
                        }
                    }
                    if(all==(pUnionT2T3->getSizeColumn()-3))
                        break;// выход из while
                }
                // Точка остановки для отладки. Заполнились все строки проф
                int thisPointStop=999999;
            }

    // Точка остановки для отладки. Заполнил pUnionT2T3.
    int thisPointStop2=999999;
}

int Generator::checkT1(QString prof, int inter)
{
    double sumUnionT2T3=0;
    double sumT1=0;
    int answer;

    //  sumUnionT2T3
    // по строчкам UnionT2T3
    for(int i=0; i < pUnionT2T3->getSizeLine(); i++)
    {
        if(pUnionT2T3->stab(i,0)==prof)
            sumUnionT2T3+=pUnionT2T3->dtab(i,inter+3);
    }

    //  sumT1
    // по строчкам T1
    for(int i=0; i < pT1->getSizeLine(); i++)
    {
        if(pT1->stab(i,0)==prof)
            sumT1+=pT1->dtab(i,inter+2);
    }
    if(sumT1==sumUnionT2T3)
        answer=1;
    else
        answer=0;
    return answer;
}

void Generator::oneChange(int prof)
{
    // тут уже не подойдет как я пыталась делать
    // Комбинация - board
    // Заполняем комбинацию board
    // Созаем oldboard
    // Функция next обновила board
    // Заполняем pUnionT2T3
    // Обновляем ограничение
    // Изменение произошло?
    // Нет. Востанавливаем огран, first и тп
}

void Generator::initialFill(int prof)
{
    // Комбинация - board
    QVector<double> board;
    // Сумма - sum
    double sum;

    board=T2shape[0];
    // Бежим по строкам pUnionT2T3
    for(int i = 0; i < pUnionT2T3->getSizeLine(); i++)
    {
        // Если проф совпала, то ищем ограничение
        if (profession[prof]==pUnionT2T3->stab(i,2))
        {
            // Бежим по строкам T2
            for(int i_T2 = 0; i_T2 < pT2->getSizeLine(); i_T2++)
            {
                if(pUnionT2T3->stab(i,0)==pT2->stab(i_T2,0))
                {
                    sum = pT3->dtab(i,3);
                    // Для строки pUnionT2T3 найдены shape, board, sum
                    first(T2shape[i_T2], board, sum);
                        // Комбинация board сформирована

                    // Заполняем в таблицу pUnionT2T3
                        // Бежим по столбцам pUnionT2T3
                        for(int k = 3; k < pUnionT2T3->getSizeColumn(); k++)
                        {
                            pUnionT2T3->setD(i,k,board[k-3]);
                        }

                    // Отнимаем числа у ограничения
                    for (int x = 0; x < T2shape[0].size(); x++)
                    {
                        T2shape[i_T2][x]-=board[x];
                    }
                    break;
                }
            }
        }
    }
}

Generator.h

#ifndef GENERATOR_H
#define GENERATOR_H
#include "t1t2t3.h"

class Generator
{
public:
    Generator(T1* plT1, T2* plT2, T3* plT3);
    // Объединение T2 и T3
    void variantUnionT2T3();
    // Проверка с T1
    int checkT1(QString prof, int inter);
    // 1 изменение по професии
    void oneChange(int prof);
    // Первоначальное заполнение
    void initialFill(int prof);
private:
    // указатели на таблицы
    T1* pT1;
    T2* pT2;
    T3* pT3;
    // UnionT2T3 обединение информации T2 и T3
    Table* pUnionT2T3;
    // Адаптируемные ограничения, можно менять
    QVector<QVector<double>> T2shape;
    // уникальные професии
    QVector<QString> profession;
};

#endif // GENERATOR_H

t123.h

#ifndef T1T2T3_H
#define T1T2T3_H
#include "Table.h"

class T1: public Table
{
public:
    T1();
};

class T2: public Table
{
public:
    T2();
};

class T3: public Table
{
public:
    T3();
};

#endif // T1T2T3_H

t12.cpp

#include "t1t2t3.h"

T1::T1()
{
    forT1();
}

T2::T2()
{
    forT2();
}

T3::T3()
{
    forT3();
}

Table.h

#ifndef TABLE_H
#define TABLE_H
#include <QVector>

class Table
{
public:
    Table();
    void forT1(); // для среза кода, заполнила вручную
    void forT2(); // для среза кода, заполнила вручную
    void forT3(); // для среза кода, заполнила вручную
    double dtab(int, int); // вывод double tab(i,j)
    QString stab(int, int); // вывод QString tab(i,j)
    int getSizeColumn();// Возвращение кол-ва столбцов
    int getSizeLine();// Возвращение кол-ва строк
    void fillLineTable(QVector<QString> line); // заполнить строку для tab
    void setD(int i, int j, double val);// Заполнение double ячейки
    void setS(int i, int j, QString val);// Заполнение QString ячейки
private:
    QVector<QVector<QString>> tab;
};

#endif // TABLE_H

Table.cpp

#include "Table.h"
#include <QFile>
#include <QTextStream>
#include <QApplication>

Table::Table()
{
}

void Table::forT1()
{
    tab = {
        {"столяр","неважно","20","20","20"},
        {"слесарь","неважно", "28", "31", "20"},
        {"токарь","неважно", "25", "30", "15"},
        };
}

void Table::forT2()
{
    tab= {
            {"машина","0","25","25"},
            {"дом", "53", "36", "30"},
            {"станок", "20", "20", "0"},
         };
}

void Table::forT3()
{
    tab = {
        {"машина","неважно","слесарь","45"},
        {"машина","неважно", "токарь","5"},
        {"дом","неважно", "столяр","20"},
        {"дом","неважно", "слесарь","34"},
        {"дом","неважно", "токарь","65"},
        {"станок","неважно", "столяр","40"}
        };
}

double Table::dtab(int i, int j)
{
    return tab[i][j].toDouble();
}

QString Table::stab(int i, int j)
{
    return tab[i][j];
}

int Table::getSizeColumn()
{
    return tab[0].size();
}

int Table::getSizeLine()
{
    return tab.size();
}

void Table::fillLineTable(QVector<QString> line)
{
    tab.push_back(line);
}
void Table::setD(int i, int j, double val)
{
   tab[i][j]=QString::number(val);
}

void Table::setS(int i, int j, QString val)
{
   tab[i][j]=val;
}