search_dnf

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector <int> read_function(int& N);
vector <vector<int>> build_tab(vector<int>& f, int N);
int count_ones(vector<int>& v);
void sort_tab(vector<vector<int>>& tab);
void print_tab(vector<vector<int>>& tab, int N, int flag);
int compare(vector<int>& a, vector<int>& b);
bool compare_tab(vector<vector<int>>& tab);
vector<vector<bool>> build_matrix(vector<vector<int>>& Nf, vector<vector<int>>& tab);
void print_matrix(vector<vector<bool>>& matrix);
vector<vector<int>> search_dnf (vector<vector<bool>>& matrix, int N);

int main (){
    int N = 4;
    //auto f = read_function(N);
    //vector<int> f = {1,0,1,0,0,1,1,0,1,1,0,1,0,0,1,1};
    //vector<int> f = {0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,1};
//  vector<int> f = {0,1,0,1,1,0,0,1,0,0,1,0,1,1,0,0};
    vector<int> f = {1,0,1,1,1,0,1,1,0,1,0,1,1,1,0,0};
    auto tab = build_tab(f, N);
    sort_tab(tab);
    auto save = tab;
    while ( compare_tab(tab) );
    print_tab(save, N, 0);
    print_tab(tab, N, 1);
    auto matrix = build_matrix(save, tab);
    print_matrix(matrix);

    auto answer = search_dnf(matrix, N);
    cout << endl << "DNF [" << answer.size() << "] >> " << endl;
    for (int i = 0; i < answer.size(); ++i){
        cout << "I" <<answer[i][0]+1;
        for (int j = 1; j < answer[i].size(); ++j)
            cout << " + I" << answer[i][j]+1;
        cout << endl;
    }
}

vector<vector<int>> search_dnf (vector<vector<bool>>& matrix, int N){
    vector<vector<int>> answer;
    int limit = pow(2, matrix.size());
    for (int i = 0; i < limit; ++i){
        int num = i, count = 0;
        vector <int> temp;
        vector <bool> checked;
        for (int j = 0; j < matrix[0].size(); ++j) checked.push_back(false);

        for (int j = 0; j < matrix.size(); ++j){
            temp.push_back(num % 2);
            if ( temp[j] != 0 )
                for (int k = 0; k < matrix[j].size(); ++k){
                    if ( matrix[j][k] && !checked[k] ){
                        checked[k] = true;
                        ++ count;
                    }
                }
            num /= 2;
        }
        if ( count == checked.size() ){
            vector <int> temp2;
            for (int j = 0; j < matrix.size(); ++j)
                if ( temp[j] != 0 )
                    temp2.push_back(j);
            answer.push_back(temp2);
        }
    }
    vector <int> del;
    for (int i = 0; i < answer.size()-1; ++i)
        for (int j = i+1; j < answer.size(); ++j){
            int count = 0;
            for (int k = 0; k < answer[i].size(); k++){
                for (int t = 0; t < answer[j].size(); t++){
                    if ( answer[i][k] == answer[j][t] )
                        ++count;
                }
            }

            if ( count == answer[i].size() ) {
                bool flag = true;
                for (int k = 0; k < del.size(); k++){
                    if ( del[k] == j ) flag = false;
                }
                if ( flag )
                    del.push_back(j);
            }
        }
    vector<int> checked;
    for (int i = 0; i < answer.size(); ++i)
        checked.push_back(true);

    for (int i = 0; i < del.size(); ++i)
        checked[del[i]] = false;

    vector<vector<int>> answer2;
    for (int i = 0; i < answer.size(); i++)
        if ( checked[i] ) answer2.push_back(answer[i]);

    return answer2;
}

vector<vector<bool>> build_matrix(vector<vector<int>>& Nf, vector<vector<int>>& tab){
    vector<vector<bool>> matrix;
    for (int i = 0; i < tab.size(); ++i){
        vector<bool> temp;
        for (int j = 0; j < Nf.size(); ++j){
            bool flag = true;
            for (int k=0; k < tab[i].size(); ++k){
                if ( tab[i][k] != 2 )
                    if ( tab[i][k] != Nf[j][k] ) {
                        flag = false;
                        break;
                    }
            }
            temp.push_back(flag);
        }
        matrix.push_back(temp);
    }
    return matrix;
}

void print_matrix(vector<vector<bool>>& matrix){
    cout << "Matrix >>" << endl;
    for (int i = 0; i < matrix.size(); ++i){
        cout << "   ";
        for (int j = 0; j < matrix[i].size(); ++j)
            if ( matrix[i][j] ) cout << "1 "; else cout << "0 ";
        cout << endl;
    }
}

void print_tab(vector<vector<int>>& tab, int N, int flag){
    string str;
    if ( flag == 0) str = "Carrier"; else str = "Intervals";
    cout << str <<" >> " << endl;
    if ( flag == 0) str = "   P"; else str = "   I";
    for (int i = 0; i < tab.size(); ++i) {
        cout << str << i+1 << " >> ";
        for (int j = N-1; j >= 0; --j){
            if ( tab[i][j] == 2 )
                cout << "* ";
            else
                cout << tab[i][j] << " ";
        }
        cout << endl;
    }
}

int compare(vector<int>& a, vector<int>& b){
    int count = 0, k;
    for (int i = 0; i < a.size(); ++i)
        if ( a[i] != b[i] ) {
            k = i;
            ++count;
        }
    if ( count == 0 ){
        return -2;
    } else if ( count == 1){
        return k;
    } else return -1;
}

bool compare_tab(vector<vector<int>>& tab){
    bool compared = false;
    vector<vector<int>> answer;
    vector<bool> checked;

    for (int i = 0; i < tab.size(); ++i)
        checked.push_back(false);

    for (int i = 0; i < tab.size()-1; ++i)
        for (int j = i+1; j < tab.size(); ++j){
            int k = compare(tab[i],tab[j]);
            if ( k != -1 ) {
                compared = true;
                checked [i] = true;
                checked [j] = true;
                vector<int> temp = tab[i];
                temp[k] = 2;
                bool flag = true;
                for (auto &t : answer)
                    if ( compare(t, temp) == -2 ){
                        flag = false;
                        break;
                    }
                if ( flag )
                    answer.push_back(temp);
            }
        }
    for (int i = 0; i < tab.size(); ++i){
        if ( !checked[i] )
            answer.push_back(tab[i]);
    }
    tab = answer;
    return compared;
}

void sort_tab(vector<vector<int>>& tab) {
    for (int i = 0; i < tab.size()-1; ++i)
        for (int j = i+1; j < tab.size(); ++j)
            if ( count_ones(tab[i]) > count_ones(tab[j])){
                auto temp = tab[i];
                tab[i] = tab[j];
                tab[j] = temp;
            }
}

vector <vector<int>> build_tab(vector<int>& f, int N){
    vector<vector<int>> tab;
    for (int i = 0; i < f.size(); ++i)
        if ( f[i] ){
            int num = i;
            vector<int> temp;
            for (int j = 0; j < N; ++j){
                temp.push_back(num % 2);
                num /= 2;
            }
            tab.push_back(temp);
        }
    return tab;
}

vector <int> read_function(int& N){
    cout << "Enter the number of variables and values of the function: " << endl << "//Example: 3 1 0 1 0 1 0 1 0" << endl;
    cin >> N;
    int x, limit = pow(2, N);
    vector <int> f;
    for (int i = 0; i < limit; ++i){
        cin >> x;
        f.push_back(x);
    }
    return f;
}

int count_ones(vector<int>& v){
    int count = 0;
    for (auto &i : v)
        if ( i == 1 )
            ++count;
    return count;
}