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
|
#include<iostream>
#include<string>
#include<algorithm>
#include<list>
#include<vector>
#include<fstream>
using namespace std;
int dicho_rech(vector<string> vect, string mot)
{
int centre;
int bas=0;
int haut=vect.size()-1 ;
while(bas <= haut)
{
centre = (bas+haut)/2; // élément central de la partie traité
if(mot.compare(vect[centre])==0) // valeur trouvée
return centre;
else if(mot.compare(vect[centre])<0)
haut = centre-1; // recherche ds la partie inférieure du tableau
else if(mot.compare(vect[centre])>0)
bas = centre+1; // recherche ds la partie supérieure du tableau
}
return -1; // valeur recherchée non trouvée
}
string ltos_conversion(list<char> l)
{
<a href="http://www.freelang.com/download/misc/liste_francais.zip" target="_blank">http://www.freelang.com/download/mis...e_francais.zip</a>
list<char>::iterator it=l.begin() ;
string s ="";
s+=*it ;
for (int i = 1 ; i<l.size();i++) { advance(it,1) ; s=s+*it; }
return s ;
}
void print( list<char> l){
for(list<char>::iterator it=l.begin(); it!=l.end() ; ++it)
cout << *it;
cout<<endl;
}
void subset(char arr[], int size, int left, int index, list<char> &l , vector<string>& words , vector<string> dicovec , int& j ,vector<string>&solval){
if(left==0)
{
string s = ltos_conversion(l);
std::sort(s.begin(),s.end());
do
{
solval.push_back(s);
j++ ;
if(j%1000==0) cout<<"boucle numero "<<j<<endl;
int ind = dicho_rech(dicovec,s);
if (ind!=-1) { words.push_back(s) ; cout<<"une solution"<<endl;}
}
while (next_permutation(s.begin(),s.end())) ;
return ;
}
for(int i=index; i<size;i++){
l.push_back(arr[i]);
subset(arr,size,left-1,i+1,l,words,dicovec,j,solval);
l.pop_back();
}
}
int main(int argc,char** argv)
{
ifstream dico("liste_francais.txt",ios::in);
vector<string> words ;
vector<string> dicovec ;
vector<string> solvalvec;
char array[10]={'a','g','u','e','r','i','c','f','p','r'};
list<char> lt;
int i =8;
int k=0 ;
string line ;
while(getline(dico,line)) { dicovec.push_back(line) ;}
sort(dicovec.begin(),dicovec.end());
while ((words.size()==0)&&(i>=1))
{
subset(array,8,i,0,lt,words,dicovec,k,solvalvec);
i-- ;
}
for(i=0;i<words.size();i++) cout<<words[i]<<endl;
dico.close();
return 0;
} |
