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 ?
On May 31, 9:09 pm, Loïc Joly <loic.actarus.j...@numericable.fr>
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 ?
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 ?
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 ) ;
}
On Jun 1, 11:29 pm, David Fleury <dfleu...@libertysurf.fr> 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 ) ;
}
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.
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.
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.
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 ?
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 ?
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 ?
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.
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.
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.
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'é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'é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 ?
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.
On Jun 3, 10:13 pm, David Fleury <dfleu...@libertysurf.fr> 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.
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.
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.
(ç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 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)
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 :)
On Jun 3, 10:13 pm, David Fleury <dfleu...@libertysurf.fr> 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.
(ç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 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)
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 :)
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.
(ç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 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)
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 :)
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.
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é.
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.
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é.
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.
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é.
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.
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.
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.