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.