-
Notifications
You must be signed in to change notification settings - Fork 2
/
cl_brute.cpp
133 lines (123 loc) · 3.79 KB
/
cl_brute.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//cl_brute.cpp
/*
Copyright (C) 2013 AIDEUS
authors: Sergey Rodionov ([email protected])
Alexey Potapov ([email protected])
aideus.com
This file is part of cl-lab.
cl-lab is released under the GNU General Public License (GNU GPL).
Please read the included file COPYING for more information.
*/
#include "cl_brute.h"
void cl_brute_all_brackets(int i1, int i2, vector< vector< pair<int,int> > >& allb)
{
//1. no brackets at all
allb.push_back( vector< pair<int,int> >() );
// cout<<i1<<" "<<i2<<endl;
for (int pos1 = i1; pos1 < i2 - 1 ; pos1++)
for (int pos2 = pos1 + 2; pos2 <= i2 ; pos2++)
{
pair<int,int> main_brackets(pos1,pos2);
vector< vector< pair<int,int> > > inside_main, after_main;
cl_brute_all_brackets(pos1 + 1, pos2, inside_main);
cl_brute_all_brackets(pos2, i2, after_main);
for (size_t ii = 0 ; ii < inside_main.size() ; ii++)
for (size_t ia = 0 ; ia < after_main.size() ; ia++)
{
vector< pair<int,int> > b;
//add main brackets
b.push_back(main_brackets);
//add brackets inside main
b.insert(b.end(), inside_main[ii].begin(), inside_main[ii].end());
//add brackets after main
b.insert(b.end(), after_main[ia].begin(), after_main[ia].end());
allb.push_back(b);
}
}
}
//
void cl_brute_apply_brackets(string s, const vector< pair<int,int> >& brackets, string& rez)
{
vector< string > ss(s.size());
for (size_t i = 0 ; i < s.size() ; i++)
ss[i] = s[i];
for (size_t i = 0 ; i < brackets.size() ; i++)
{
size_t pos1 = brackets[i].first;
size_t pos2 = brackets[i].second;
if (pos1 >= ss.size() || pos2 >= ss.size())
{
cerr<<"Error | cl_brute_apply_brackets | internal error"<<endl;
exit(EXIT_FAILURE);
}
ss[pos1].push_back('(');
ss[pos2].push_back(')');
}
rez.clear();
for (size_t i = 0 ; i < ss.size() ; i++)
rez.append(ss[i]);
}
//
//
void cl_brute_generator::init(int l_, string alphabet_)
{
l = l_;
alphabet = alphabet_;
cl_brute_all_brackets(0, l - 1, allb);
cs = vector<size_t>(l, 0);
cb = 0;
}
//
bool cl_brute_generator::get_next(string& s)
{
s = "";
if (cb == allb.size()) //finish
return false;
generate_string(s);
if (!get_next_cs())
{
//put zeros to cs again
fill(cs.begin(), cs.end(), 0);
cb++; //and take new bracket set
}
return true;
}
//
string cl_brute_generator::create_random()
{
cb = random() % allb.size();
for (size_t i = 0 ; i < cs.size() ; i++)
cs[i] = random() % alphabet.size();
string s;
generate_string(s);
return s;
}
//
bool cl_brute_generator::get_next_cs()
{
size_t ci = cs.size() - 1; //current index in cs
while(cs[0] != alphabet.size())
{
cs[ci]++;
if (cs[ci] != alphabet.size())
{
return true;
}
if (ci != 0)
{
cs[ci] = 0;
ci--;
}
}
return false;
}
//
void cl_brute_generator::generate_string(string& s)
{
string bfs;
bfs.resize(cs.size()); //bracket free string
for (size_t i = 0 ; i < cs.size() ; i++)
bfs[i] = alphabet.at(cs[i]);
cl_brute_apply_brackets(bfs, allb.at(cb), s);
}
//