Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

comment reduire ca

31 réponses
Avatar
giovanni
voila j ailes combinaison suivante
123 donc memoire 1 et memoire 2 et memoire 3 = total
124 donc memoire 1 et memoire 2 et memoire 4 = total2
125 etc
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456

voici comme j'aifait moi pour la combinaison 123

if (nb_11==nb_1 || nb_11==nb_2 || nb_11==nb_3 || nb_11==nb_4 ||
nb_11==nb_5 || nb_11==nb_6)
{if (nb_22==nb_1 || nb_22==nb_2 || nb_22==nb_3 || nb_22==nb_4 ||
nb_22==nb_5 || nb_22==nb_6)
{if (nb_33==nb_1 || nb_33==nb_2 || nb_33==nb_3 || nb_33==nb_4 ||
nb_33==nb_5 || nb_33==nb_6)
{ ++t123; printf(" test t123=%d \n",t123);}}}
et recopie la meme chose en changeant les memoire mais je n arrive pas avec
une boucle le faire et quel utiliser while do ou for ou case??
merci

10 réponses

1 2 3 4
Avatar
James Kanze
On Jun 1, 11:29 pm, David Fleury wrote:

On May 31, 9:09 pm, Loïc Joly
wrote:



D'après la liste de chiffres qu'il a donné, je crois que ce
qu'il cherche, c'est toutes les combinaisons de 3 chiffres,
choisis parmi les 6 premiers. Il y a une solution simple (mais
très inefficace) pour le faire avec la bibliothèque standard,
utilise next_permutation pour générer toutes les permutations
des six chiffres, trie-les, et supprimer les dupliqués.


En utilisant un std::set ou unordered_set au lieu d'un std::vector on
supprime les deux dernières choses.


Pour moi, on ne les supprime pas, on ne fait que les réaliser
de manière automatique par la STL. Ca restera quand même bien
moins efficace qu'un algo qui dès le début se débrouille pour
ne pas générer certaines permutations.


Tout à fait, et c'est à ça que je pensais quand j'ai écrit
« (mais très inefficace) ». Pour 3 dans 6, je ne crois pas que
ça a de l'importance, mais pour 100 dans 1000... L'algorithme
que j'ai proposé est O(n!), quand même. (J'ai une assez bonne
idée de comment je m'attaquerais au problème, mais je ne connais
pas d'algorithme de tête pour le faire, et il n'y en a
certainement pas dans la bibliothèque standard.)


Juste pour savoir, la récursion ne serait pas une possibilité
acceptable ?


C'est effectivement l'approche à laquelle je pensais. Ou enfin,
un melange : on itère sur le premier élément, en l'écartant de
l'ensemble une fois qu'on l'a traité, et on itère pour les
autres. Quelque chose du genre :

void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
result.push_back( so_far ) ;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end,
m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >&
result,
std::vector< int > const&
set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}

--
James Kanze (Gabi Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34





Avatar
David Fleury
On Jun 1, 11:29 pm, David Fleury wrote:
Tout à fait, et c'est à ça que je pensais quand j'ai écrit
« (mais très inefficace) ». Pour 3 dans 6, je ne crois pas que
ça a de l'importance, mais pour 100 dans 1000... L'algorithme
que j'ai proposé est O(n!), quand même. (J'ai une assez bonne
idée de comment je m'attaquerais au problème, mais je ne connais
pas d'algorithme de tête pour le faire, et il n'y en a
certainement pas dans la bibliothèque standard.)


Juste pour savoir, la récursion ne serait pas une possibilité
acceptable ?


C'est effectivement l'approche à laquelle je pensais. Ou enfin,
un melange : on itère sur le premier élément, en l'écartant de
l'ensemble une fois qu'on l'a traité, et on itère pour les
autres. Quelque chose du genre :

void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
result.push_back( so_far ) ;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end,
m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >&
result,
std::vector< int > const&
set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}



C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peut être.
(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector) mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une base "n"
pour résoudre en itératif.

David.



Avatar
Vincent Lascaux
C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peut être.
(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector) mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une base "n"
pour résoudre en itératif.


Je comprends pas, une triple boucle (genre premiere variable de 1 à 6,
deuxième de la première + 1 à 6, troisième de la deuxième + 1 à 6) ne
résoud-elle pas le problème en 3 lignes de code, de façon claire et
avec une complexité minimal (en O du nombre de solutions) et avec une
très petite constante ?

--
Vincent

Avatar
David Fleury
C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peut être.
(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector) mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une base "n"
pour résoudre en itératif.


Je comprends pas, une triple boucle (genre premiere variable de 1 à 6,
deuxième de la première + 1 à 6, troisième de la deuxième + 1 à 6) ne
résoud-elle pas le problème en 3 lignes de code, de façon claire et
avec une complexité minimal (en O du nombre de solutions) et avec une
très petite constante ?



Le but se serait de générer les séries pour d'autres valeurs que 6 et 3.
(même si 1000!/(100!*900!) c'est pas pour tout de suite)
Sinon c'est pas assez drôle.


Avatar
James Kanze
On Jun 3, 10:13 pm, David Fleury wrote:

void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
result.push_back( so_far ) ;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >&
result,
std::vector< int > const&
set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}


C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peut être.


Comment, « moins obfusqué » ? J'ai plutôt l'impression que
c'est assez idiomatique. (Ben, il manque peut-être un peu de
commentaire, mais c'est tout.)

(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector)


J'aimerais voir comment faire en 5 lignes avec std::string,
étant donné que std::string a plus ou moins la même interface
que vector, ici.

mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une
base "n" pour résoudre en itératif.


Je suis preneur. Montre.

--
James Kanze (Gabi Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
James Kanze
On Jun 3, 10:48 pm, Vincent Lascaux wrote:
C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peu t être.
(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector) mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une base "n"
pour résoudre en itératif.


Je comprends pas, une triple boucle (genre premiere variable de 1 à 6,
deuxième de la première + 1 à 6, troisième de la deuxième + 1 à 6) ne
résoud-elle pas le problème en 3 lignes de code, de façon claire et
avec une complexité minimal (en O du nombre de solutions) et avec une
très petite constante ?


C'est un peu figé, non ? (Et je ne vois même pas comment le
résoudre pour ls cas de 3, avec des boucles embriquer, au moins
de remplir les boucles avec des if outre-compliqué.)

--
James Kanze (Gabi Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
David Fleury
On Jun 3, 10:13 pm, David Fleury wrote:

void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
result.push_back( so_far ) ;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >&
result,
std::vector< int > const&
set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}


C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" peut être.


Comment, « moins obfusqué » ? J'ai plutôt l'impression que
c'est assez idiomatique. (Ben, il manque peut-être un peu de
commentaire, mais c'est tout.)



En fait, je crois que c'est moi qui ne suis pas à l'aise
quand je suis en mode 'algo' pour lire les itérateurs.



(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector)


J'aimerais voir comment faire en 5 lignes avec std::string,
étant donné que std::string a plus ou moins la même interface
que vector, ici.


"plus ou moins" fait toute la différence pour le cout
et l'absence d'opérateur +

Ca donnerait quelque chose comme ça:

void compute( int permutationSize, int maxValue, string v = "", int
currentValue = 0, int currentSize = 0 )
{
if ( currentSize == permutationSize )
cout << v << endl;
else
for ( int i = currentValue + 1; i <= maxValue; ++i )
compute( permutationSize, maxValue, v + (char)( '0' + i ), i,
currentSize + 1 );
}

int main() { compute( 3, 6 ); }

5 lignes en réduisant un peu de domaine de valeur à ce que peut contenir
un char.
avec un vector, ce serait plus long à cause de l'affichage
et de l'objet temporaire à créer pour l'appel récursif (environ 8 lignes
au final)


mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une
base "n" pour résoudre en itératif.


Je suis preneur. Montre.


Comme je dors moi ;), je viens de mettre ça au point ce matin.
(je suis un peu un retard pour le boulot mais tant pis :) )

Voilà :

bool increment( vector<int>& value, int maxValue, int maxPermutation )
{
bool hasOverflow = true;
int currentDigit = value.size()-1;

while( hasOverflow && currentDigit >= 0 )
{
hasOverflow = ++value[currentDigit] > ( maxValue - ( maxPermutation
- currentDigit - 1 ) );
if ( !hasOverflow )
for ( int i = currentDigit+1; i < value.size(); ++i )
value[i] = value[i-1] + 1;

--currentDigit;
}
if ( hasOverflow && currentDigit<0 ) return false;

return true;
}


void compute( int maxPermutation, int maxValue )
{
vector< int > value;
for ( int i = 1 ; i <= maxPermutation; ++i )
value.push_back( i ) ;

do {
copy( value.begin(), value.end(), ostream_iterator<int>( cout, " " ) );
cout << endl;
} while( increment( value, maxValue, maxPermutation ) );
}

int main()
{
compute( 3, 6 );
}

A mon avis, les deux subilités si on veut, c'est :
1 - la détection de l'overflow (je ne suis pas sur que ça veuille
dire retenue en anglais mais j'ai vraiment pas le temps de vérifier)
2 - le raccourci volontaire sur if ( !hasOverflow )

Sauf bug, ça doit marcher pas trop mal :)
En tout cas c'est bon pour 3/6

David



Avatar
James Kanze
On Jun 4, 8:59 am, David Fleury wrote:
On Jun 3, 10:13 pm, David Fleury wrote:

void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
result.push_back( so_far ) ;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >&
result,
std::vector< int > const&
set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}


C'était l'idée.
J'aurais peut être fait ça plus "à la C" et moins "obfusqué" p eut être.


Comment, « moins obfusqué » ? J'ai plutôt l'impression que
c'est assez idiomatique. (Ben, il manque peut-être un peu de
commentaire, mais c'est tout.)


En fait, je crois que c'est moi qui ne suis pas à l'aise
quand je suis en mode 'algo' pour lire les itérateurs.


J'avoue qu'en général, je préfère les itérateurs classiques
aussi, avec un seul itérateur par itération. Curieusement, je
trouve que cet algorithme est un des rares cas où l'idiome des
deux itérateurs convient peut-être plus.

(ça doit faire 5 lignes de code en prenant une string au lieu d'un
vector)


J'aimerais voir comment faire en 5 lignes avec std::string,
étant donné que std::string a plus ou moins la même interface
que vector, ici.


"plus ou moins" fait toute la différence pour le cout
et l'absence d'opérateur +

Ca donnerait quelque chose comme ça:

void compute( int permutationSize, int maxValue, string v = "", int
currentValue = 0, int currentSize = 0 )
{
if ( currentSize == permutationSize )
cout << v << endl;
else
for ( int i = currentValue + 1; i <= maxValue; ++i )
compute( permutationSize, maxValue, v + (char)( '0' + i ), i,
currentSize + 1 );
}


D'accord. Tu supposes que les valeurs sont dans [1...n], plutôt
que de les prendre d'un vector, et tu sors le resultat
directement dans cout, plutôt que de le sauver dans un autre
vector. Et vue que tu travailles à tous les niveaux avec les
indices, tu peux t'en tirer avec des paramètres par défaut.

J'avais commencé un peu dans ce sens, et puis je me suis dit que
récopier le vecteur « so_far » (ton « v »), ce n'était pas
très élégant. C'est sans doute un peu d'optimization prématurée
de ma part.

int main() { compute( 3, 6 ); }

5 lignes en réduisant un peu de domaine de valeur à ce que peut conte nir
un char.
avec un vector, ce serait plus long à cause de l'affichage
et de l'objet temporaire à créer pour l'appel récursif (environ 8 l ignes
au final)


Tu passes un paramètre où mettre les résultats, comme j'ai fait,
et ce n'est pas ça qui augmente la taille de l'algorithme
proprement dit. Mais évidemment, arrivé à quelque chose comme
10000 dans 1000000, toutes ces copies risquent d'avoir un effet
néfaste sur les performances. Si tu régardes bien, les lignes en
plus dans ma version de la partie recursive (parce que la reste,
c'est de la présentation), c'est pour réutiliser toujours le
même vector pour les valeurs que je génère, sans jamais le
copier.

mais je voudrais pas donner une solution trop présentable.

Finalement, j'ai eu une idée pour la version itérative.
Et le mot "permutation" ne va pas vers la bonne piste.

Il suffirait de modifier légèrement une addition de 1 dans une
base "n" pour résoudre en itératif.


Je suis preneur. Montre.


Comme je dors moi ;), je viens de mettre ça au point ce matin.
(je suis un peu un retard pour le boulot mais tant pis :) )

Voilà :

bool increment( vector<int>& value, int maxValue, int maxPermutation )
{
bool hasOverflow = true;
int currentDigit = value.size()-1;

while( hasOverflow && currentDigit >= 0 )
{
hasOverflow = ++value[currentDigit] > ( maxValue - ( maxPermutation
- currentDigit - 1 ) );
if ( !hasOverflow )
for ( int i = currentDigit+1; i < value.size(); ++i )
value[i] = value[i-1] + 1;

--currentDigit;
}
if ( hasOverflow && currentDigit<0 ) return false;
return true;
}

void compute( int maxPermutation, int maxValue )
{
vector< int > value;
for ( int i = 1 ; i <= maxPermutation; ++i )
value.push_back( i ) ;

do {
copy( value.begin(), value.end(), ostream_iterator<int>( cout, " " ) );
cout << endl;
} while( increment( value, maxValue, maxPermutation ) );
}

int main()
{
compute( 3, 6 );
}

A mon avis, les deux subilités si on veut, c'est :
1 - la détection de l'overflow (je ne suis pas sur que ça veuille
dire retenue en anglais mais j'ai vraiment pas le temps de vérifier)


Dans ce cas-ci, je crois que je dirais le débordement d'une
cellule (ce que tu as appelé digit).

2 - le raccourci volontaire sur if ( !hasOverflow )

Sauf bug, ça doit marcher pas trop mal :)


En effet. L'idée est intéressant : en gros, tu exploites
l'idée que les seules informations dans la pile de récursion
dont tu as réelement besoin, tu peux les réconsituer à partir du
contenu du vecteur. C'est vrai ; je n'y avais pas pensé.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34




Avatar
David Fleury


Tu passes un paramètre où mettre les résultats, comme j'ai fait,
et ce n'est pas ça qui augmente la taille de l'algorithme
proprement dit. Mais évidemment, arrivé à quelque chose comme
10000 dans 1000000, toutes ces copies risquent d'avoir un effet
néfaste sur les performances. Si tu régardes bien, les lignes en
plus dans ma version de la partie recursive (parce que la reste,
c'est de la présentation), c'est pour réutiliser toujours le
même vector pour les valeurs que je génère, sans jamais le
copier.



je vais relire plus en détail.
Il semble intéresant de voir comment éviter la recopie.



A mon avis, les deux subilités si on veut, c'est :
1 - la détection de l'overflow (je ne suis pas sur que ça veuille
dire retenue en anglais mais j'ai vraiment pas le temps de vérifier)


Dans ce cas-ci, je crois que je dirais le débordement d'une
cellule (ce que tu as appelé digit).


Oui, le terme "digit" venait de l'analogie avec un nombre.
"carry" devant plutôt être le terme pour retenue lors d'une addition.


2 - le raccourci volontaire sur if ( !hasOverflow )

Sauf bug, ça doit marcher pas trop mal :)


En effet. L'idée est intéressant : en gros, tu exploites
l'idée que les seules informations dans la pile de récursion
dont tu as réelement besoin, tu peux les réconsituer à partir du
contenu du vecteur. C'est vrai ; je n'y avais pas pensé.



A la base, cela vient de l'idée de générer toutes les permutations
en supprimant celles qui ne sont pas valides. Ensuite, ce sont des
réglages sur un code d'addition simple.
En tout cas, c'est plus rapide qu'en récursif, et ça laisse à l'OP
pas mal de choix pour trouver une solution.

David.


Avatar
James Kanze
On Jun 4, 9:45 pm, David Fleury wrote:

Tu passes un paramètre où mettre les résultats, comme j'ai fait,
et ce n'est pas ça qui augmente la taille de l'algorithme
proprement dit. Mais évidemment, arrivé à quelque chose comme
10000 dans 1000000, toutes ces copies risquent d'avoir un effet
néfaste sur les performances. Si tu régardes bien, les lignes en
plus dans ma version de la partie recursive (parce que la reste,
c'est de la présentation), c'est pour réutiliser toujours le
même vector pour les valeurs que je génère, sans jamais le
copier.


je vais relire plus en détail.
Il semble intéresant de voir comment éviter la recopie.


Au fond, ce n'est pas beaucoup différent de ce que tu fais dans
ta version non-récursive, au moins en principe. (Je modifie bien
la taille de la chaîne, au moyen des push_back et des pop_back.
Mais une fois qu'on est arrivé à la capacité maximum, ça doit se
résumer à la modification d'un pointeur de fin dans
l'implémentation.)

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate. Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


1 2 3 4