festerbestertester
BAN USERSeems to work on multiple data sets:
int main()
{
std::vector<int> vals;
//int values[] = {-1,2,100,100,101,3,4,5,-7};
int values[] = {-1,2,100,100,101,3,4,5,-7,1,2,3,4,5,6,300,-200,7,8,9};
for(int x = 0; x < sizeof(values)/sizeof(values[0]); ++x)
vals.push_back(values[x]);
std::vector<int> res = find_subseq2(vals);
getchar();
This gives the correct result. Not sure if it is correct? Comments?
static int get_min_greater_than(const std::vector<int>& items, size_t nStart, int valToBeGreaterThan)
{
int nLeastGreaterThan = valToBeGreaterThan;
for(size_t x = nStart, n = items.size(); x < n; ++x)
{
const int v = items[x];
if(v > valToBeGreaterThan)
{
if(nLeastGreaterThan == valToBeGreaterThan || v < nLeastGreaterThan)
nLeastGreaterThan = v;
}
}
return nLeastGreaterThan;
}
std::vector<int> find_subseq2(const std::vector<int>& items)
{
std::vector< std::list<int> > all;
std::list< std::list<int> > allExtras;
for(size_t x = 0, n = items.size(); x < n; ++x)
{
bool bInserted = false;
const int v = items[x];
for(std::vector< std::list<int> >::iterator i = all.begin(), e = all.end(); i != e; ++i)
{
std::list<int>& thisList = *i;
if(v > *thisList.rbegin())
{
const int nMinGreaterThan = get_min_greater_than(items, x, *thisList.rbegin());
if(v != nMinGreaterThan)
{
// we should be able to add
std::list<int> extra;
extra.insert(extra.end(), thisList.begin(), thisList.end());
allExtras.push_back(extra);
}
thisList.push_back(v);
bInserted = true;
}
}
all.insert(all.end(), allExtras.begin(), allExtras.end());
if(!bInserted)
{
// wasn't part of any existing sequence
all.resize(all.size()+1);
std::list<int>& thisList = all[all.size()-1];
thisList.push_back(v);
}
}
size_t nMaxSize = 0, nMaxPosition = 0;
for(size_t x = 0, n = all.size(); x < n; ++x)
{
if(all[x].size() > nMaxSize)
{
nMaxSize = all[x].size();
nMaxPosition = x;
}
}
std::vector<int> res;
if(all.size())
{
std::list<int>& thisList = all[nMaxPosition];
res.insert(res.end(), thisList.begin(), thisList.end());
}
return res;
}
{{
int get_required_bits()
{
double bits = 0;
for(int x = 52; x >= 1; --x)
bits += log((double)x);
return (int)ceil(bits);
}
}}}
Ok, this works and return minimum swaps
- festerbestertester February 27, 2015