C++ Performance bricht ein beim Finden von Partitionen

[CyborgBeta]

Moin,

ich möchte eine Funktion schreiben, die aus der Menge 1,...,50 eine n1-elementige Teilmenge bildet, aus der ich bis zu n2 Elemente auswählen kann, wobei jede Summe eindeutig ist, sodass das Ergebnis jeder Partitionssumme (v(1)+...+v(n2)) nur genau einmal vorkommt.

Beispiel: findVec(i, 3, 50) soll aus der Menge 1,...,50 eine i-elementige Teilmenge bilden, aus der ich eindeutig bis zu 3 Elemente wählen kann. So eine Menge könnte zum Beispiel 1 4 13 sein.

Das Problem dabei ist, dass das für höhere i sehr langsam wird. Habt ihr vielleicht eine Idee?

#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;

struct VectorHash
{
    size_t operator()(const vector<int> &v) const
    {
        hash<int> hasher;
        size_t seed = 0;
        for (int i : v)
        {
            seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

void incrementVecp(vector<int> &vecp, int *ip, const int n1, const int n2)
{
    vecp[*ip]++;
    if (vecp[*ip] == n2)
    {
        while (*ip >= 0 && vecp[*ip] == n2)
        {
            vecp[*ip] = 0;
            (*ip)--;
            if (*ip >= 0)
            {
                vecp[*ip]++;
            }
        }
        if (*ip >= 0)
        {
            *ip = n1 - 1;
        }
    }
}

bool isConfictFree(vector<int> &gramm, const int n)
{
    for (int n1 = 1; n1 <= n; n1++)
    {
        for (int n2 = n1; n2 <= n; n2++)
        {
            vector<int> v1(n1, 0);
            vector<int> v2(n2, 0);
            for (int i1 = n1 - 1; i1 >= 0;)
            {
                for (int i2 = n2 - 1; i2 >= 0;)
                {
                    vector<int> v3 = v1;
                    vector<int> v4 = v2;
                    sort(v3.begin(), v3.end());
                    sort(v4.begin(), v4.end());
                    if (v3 != v4)
                    {
                        int sum1 = 0;
                        int sum2 = 0;
                        for (int v : v3)
                        {
                            sum1 += gramm[v];
                        }
                        for (int v : v4)
                        {
                            sum2 += gramm[v];
                        }
                        if (sum1 == sum2)
                        {
                            return false;
                        }
                    }
                    incrementVecp(v2, &i2, n2, gramm.size());
                }
                incrementVecp(v1, &i1, n1, gramm.size());
            }
        }
    }
    return true;
}

void findVec(const int n1, const int n2, const int maxVal)
{
    vector<int> v(n1, 0);
    for (int i = n1 - 1; i >= 0;)
    {
        if (isConfictFree(v, n2))
        {
            for (int j : v)
            {
                cout << j << " ";
            }
            cout << endl;
            return;
        }
        incrementVecp(v, &i, n1, maxVal);
    }
}

int main(int argc, char const *argv[])
{
    for (int i = 1; i <= 5; i++)
    {
        cout << i << endl;
        findVec(i, 3, 50);
        cout << endl;
    }
    return 0;
}

 

[duAffentier]

Wie ist das:

#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;

struct VectorHash
{
    size_t operator()(const vector<int> &v) const
    {
        hash<int> hasher;
        size_t seed = 0;
        for (int i : v)
        {
            seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

void incrementVecp(vector<int> &vecp, int *ip, const int n1, const int n2)
{
    if (*ip >= 0 && vecp[*ip] < n2)
    {
        vecp[*ip]++;
    }
    else
    {
        while (*ip >= 0 && vecp[*ip] == n2)
        {
            vecp[*ip] = 0;
            (*ip)--;
        }
        if (*ip >= 0)
        {
            vecp[*ip]++;
            *ip = n1 - 1;
        }
    }
}

// The recursive function to generate subsets
void generateSubsets(vector<int>& subset, int start, int end, int maxElements, unordered_set<vector<int>, VectorHash>& result)
{
    if (subset.size() <= maxElements)
    {
        // Check if the sum is unique
        int sum = accumulate(subset.begin(), subset.end(), 0);
        vector<int> sumVec(1, sum);
        if (result.find(sumVec) == result.end())
        {
            result.insert(subset);
        }
    }

    // Terminate the recursion when we've added all elements
    if (start == end)
    {
        return;
    }

    // Recurse with the current element added
    subset.push_back(start);
    generateSubsets(subset, start + 1, end, maxElements, result);
    subset.pop_back();

    // Recurse without the current element
    generateSubsets(subset, start + 1, end, maxElements, result);
}

 

[CyborgBeta]

@duAffentier Sieht ganz gut aus. Muss ich aber erst einmal verstehen. Wenn ich das richtig sehe, ist das einfach die rekursive Variante. Aber du prüfst nicht auf alle möglichen "Kombinations"summen, oder?

if (subset.size() <= maxElements) { // Check if the sum is unique int sum = accumulate(subset.begin(), subset.end(), 0); vector<int> sumVec(1, sum); if (result.find(sumVec) == result.end()) { result.insert(subset); } }

Was tut das?

 

[BeBur]

Das wird für Leetcode, codewars oder für einen Wettbewerb sein. Man sollte daher nicht einfach eine Lösung vor die Nase setzen.

 

[CyborgBeta]

@BeBur Das ist eigentlich für mich selber ... Aber ja, bitte keine Nonsens-Antworten geben. Danke.

 

[CyborgBeta]

Ich such(t)e folgende Folge: https://oeis.org/A051912

Nur nicht für "any three ordered terms", sondern für "any ten ordered terms"...

Da das Problem aber, wie ich nun erfahren habe, np-vollständig ist, (und ein spezielles Rucksackproblem ist) bedarf es hier keiner weiteren Antworten mehr. Oder anders: Es kann nicht weiter optimiert werden. (bis auf ein paar Kleinigkeiten, wo es aber nur um ein paar Sekunden geht).