odtwarzanie zbioru na podstawie innego zbioru

0

Przepisałem swoje rozwiązanie z Javy na C++. Poniżej kod:

// Solver.h
#pragma once

#include<vector>
#include<list>
#include<algorithm>

class Solver
{
    static bool checkLength(int n, int len)
    {
        if (n*(n + 1) == 2 * len) return true;
        else return false;
    }

    static bool computeElements(std::vector<int> &v, std::list<int> &li, int pos, int n);
    static bool fillFrom(std::vector<int> &v, std::list<int> &li, int pos, int n);

public:

    static bool solve(const std::vector<int> &A);

};

// Solver.cpp
#include "Solver.h"

#include <iterator>     // std::back_inserter
#include <algorithm>
#include <iostream>

bool Solver::computeElements(std::vector<int> &v, std::list<int> &li, int pos, int n)
{
    int from = pos*(pos + 1) / 2;
    int to = from + pos + 1;

    int diff = v[v.size() - (from + 1)] - v[pos];
    std::list<int>::iterator it = std::find(li.begin(), li.end(), diff);
    if (it != li.end())
    {
        v[v.size() - (to + 1)] = *it;
        li.erase(it);
    }
    else return false;

    int index = pos;
    int inc = n - 1;
    for (int p = pos; p > 0; p--, inc--) {

        int sum = v[index - 1] + v[pos];
        std::list<int>::iterator it = std::find(li.begin(), li.end(), sum);
        if (it != li.end())
        {
            index += inc;
            v[index] = *it;
            li.erase(it);
        }
        else return false;
    }
    return true;
}

bool Solver::fillFrom(std::vector<int> &v, std::list<int> &li, int pos, int n)
{
    for (std::list<int>::iterator it = li.begin(); it != li.end(); it++)
    {
        std::list<int> liCopy;
        std::copy(li.begin(), it, std::back_inserter(liCopy));
        std::list<int>::iterator it2 = it;
        it2++;
        std::copy(it2, li.end(), std::back_inserter(liCopy));
        v[pos] = *it;
        if (!computeElements(v, liCopy, pos, n)) {
            continue;
        }
        if (pos == n - 2) return true;
        if (fillFrom(v, liCopy, pos + 1, n)) return true;
    }
    return false;
}

bool Solver::solve(const std::vector<int> &A)
{

    int len = A.size();
    int n = (int)sqrt(len * 2);
    if (!checkLength(n, len)) {
        std::cout << "Incorrect length of the set\n";
        return false;
    }

    std::list<int> li;
    std::copy(A.begin(), A.end(), std::back_inserter(li));
    std::vector<int> v(A.size(), 0);
    int s = v.size();
    v[s - 1] = li.back();
    li.pop_back();
    v[s - 2] = li.back();
    li.pop_back();
    v[0] = v[s - 1] - v[s - 2];
    std::list<int>::iterator it = std::find(li.begin(), li.end(), v[0]);
    if (it != li.end())
    {
        v[0] = *it;
        li.erase(it);
    }

    if (fillFrom(v, li, 1, n)) {
        std::cout << "Solution: ";
        for (int i = 0; i<n; i++) {
            std::cout << v[i] << " ";
        }
        std::cout << std::endl;
        return true;
    }
    else {
        std::cout << "Set can't be solved" << std::endl;
        return false;
    }
}

Przepisałem też rozwiązanie Trzeźwego Karpia z Pythona na C++

// Solver2.h
#pragma once
#include <vector>
#include <map>
#include <list>

class Solver2
{
    static bool recCreateMap(std::vector<int> &mapa, std::map<int, int> &cnt, std::map<int, std::list<int> > &ends);

public:
    static bool solve(const std::vector<int> &A);
};

// Solver2.cpp
#include "Solver2.h"

#include <iostream>

using namespace std;

void collectionsCounter(const vector<int> &A, map<int, int> &mapa)
{
    for (int el : A) mapa[el]++;
}

bool Solver2::recCreateMap(vector<int> &M, map<int,int> &cnt, map<int, list<int> > &ends)
{
    vector<int> elems;
    for (pair<int, int> p : cnt)
    {
        for (int i = 0; i < p.second; i++) elems.push_back(p.first);
    }
    if (elems.empty()) return true;
    else
    {
        for (int a : elems)
        {
            int e = a - M.back();
            if (e > 0 && cnt.count(e) > 0)
            {
                bool accept = true;
                map<int, int> newCnt(cnt);
                map<int, list<int> > newEnds(ends);
                for (auto& p : ends)
                {
                    for (int v : p.second)
                    {
                        if (p.first == 0 || M.size() == v+1)
                        {
                            if (newCnt.count(p.first + e) == 0)
                            {
                                accept = false;
                                break;
                            }
                            newEnds[p.first + e].push_back(M.size());
                            newCnt[p.first + e] --;
                            if (newCnt[p.first + e] == 0)
                                newCnt.erase(p.first + e);
                        }
                    }
                }
                if (accept)
                {
                    M.push_back(e);
                    bool res = recCreateMap(M, newCnt, newEnds);
                    if (res) return true;
                    M.pop_back();
                }
            }
           
        }
    }
    return false;
}

bool Solver2::solve(const vector<int> &A)
{
    vector<int> M;
    int s = A.size();
    M.push_back(A[s - 1] - A[s - 2]);
    map<int, int> cnt;
    collectionsCounter(A, cnt);

    cnt[M[0]]--;
    map<int, list<int> > ends;
    
    ends[0].push_back(0);
    ends[M[0]].push_back(0);

    bool res = recCreateMap(M, cnt, ends);
    if (res)
    {
        cout << "Rozwiazanie: ";
        for (int i = 0; i < M.size(); i++)
        {
            cout << M[i] << " ";
        }
        cout << "\n";
    }
    else
    {
        cout << "Brak rozwiazania\n";
    }
    return res;
}

Oba rozwiazania wywoluje sie tak samo:

int main()
{
    vector<int> A = { 1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48 };
    vector<int> B = { 2,2,4,6,15,17,19,21,21,23 };
    vector<int> C = { 2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18 };

    Solver s;
    
    s.solve(A);
    s.solve(B);
    s.solve(C);

    Solver2 s2;
    s2.solve(A);
    s2.solve(B);
    s2.solve(C);

    return 0;
}

Przeprowadzilem tez analizę porównawczą wydajności obu algorytmów w zależności od N - rozmiaru rozwiązania. Wyniki w następnym wpisie.

0

Fajnie gutek. Jestem ciekawy analizy. Wprowadzilem troche poprawek do algorytmu tak wiec mozesz je przelozyc na cpp:

import math
import collections
import copy

def recCreateMap(M, cnt, ends):
    print(M)
    if len(cnt) == 0:
        return M
    else:
        for a in cnt.elements():
            e = a-M[-1]
            if e > 0 and e in cnt:
                accept = True
                newCnt = collections.Counter(cnt)
                newEnds = copy.deepcopy(ends)
                for k, l in ends.items():
                    for v in l:
                        if k == 0 or len(M) == v+1:
                            if k+e not in newCnt:
                                accept = False
                                break
                            newEnds[k+e].append(len(M))
                            newCnt[k+e] -= 1
                            if newCnt[k+e] <= 0: 
                                del newCnt[k+e]
                    if not accept:
                        break
                  
                if accept:
                    M.append(e)
                    res = recCreateMap(M, newCnt, newEnds)
                    if res is not None: return res
                    M.pop()
            

def createMap(A):    
    M = [A[-1] - A[-2]]
    cnt = collections.Counter(A)
    cnt[M[-1]] -= 1
    if cnt[M[-1]] <= 0:
        del cnt[M[-1]]
    ends = collections.defaultdict(list)
    ends[0] = [0]
    ends[M[-1]] = [0]
    return recCreateMap(M, cnt, ends)
    
print(createMap([2,2,4,15,17,19,6,21,21,23]))
print(createMap([2,3,3,4,6,6,7,8,9,9,11,12,15,15,18]))
print(createMap([1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48]))
0

Mój eksperyment wyglądał następująco: napisałem generator zadań, który przyjmował jako parametr długość rozwiązania (np. 5), tworzył losowy ciąg całkowity o tej długości (rozwiązanie) i wyliczał jego obraz (zadanie) w tym przypadku o długości 15.Obraz był posortowany z pominięciem 2 ostatnich elementów, tak by dały prawidłowy pierwszy element rozwiązania. Następnie dla parametrów N=20, 40, ... 280 wygenerowałem po 10 par zadanie-rozwiązanie i dałem Solverom do rozwiązania. Wyniki dla danego N to uśredniony czas z 10.zadań.

Oba Solvery mają podobną złożoność obliczeniową, czyli wykładniczą, z tym że działają optymalniej w różnych zakresach. Mniej więcej dla N=140 mają równą szybkość, dla N<140 Twój jest szybszy, dla N>140 mój jest szybszy i jego przewaga rośnie wraz z N :). Jednak zauważyłem, że o ile mój daje dość powtarzalne czasy, Twój potrafi zaskoczyć bardzo szybkim wyliczeniem, np. dla N=260, Twój dawał rozwiązał 9 zadań średnio w 223 s., ale ostatnie rozwiązał w 3 s. (!!!). Możliwe, że lepiej radzi sobie z posortowanymi danymi w obrazie. Dla N=280 Solver2 działa niestety dość wolno, i nie zdążyłem wygenerować pełnych wyników, jedynie mam czas dla jednego zadania: 2045,79 s.

Wydaje mi się, że wykorzystując Twoje słownikowe struktury danych w moim Solverze można by jeszcze poprawić jego działanie.
Twoich ostatnich poprawek nie wprowadzałem, to są eksperymenty z wersji, którą podałeś wczoraj.

screenshot-20180218143349.png

0

Dobra analiza. Jakbys mial czas to wrzuc wyniki z poprawionym kodem. Takze do kilku miejsc w kodzie bym sie przyczepil (np. uzywanie map zamiast hash map).
Takze ten kod mozna zoptymalizowac:

                            newCnt[p.first + e] --;
                            if (newCnt[p.first + e] == 0)

na

                            if (--newCnt[p.first + e] == 0)

1 użytkowników online, w tym zalogowanych: 0, gości: 1