Question hyper-basique

[JLH974]

Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je bute
dessus :
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?

JLH La Réunion

[Serge Paccalin]

Le Wed, 3 Mar 2010 13:01:29 +0400, JLH974 a écrit

Post by JLH974
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?

Récursivement, c'est très simple.

Choisir n objets parmi m, c'est :
— choisir 1 objet parmi les m - n + 1 premiers
— choisir n - 1 objets parmi ceux qui restent entre le 1er choisi
(exclu) et le dernier (inclus).

[zwim]

Le Wed, 3 Mar 2010 13:01:29 +0400
JLH974 a écrit

Post by JLH974
Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je bute
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?
JLH La Réunion

Voir les liens proposés par A.Caspis dans ce thread.

http://groups.google.fr/group/fr.sci.maths/browse_thread/thread/e0caa3b54915763/e0c5a2bf18c2b3e7

[JLH974]

Merci Zwim pour ces liens intéressants
Mais je suis un peu "décontenancé"
Je remarque dans les lignes des Goto qui m'embarassent
J'ai appris l'informatique en pratiquant le basic et ses goto
J'ai mis longtemps avant de m'en débarasser et j'ai mis encore plus
longtemps avant de saisir la programmation objet
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

Jean-Luc

Post by Serge Paccalin
Le Wed, 3 Mar 2010 13:01:29 +0400
JLH974 a écrit

Post by JLH974
Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je bute
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?
JLH La Réunion

Voir les liens proposés par A.Caspis dans ce thread.
http://groups.google.fr/group/fr.sci.maths/browse_thread/thread/e0caa3b54915763/e0c5a2bf18c2b3e7
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

[zwim]

Le Sat, 6 Mar 2010 22:36:38 +0400
JLH974 a écrit

Post by JLH974
Merci Zwim pour ces liens intéressants
Mais je suis un peu "décontenancé"
Je remarque dans les lignes des Goto qui m'embarassent
J'ai appris l'informatique en pratiquant le basic et ses goto
J'ai mis longtemps avant de m'en débarasser et j'ai mis encore plus
longtemps avant de saisir la programmation objet
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

Oui, en même temps la version en visual basic ne fait que plus ou
moins copier celle en fortran et en fortran 77, pas moyen de faire
autrement qu'avec des goto.

Ca doit être possible de faire une version propre en C avec des
fonctions qui vont bien apèrs tout.

Cela dit les goto ne sont pas définitivement bannis, car ils restent
dans certains cas l'instruction qui rend le code le plus lisible,
notamment pour les cas de gestion des erreurs ou pour effectuer un
break global pour sortir d'un traitement avec des boucles imbriquées.

Par example :

toto* a = NULL;
titi *b = NULL;

a = malloc(n);
if(!a) goto cleanup;

[code qui remplit a, depuis des data externes]

b = malloc(a[137]);
if(!b) goto cleanup;

[code de la fonction]
[...]

cleanup:
if(a) free(a); a=NULL;
if(b) free(b); b=NULL;

Bien entendu ici, c'est un cas d'école, mais imagine une fonction qui
doit initialiser non 2, mais 5 ou 6 pointeurs, fichiers, ou devices
avant de pouvoir commencer le traitement et que chacune de ces
initialisations puissent échouer.
Il est alors plus lisible de déporter le nettoyage vers un goto
cleanup; en fin de fonction puisque de toute façon dans le cas nominal
sans échecs, ce traitement de nettoyage sera de toute façon effectué
en fin de fonction.

Post by JLH974
Jean-Luc

Post by Serge Paccalin
Le Wed, 3 Mar 2010 13:01:29 +0400
JLH974 a écrit

Post by JLH974
Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je bute
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?
JLH La Réunion

Voir les liens proposés par A.Caspis dans ce thread.
http://groups.google.fr/group/fr.sci.maths/browse_thread/thread/e0caa3b54915763/e0c5a2bf18c2b3e7
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

[JLH974]

Merci Zwim
C'est vrai que les Goto dans les cas que tu cites sont quasi-irremplacables
Mais j'ai des manies de "vieux garçon" je vais essayer de retravailler
l'algorithme en adoptant une structure de boucle avec test et réécriture
dans chaque boucle
Ce sera lourd, répétitif, pas "élégant" pour deux bits mais comme disait le
professeur Shadoko : Pourquoi faire simple quand il est si facile de faire
compliqué...
Cela dit je ne suis pas sûr du tout d'y arriver... car les boucles
"s'autoimbriquent" en quelque sorte dans l'algorithme original et c'est mon
cauchemar...

A+
JLH

Post by zwim
Le Sat, 6 Mar 2010 22:36:38 +0400
JLH974 a écrit

Post by JLH974
Merci Zwim pour ces liens intéressants
Mais je suis un peu "décontenancé"
Je remarque dans les lignes des Goto qui m'embarassent
J'ai appris l'informatique en pratiquant le basic et ses goto
J'ai mis longtemps avant de m'en débarasser et j'ai mis encore plus
longtemps avant de saisir la programmation objet
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

Oui, en même temps la version en visual basic ne fait que plus ou
moins copier celle en fortran et en fortran 77, pas moyen de faire
autrement qu'avec des goto.
Ca doit être possible de faire une version propre en C avec des
fonctions qui vont bien apèrs tout.
Cela dit les goto ne sont pas définitivement bannis, car ils restent
dans certains cas l'instruction qui rend le code le plus lisible,
notamment pour les cas de gestion des erreurs ou pour effectuer un
break global pour sortir d'un traitement avec des boucles imbriquées.
toto* a = NULL;
titi *b = NULL;
a = malloc(n);
if(!a) goto cleanup;
[code qui remplit a, depuis des data externes]
b = malloc(a[137]);
if(!b) goto cleanup;
[code de la fonction]
[...]
if(a) free(a); a=NULL;
if(b) free(b); b=NULL;
Bien entendu ici, c'est un cas d'école, mais imagine une fonction qui
doit initialiser non 2, mais 5 ou 6 pointeurs, fichiers, ou devices
avant de pouvoir commencer le traitement et que chacune de ces
initialisations puissent échouer.
Il est alors plus lisible de déporter le nettoyage vers un goto
cleanup; en fin de fonction puisque de toute façon dans le cas nominal
sans échecs, ce traitement de nettoyage sera de toute façon effectué
en fin de fonction.

Post by JLH974
Jean-Luc

Post by Serge Paccalin
Le Wed, 3 Mar 2010 13:01:29 +0400
JLH974 a écrit

Post by JLH974
Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je bute
Comment -avec un algo très simple dont vous avez les secret- générer toutes
les combinaisons à n objets pris parmi une collection de m objets (m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?
JLH La Réunion

Voir les liens proposés par A.Caspis dans ce thread.
http://groups.google.fr/group/fr.sci.maths/browse_thread/thread/e0caa3b54915763/e0c5a2bf18c2b3e7
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

[Joe Cool]

Post by JLH974
C'est vrai que les Goto dans les cas que tu cites sont quasi-irremplacables

Excepté par des exceptions...

[Wykaaa]

Post by zwim
Le Sat, 6 Mar 2010 22:36:38 +0400
JLH974 a écrit

Post by JLH974
Merci Zwim pour ces liens intéressants
Mais je suis un peu "décontenancé"
Je remarque dans les lignes des Goto qui m'embarassent
J'ai appris l'informatique en pratiquant le basic et ses goto
J'ai mis longtemps avant de m'en débarasser et j'ai mis encore plus
longtemps avant de saisir la programmation objet
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

Oui, en même temps la version en visual basic ne fait que plus ou
moins copier celle en fortran et en fortran 77, pas moyen de faire
autrement qu'avec des goto.
Ca doit être possible de faire une version propre en C avec des
fonctions qui vont bien apèrs tout.
Cela dit les goto ne sont pas définitivement bannis, car ils restent
dans certains cas l'instruction qui rend le code le plus lisible,
notamment pour les cas de gestion des erreurs ou pour effectuer un
break global pour sortir d'un traitement avec des boucles imbriquées.
toto* a = NULL;
titi *b = NULL;
a = malloc(n);
if(!a) goto cleanup;
[code qui remplit a, depuis des data externes]
b = malloc(a[137]);
if(!b) goto cleanup;
[code de la fonction]
[...]
if(a) free(a); a=NULL;
if(b) free(b); b=NULL;
Bien entendu ici, c'est un cas d'école, mais imagine une fonction qui
doit initialiser non 2, mais 5 ou 6 pointeurs, fichiers, ou devices
avant de pouvoir commencer le traitement et que chacune de ces
initialisations puissent échouer.
Il est alors plus lisible de déporter le nettoyage vers un goto
cleanup; en fin de fonction puisque de toute façon dans le cas nominal
sans échecs, ce traitement de nettoyage sera de toute façon effectué
en fin de fonction.

Je vous conseille, si vous lisez l'anglais, la lecture de l'article de
Donald Knuth " Structured programming with goto statement" paru en
décembre 1974 dans la revue de l'ACM, Computing Survey.
C'est là : pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf

[Joe Cool]

Post by JLH974
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

C'est le cas, sauf chez les mauvais (ou les vieux) programmeurs.

[Jean-marc]

Post by Joe Cool

Post by JLH974
Je croyais les Goto définitivement sacrifiés sur l'autel du
"bien-programmer"?

C'est le cas, sauf chez les mauvais (ou les vieux) programmeurs.

Sauf avec les langages qui n'ont pas de mécanismes d'exception,
de try-catch, etc.

Dans ce cas, le "goto avec contraintes" (une seule étiquette de saut
par fonction, saut toujours en avant, goto utilisé seulement
pour de la gestion d'erreur) est une bonne pratique, courante.

On a déjà évoqué le sujet ici même et la conclusion était la
même pour à peu près tous : il vaut mieux un "bon goto" qu'un
code à profondeur d'indentation ridicule.

Finalement, peu de personnes ont réellement compris ce qu'avait
voulu dire Dijkstra dans son article et on le cite à tort et à
travers, un peu comme les gens qui n'y connaissent rien en maths
se gargarisent en citant le(s) "théorème(s) d'incomplétude de Gödel" ...

[Joe Cool]

Post by Jean-marc

Post by Joe Cool
C'est le cas, sauf chez les mauvais (ou les vieux) programmeurs.

Sauf avec les langages qui n'ont pas de mécanismes d'exception,
de try-catch, etc.

Il faut être vieux (ou mauvais) pour rédiger des programmes de haut
niveau en assembleur, en cobol ou en C.

Post by Jean-marc
Dans ce cas, le "goto avec contraintes" (une seule étiquette de saut
par fonction, saut toujours en avant, goto utilisé seulement
pour de la gestion d'erreur) est une bonne pratique, courante.

La bonne pratique est de changer de langage quand le langage est mauvais.

Post by Jean-marc
On a déjà évoqué le sujet ici même et la conclusion était la
même pour à peu près tous : il vaut mieux un "bon goto" qu'un
code à profondeur d'indentation ridicule.

Je suppose que «tous» fait référence aux vieux programmeurs en retraite
qui ont du temps à perdre dans les fora.

Post by Jean-marc
Finalement, peu de personnes ont réellement compris ce qu'avait
voulu dire Dijkstra dans son article et on le cite à tort et à
travers, un peu comme les gens qui n'y connaissent rien en maths
se gargarisent en citant le(s) "théorème(s) d'incomplétude de Gödel" ...

Dijkstra était très claire, aussi limpide que d'appeler un chat un chat.
Quand il dit «pas de goto», ça signifie «pas de goto».

[Vincent Guichard]

Post by Joe Cool

Post by Jean-marc

Post by Joe Cool
C'est le cas, sauf chez les mauvais (ou les vieux) programmeurs.

Sauf avec les langages qui n'ont pas de mécanismes d'exception,
de try-catch, etc.

Il faut être vieux (ou mauvais) pour rédiger des programmes de haut
niveau en assembleur, en cobol ou en C.

Tous les programmes ne sont pas forcement "des programmes de haut
niveau". Et on n'a pas forcement accès à un langage plus évolué que le C
(Des fois on est même heureux que le seul langage disponible "ressemble"
à du C).

Ensuite je ne pense pas être vieux, mais il est probable que je sois
mauvais ^^.

Vincent Guichard

[Joe Cool]

Post by Vincent Guichard
Tous les programmes ne sont pas forcement "des programmes de haut
niveau".

Dans ce cas on se les réserve soit comme langage cible d'un compilateur,
soit pour hacker les machines à laver.

Post by Vincent Guichard
Et on n'a pas forcement accès à un langage plus évolué que le C
(Des fois on est même heureux que le seul langage disponible "ressemble"
à du C).

Quel est le rapport avec l'algorithmique? Est-ce la fautre de Dijkstra
si votre environnement de travail est pourri?

[Jean-marc]

Post by Joe Cool

Post by Vincent Guichard
Tous les programmes ne sont pas forcement "des programmes de haut
niveau".

Dans ce cas on se les réserve soit comme langage cible d'un
compilateur, soit pour hacker les machines à laver.

Post by Vincent Guichard
Et on n'a pas forcement accès à un langage plus évolué que le C
(Des fois on est même heureux que le seul langage disponible
"ressemble" à du C).

Quel est le rapport avec l'algorithmique? Est-ce la fautre de Dijkstra
si votre environnement de travail est pourri?

Tout le monde savait que tu étais le plus gros troll de fr.sci.maths, tu
prouves aujourd'hui que tu es un prétendant sérieux sur ce groupe
ci également, hélas.

une seule conclusion, donc : "Casse toi, pauv' con".

[Jérôme Benoit]

Post by Jean-marc
Tout le monde savait que tu étais le plus gros troll de fr.sci.maths, tu
prouves aujourd'hui que tu es un prétendant sérieux sur ce groupe ci
également, hélas.

Dire que je venais faire un petit tour peinard pour me reposer et
apprendre éventuellement deux ou trois choses ... C'est plus du troll là,
c'est une suite d'inepties alignées en rang d'oignons, un peu comme
l'abécédaire de "L'art d'avoir toujours raison" de notre ami Arthur
Schopenhauer en mode accéléré de mise en application ...

Je vais mettre à jour mon killfile :)

a +.

[Paul Gaborit]

À (at) 30 Apr 2010 19:13:43 GMT,
Jérôme Benoit <***@grenouille.com> écrivait (wrote):
[...]

Post by Jérôme Benoit
Je vais mettre à jour mon killfile :)

Juste pour savoir : lequel ou lesquels des participants à cette enfilade
avez-vous placés dans votre killfile ?

[Jérôme Benoit]

Post by Paul Gaborit

Post by Jérôme Benoit
Je vais mettre à jour mon killfile :)

Juste pour savoir : lequel ou lesquels des participants à cette enfilade
avez-vous placés dans votre killfile ?

Un certain Joe qui en plus d'être incompétent et pas Cool du tout :)

a +.

[Paul Gaborit]

À (at) 01 May 2010 13:42:49 GMT,

Post by Paul Gaborit

Post by Jérôme Benoit
Je vais mettre à jour mon killfile :)

Juste pour savoir : lequel ou lesquels des participants à cette enfilade
avez-vous placés dans votre killfile ?

Un certain Joe qui en plus d'être incompétent est pas Cool du tout :)

J'aurais sans aucun doute fait le même choix si j'utilisais un
killfile. ;-)

[Joe Cool]

Post by Jérôme Benoit

Post by Paul Gaborit
Juste pour savoir : lequel ou lesquels des participants à cette enfilade
avez-vous placés dans votre killfile ?

Un certain Joe qui en plus d'être incompétent et pas Cool du tout :)

En ce qui vous concerne, pour un Jérôme, vous êtes plutôt benoît,
une sorte de Ravi de la Crèche: vous ne doutez de rien. Quant à
ma compétence, elle repose sur l'exactitude des travaux que j'ai
cités pour appuyer mes dires; autrement dit, pour vous, la grande
majorité des articles de recherche sont de la foutaise. Même pas...
Je crois plutôt que vous n'y comprenez rien, et quitte à choisir
un camp, il vaut mieux choisir le plus peuplé.

[Paul Gaborit]

À (at) Fri, 07 May 2010 16:24:28 +0200,

Quant à ma compétence, elle repose sur l'exactitude des travaux que
j'ai cités pour appuyer mes dires;

Concernant l'utilisation d'un algorithme de tri pour mélanger un
tableau, auriez-vous quelques références à nous citer pour tenter de
justifier vos allégations ?

PS: un article scientifique n'est pas vérité par essence...

[Jérôme Benoit]

Post by Paul Gaborit

Quant à ma compétence, elle repose sur l'exactitude des travaux que
j'ai cités pour appuyer mes dires;

Concernant l'utilisation d'un algorithme de tri pour mélanger un
tableau, auriez-vous quelques références à nous citer pour tenter de
justifier vos allégations ?

Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)
Complexité d'un shuffle : O(n)

Bref, ce Joe est un âne gravement atteint d'une enflure du cerveau près
de la zone de l'égo (qui doit pas être loin de la zone de l'intelligence
et qui doit l'étouffer depuis trop longtemps).

Don't feed the troll please, pretty please.

a +.

[Joe Cool]

Post by Jérôme Benoit
Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)

Il y a des fonctions de tri de complexité linéaire.

[Paul Gaborit]

À (at) Tue, 11 May 2010 11:33:43 +0200,

Post by Joe Cool

Post by Jérôme Benoit
Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)

Il y a des fonctions de tri de complexité linéaire.

Références ?

[JKB]

Le 11-05-2010, ? propos de
Re: Question hyper-basique,

Post by Paul Gaborit
À (at) Tue, 11 May 2010 11:33:43 +0200,

Post by Joe Cool

Post by Jérôme Benoit
Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)

Il y a des fonctions de tri de complexité linéaire.

Références ?

Ouaips, ça m'intéresse, justement, j'ai des listes chaînées de plus
de sept millions de maillons à trier !...

JKB

[xtof.pernod]

Post by JKB
Le 11-05-2010, ? propos de
Re: Question hyper-basique,

Post by Paul Gaborit
À (at) Tue, 11 May 2010 11:33:43 +0200,

Post by Joe Cool

Post by Jérôme Benoit
Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)

Il y a des fonctions de tri de complexité linéaire.

C'est un peu court, jeune homme..
Je tiens le pari sur un tri en O(1) =)

Post by JKB

Post by Paul Gaborit
Références ?

Des tris sans comparaison, en O(N) : (de mémoire et en 'franglais')
. counting sort (tri par comptage ?), histogram sort
. bead sort (tri par boulier vertical (??))
. radix sort (tri par "radicelles" (????))
. bucket sort (tri par (?) emplacements)
. etc.

Tous ont des contraintes, ce qui fait qu'il ne sont pas applicables
dans le cas général, comme quick-sort par ex.

Pour les références, l'omnisciente Wikipedia doit en regorger.

Post by JKB
Ouaips, ça m'intéresse, justement, j'ai des listes chaînées de plus
de sept millions de maillons à trier !...

Peux-tu donner un peu plus de détails sur la clé de tri / le
critère de comparaison, et sur ce qui motive l'utilisation
de liste chainée ?..

Post by JKB
JKB

[Comité de lecture et d'analyse des conneries usenettiques d'éléphant Man Ze clown]

Bonsoir,

"xtof.pernod" <***@NOSPAM.free.fr> a �crit dans le message de news: 4beb0ed3$0$27572$***@reader.news.orange.fr...
| Le 11/05/2010 12:17, JKB a fait rien qu' écrire :
| > Le 11-05-2010, ? propos de
| > Re: Question hyper-basique,
| > Paul Gaborit ?crivait dans fr.comp.algorithmes :

| >> ? (at) Tue, 11 May 2010 11:33:43 +0200,
| >> Joe Cool<***@free.fr> écrivait (wrote):

| >>> Jér´me Benoit a écrit :
| >>>> Complexité moyenne pour faire un tri : O(nlog(n)) (mªme avec
une
| >>>> récursion terminale)

| >>> Il y a des fonctions de tri de complexité linéaire.

| C'est un peu court, jeune homme..
| Je tiens le pari sur un tri en O(1) =)


| >> Références ?

| Des tris sans comparaison, en O(N) : (de mémoire et en 'franglais')
| . counting sort (tri par comptage ?), histogram sort
| . bead sort (tri par boulier vertical (??))
| . radix sort (tri par "radicelles" (????))
| . bucket sort (tri par (?) emplacements)
| . etc.

| Tous ont des contraintes, ce qui fait qu'il ne sont pas applicables
| dans le cas général, comme quick-sort par ex.

| Pour les références, l'omnisciente Wikipedia doit en regorger.


| > Ouaips, §a m'intéresse, justement, j'ai des listes cha®nées de
plus
| > de sept millions de maillons trier !...


| Peux-tu donner un peu plus de détails sur la clé de tri / le
| crit¨re de comparaison, et sur ce qui motive l'utilisation
| de liste chainée ?..


| > JKB


| --
| Christophe.

[Paul Gaborit]

À (at) Wed, 12 May 2010 22:25:06 +0200,

Post by xtof.pernod

Post by Paul Gaborit

Post by Joe Cool
Il y a des fonctions de tri de complexité linéaire.

Références ?

Des tris sans comparaison, en O(N) : (de mémoire et en 'franglais')
. counting sort (tri par comptage ?), histogram sort
. bead sort (tri par boulier vertical (??))
. radix sort (tri par "radicelles" (????))
. bucket sort (tri par (?) emplacements)
. etc.

Merci. Je connaissais.

Post by xtof.pernod
Tous ont des contraintes, ce qui fait qu'il ne sont pas applicables
dans le cas général, comme quick-sort par ex.

Ce ne sont donc pas des fonctions générales de tri : elles ne peuvent
s'utiliser que dans des cas très particuliers. Par conséquent, elles ne
peuvent évidement pas servir à mélanger un tableau comme demandé
initialement.

J'attends donc toujours le nom de l'agorithme de tri qui réponde aux
exigences de Joe Cool et qui garantisse un ordre final aléatoire et
équiréparti si on lui fournit une fonction de comparaison totalement
aléatoire. (S'il était en O(n) ce serait la cerise sur le gateau mais
n'en demandons pas trop pour l'instant.)

[xtof.pernod]

Post by Paul Gaborit
À (at) Wed, 12 May 2010 22:25:06 +0200,

Post by xtof.pernod

Post by Joe Cool
Il y a des fonctions de tri de complexité linéaire.

[JKB:]
Références ?

Des tris sans comparaison, en O(N) : (de mémoire et en 'franglais')
. counting sort (tri par comptage ?), histogram sort
. bead sort (tri par boulier vertical (??))
. radix sort (tri par "radicelles" (????))
. bucket sort (tri par (?) emplacements)
. etc.

Merci. Je connaissais.

Ah.. bah c'est bien.

JKB voulait des réferences, c'est juste quelques pistes.
Mais ça a pas l'air de coller bien avec son cas.

Post by Paul Gaborit

Post by xtof.pernod
Tous ont des contraintes, ce qui fait qu'il ne sont pas applicables
dans le cas général, comme quick-sort par ex.

Ce ne sont donc pas des fonctions générales de tri : elles ne peuvent
s'utiliser que dans des cas très particuliers. Par conséquent, elles ne
peuvent évidement pas servir à mélanger un tableau comme demandé
initialement.

Euh.. oui, c'est pas en gros ce que j'ai dit ?
Le post initial ayant été répondu dès le 2eme ou 3eme coup, on
s'est un peu enfoncé dans des considérations "drosophiliennes".

Le problème est sympa, mais l'ambiance quelque peu tendue, non..?

Post by Paul Gaborit
J'attends donc toujours le nom de l'agorithme de tri qui réponde aux
exigences de Joe Cool et qui garantisse un ordre final aléatoire et
équiréparti si on lui fournit une fonction de comparaison totalement
aléatoire.

(à qui, au tri, ou à Joe ? =)

Bon, si on admet un générateur pseudo-aléatoire extérieur au tri,
on peut toujours comparer la valeur courante (du tableau) à celle
retournée par le générateur. Franchement aberrant pour la
"question hyper basique" du début.

Sinon: on peut toujours comparer les valeurs "à l'envers" en retournant
les bits (sur 8 bits: 12 devient 02, 1 devient 128, etc.), ou en
passant par des S-boxes (boites de substitution)?

Inconvénient : pour 2 tableaux triés identiques, les tableaux
mélangés seront identiques aussi..

Post by Paul Gaborit
(S'il était en O(n) ce serait la cerise sur le gateau mais
n'en demandons pas trop pour l'instant.)

Il n'y a pas de tri par comparaison en O(N), par définition.
C'est donc pas une cerise que tu demandes, mais l'impossible.

Quant à l'existance d'une fonction "totalement aléatoire"..

[Jérôme Benoit]

Il n'y a pas de tri par comparaison en O(N), par définition. C'est donc
pas une cerise que tu demandes, mais l'impossible.

Il voudrait que l'ami Joe étaye ses allégations sur l'utilisation d'un
tri par comparaison pour mélanger un tableau, le mélange résultant doit
être équi-réparti.

Sur le plan de la performance, on sait déjà que c'est une méthode qui
vaut rien pour mélanger un tableau mais si au moins l'absence de biais
pouvait être étayé par une implémentation ou une démonstration qui lui
donnerait un minimum de crédibilité, parce que pour le moment, çà n'en a
aucune :)

a +.

[xtof.pernod]

Post by Jérôme Benoit

Il n'y a pas de tri par comparaison en O(N), par définition. C'est donc
pas une cerise que tu demandes, mais l'impossible.

Il voudrait que l'ami Joe étaye ses allégations sur l'utilisation d'un
tri par comparaison pour mélanger un tableau, le mélange résultant doit
être équi-réparti.

Apparemment, il est parti en vacances, le sujet l'intéresse plus, ou
alors il est fort occupé depuis ce jeudi (?)..

Post by Jérôme Benoit
Sur le plan de la performance, on sait déjà que c'est une méthode qui
vaut rien pour mélanger un tableau mais si au moins l'absence de biais

Oui, oui, mais attends, on doit pouvoir faire pire !

Post by Jérôme Benoit
pouvait être étayé par une implémentation ou une démonstration qui lui
donnerait un minimum de crédibilité, parce que pour le moment, çà n'en a
aucune :)

Ok.. je reprends le truc:


Proposition: il existe un algorithme, basé sur un tri de complexité
linéaire (O(N)), qui mélange un tableau trié donné en entrée.

Elements:
. soit N le nombre d'éléments du tableau,
. K le nombre de bits de la clé de tri
. le "radix sort" ne fait pas de comparaisons directes des éléments
de la table (ex: a[i] <= b[i]), mais des leurs bits ;
. il est de complexité O(N * K), soit O(N)

. il "suffit" de remplacer la fonction qui teste si un bit est positionné
dans une clé par une fonction qui retourne "aléatoirement" 0 ou 1.


Le tableau mélangé sera d'une bonne répartition si & ssi le tableau
d'entrée l'est. (pas plus de garantie que ça, donc..)


Note. la constante cachée dans O(N), du point de vue du nombre de tests,
serait assez conséquente: au moins > 4, si j'en crois ce que j'ai sous
les yeux..



Implémentation: laissée à la discrétion du lecteur/trice interessé(e) =)

Post by Jérôme Benoit
a +.

[xtof.pernod]

Post by Jérôme Benoit

Il n'y a pas de tri par comparaison en O(N), par définition. C'est donc
pas une cerise que tu demandes, mais l'impossible.

Il voudrait que l'ami Joe étaye ses allégations sur l'utilisation d'un
tri par comparaison pour mélanger un tableau, le mélange résultant doit
être équi-réparti.

Apparemment, il est parti en vacances, le sujet l'intéresse plus, ou
alors il est fort occupé depuis ce jeudi (?)..

Post by Jérôme Benoit
Sur le plan de la performance, on sait déjà que c'est une méthode qui
vaut rien pour mélanger un tableau mais si au moins l'absence de biais

Oui, oui, mais attends, on doit pouvoir faire pire !

Post by Jérôme Benoit
pouvait être étayé par une implémentation ou une démonstration qui lui
donnerait un minimum de crédibilité, parce que pour le moment, çà n'en a
aucune :)

Ok.. je reprends le truc:


Proposition: il existe un algorithme, basé sur un tri de complexité
linéaire (O(N)), qui mélange un tableau trié donné en entrée.

Elements:
. soit N le nombre d'éléments du tableau,
. K le nombre de bits de la clé de tri
. le "radix sort" ne fait pas de comparaisons directes des éléments
de la table (ex: a[i] <= b[i]), mais des leurs bits ;
. il est de complexité O(N * K), soit O(N)

. il "suffit" de remplacer la fonction qui teste si un bit est positionné
dans une clé par une fonction qui retourne "aléatoirement" 0 ou 1.


Le tableau mélangé sera d'une bonne répartition si & ssi le tableau
d'entrée l'est. (pas plus de garantie que ça, donc..)


Note. la constante cachée dans O(N), du point de vue du nombre de tests,
serait assez conséquente: au moins > 4, si j'en crois ce que j'ai sous
les yeux..



Implémentation: laissée à la discrétion du lecteur/trice interessé(e) =)

Post by Jérôme Benoit
a +.

[Paul Gaborit]

À (at) Fri, 14 May 2010 13:30:00 +0200,

Post by xtof.pernod
Le problème est sympa, mais l'ambiance quelque peu tendue, non..?

Non, l'ambiance est bonne. ;-)

On rigole beaucoup lorsque Joe Cool vient nous affirmer qu'on peut
mélanger correctement un tableau en utilisant une fonction de tri avec
une fonction de comparaison aléatoire.

On rigole un peu plus lorsqu'on lui fait remarquer que, même si sa
méthode fonctionnait, elle serait inefficace puisqu'en O(n log(n)) alors
qu'on peut faire un mélange efficace en O(n) et qu'il répond en évoquant
les fonctions de tri en O(n) (qui ne sont pas applicables dans sa
pseudo-méthode de mélange puisqu'elles n'utilisent pas de fonctions de
comparaison).

On rigole encore plus lorsqu'il vient nous dire que nous sommes tous des
moutons qui ne comprenons rien à rien alors que lui s'appuie sur des
écrits scientifiques irréprochables qui ne sont évidemment pas à notre
portée mais qu'il est toujours incapable de produire la moindre
référence concernant sa pseudo-méthode de mélange.

Post by xtof.pernod

J'attends donc toujours le nom de l'algorithme de tri qui réponde aux
exigences de Joe Cool et qui garantisse un ordre final aléatoire et
équiréparti si on lui fournit une fonction de comparaison totalement
aléatoire.

(à qui, au tri, ou à Joe ? =)

:-)

C'est bien au tri qu'on fournit une fonction de comparaison aléatoire et
c'est bien de Joe Cool qu'on attend une réponse.

Post by xtof.pernod

(S'il était en O(n) ce serait la cerise sur le gateau mais
n'en demandons pas trop pour l'instant.)

Il n'y a pas de tri par comparaison en O(N), par définition.
C'est donc pas une cerise que tu demandes, mais l'impossible.

C'est ce qu'on essayait de rappeler à Joe Cool et c'est là qu'il a
évoqué les fonctions de tri en O(n). C'est pour cela que je lui
demandais des références, histoire de rigoler encore un peu.

Post by xtof.pernod
Quant à l'existence d'une fonction "totalement aléatoire"..

Je reconnais mon erreur : le "totalement" n'a pas de sens. On est
aléatoire ou pas. Et sur les machines on est toujours pseudo-aléatoire
sauf à disposer d'un mécanisme aléatoire externe.

[xtof.pernod]

Post by Paul Gaborit
À (at) Fri, 14 May 2010 13:30:00 +0200,

Post by xtof.pernod
Le problème est sympa, mais l'ambiance quelque peu tendue, non..?

Non, l'ambiance est bonne. ;-)

Oui, oui -- c'est vrai, on s'amuse bien !..

Post by Paul Gaborit
(...)
On rigole encore plus lorsqu'il vient nous dire que nous sommes tous des
moutons qui ne comprenons rien à rien alors que lui s'appuie sur des (...)

Là, je lui laisse la responsabilité de ses propos..

Post by Paul Gaborit

Post by xtof.pernod

J'attends donc toujours le nom de l'algorithme de tri qui réponde aux
exigences de Joe Cool et qui garantisse un ordre final aléatoire et
équiréparti si on lui fournit une fonction de comparaison totalement
aléatoire.

(à qui, au tri, ou à Joe ? =)

:-)
C'est bien au tri qu'on fournit une fonction de comparaison aléatoire et
c'est bien de Joe Cool qu'on attend une réponse.

Ok..

Post by Paul Gaborit
(...)

Post by xtof.pernod
Quant à l'existence d'une fonction "totalement aléatoire"..

Je reconnais mon erreur : le "totalement" n'a pas de sens. On est

Pas de problème.. il existe des fonctions qui génèrent des
nombres extrêmement bien répartis, et qui font même "mieux",
selon certaines mesures statistiques que des flux garantis
"aléatoires".

Le soucis, c'est de définir une fonction qui permette de dire:
"ça est aléatoire / bien réparti" ou "ça est pas".. Surtout
si le nombre de valeurs est (trop) petit.

Sinon, on pourrait se ramener à un truc du genre:

int alea() {
return 3; /* obtenu par un lancer de dé non biaisé */
}

Va prouver que c'est pas aléatoire..

Post by Paul Gaborit
aléatoire ou pas. Et sur les machines on est toujours pseudo-aléatoire
sauf à disposer d'un mécanisme aléatoire externe.

WoH PinaisE ! Il va dégainer une interface avec une machine qui mesure
les désintégrations atomiques pour mélanger le tableau[ N ] !...

[Paul Gaborit]

À (at) Sun, 16 May 2010 14:07:05 +0200,

Post by xtof.pernod
Pas de problème.. il existe des fonctions qui génèrent des
nombres extrêmement bien répartis, et qui font même "mieux",
selon certaines mesures statistiques que des flux garantis
"aléatoires".

Un flux réellement aléatoire n'est que rarement bien réparti...

Post by xtof.pernod
"ça est aléatoire / bien réparti" ou "ça est pas".. Surtout
si le nombre de valeurs est (trop) petit.
int alea() {
return 3; /* obtenu par un lancer de dé non biaisé */
}
Va prouver que c'est pas aléatoire..

(Si c'est un dé que ne comporte que des faces à 3 points, pourquoi
pas...)

Mouais... Ce n'est pas avec ce genre de fonctions qu'on va épater les
crypanalystes ou les tenants des méthodes de Monte-Carlo (deux domaines
où la qualité des générateurs aléatoires est prépondérante mais pas pour
les mêmes raisons).

Post by xtof.pernod

Post by Paul Gaborit
aléatoire ou pas. Et sur les machines on est toujours pseudo-aléatoire
sauf à disposer d'un mécanisme aléatoire externe.

WoH PinaisE ! Il va dégainer une interface avec une machine qui mesure
les désintégrations atomiques pour mélanger le tableau[ N ] !...

Est-il utile d'avoir de l'aléatoire véritable plutôt que du
pseudo-aléatoire pour mélanger un tableau ? Cela dépend de l'enjeu et,
là, il n'est pas précisé.

[xtof.pernod]

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

??? Je suis pas sur de te suivre, là..

pour un échantillon suffisamment grand, la répartition tend vers
l'équilibre. Sinon ça implique qu'il y a des fréquences.


Mais si tu peux me montrer un fichier "réellement" aléatoire,
et pas bien réparti, ça m'interesse. J'ai une moulinette à aiguiser..

Post by Paul Gaborit

Post by xtof.pernod
(...)
int alea() {
return 3; /* obtenu par un lancer de dé non biaisé */
}
Va prouver que c'est pas aléatoire..

(Si c'est un dé que ne comporte que des faces à 3 points, pourquoi
pas...)

Un dé à 6 faces identiques, un compteur de désintégrations atomique,
3 ratons laveur, t'es sacrément équipé, dis-donc..

Post by Paul Gaborit
Mouais... Ce n'est pas avec ce genre de fonctions qu'on va épater les
crypanalystes ou les tenants des méthodes de Monte-Carlo (deux domaines

^^^^^^^^^^^^^
cryptologues (ou cryptographes), peut-être ?..
les crypanalystes, ils bossent rarement avec des PRNG..

Post by Paul Gaborit
où la qualité des générateurs aléatoires est prépondérante mais pas pour
les mêmes raisons).
(...)
Est-il utile d'avoir de l'aléatoire véritable plutôt que du
pseudo-aléatoire pour mélanger un tableau ? Cela dépend de l'enjeu et,
là, il n'est pas précisé.

Voui.. je pense que l'O.P est très content avec les 2, 3 premières
réponses (en tout cas point n'a-t-il dit le contraire=).

++,

[Paul Gaborit]

À (at) Mon, 17 May 2010 22:27:15 +0200,

Post by xtof.pernod

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

??? Je suis pas sur de te suivre, là..
pour un échantillon suffisamment grand, la répartition tend vers
l'équilibre. Sinon ça implique qu'il y a des fréquences.

Prenons l'exemple d'une pièce de monnaie. Il est très rare qu'une série
de tirages comporte autant de pile que de face. Et si on regarde combien
de fois on revient à l'équilibre, on s'aperçoit que plus on augmente le
nombre de tirages et plus la fréquence de retour à l'équilibre
diminue...

Un générateur pseudo-aléatoire qui donnerait souvent des séries de
tirages bien répartis entre pile et face serait suspect... de ne pas
être aléatoire.

Post by xtof.pernod
Mais si tu peux me montrer un fichier "réellement" aléatoire,
et pas bien réparti, ça m'interesse. J'ai une moulinette à aiguiser..

Voir ci-dessus...

Post by xtof.pernod

Post by Paul Gaborit
Mouais... Ce n'est pas avec ce genre de fonctions qu'on va épater les
crypanalystes ou les tenants des méthodes de Monte-Carlo (deux domaines

^^^^^^^^^^^^^
cryptologues (ou cryptographes), peut-être ?..
les crypanalystes, ils bossent rarement avec des PRNG..

Le cryptanalyste s'attaque toujours au maillon le plus faible d'un
cryptosystème. Si c'est le PRNG, il n'hésite pas. J'ai souvenir d'une
certaine version de netscape dont les flux chiffrés via SSL étaient
facilement décryptables à cause d'un bug d'implémentation du PRNG (à
l'époque, les clés étaient limitées à 40 bits).

[xtof.pernod]

Post by Paul Gaborit
À (at) Mon, 17 May 2010 22:27:15 +0200,

Post by xtof.pernod

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

??? Je suis pas sur de te suivre, là..
pour un échantillon suffisamment grand, la répartition tend vers
l'équilibre. Sinon ça implique qu'il y a des fréquences.

Prenons l'exemple d'une pièce de monnaie. Il est très rare qu'une série
de tirages comporte autant de pile que de face. Et si on regarde combien
de fois on revient à l'équilibre, on s'aperçoit que plus on augmente le
nombre de tirages et plus la fréquence de retour à l'équilibre
diminue...

Ah ouais.. vu sous cet angle.
Très fin. Je vais tester ça.

Pendant que j'y suis, tu aurais la formule qui donne le nombre
théorique de passages par la ligne 1/2 en fonction de N (nbre
d'échatillons) ?

Post by Paul Gaborit
Un générateur pseudo-aléatoire qui donnerait souvent des séries de
tirages bien répartis entre pile et face serait suspect... de ne pas
être aléatoire.

je suis pas totalement convaincu. pour moi la moyenne va tendre assez
vite (pour un flux bien réparti) vers 1/2 +/- epsillon(N), et de là
à en déduire que ceci || cela..

Post by Paul Gaborit

Post by xtof.pernod

Post by Paul Gaborit
Mouais... Ce n'est pas avec ce genre de fonctions qu'on va épater les
crypanalystes ou les tenants des méthodes de Monte-Carlo (deux domaines

^^^^^^^^^^^^^
cryptologues (ou cryptographes), peut-être ?..
les crypanalystes, ils bossent rarement avec des PRNG..

Le cryptanalyste s'attaque toujours au maillon le plus faible d'un
cryptosystème.

En général, c'est l'être humain =)

Post by Paul Gaborit
Si c'est le PRNG, il n'hésite pas. J'ai souvenir d'une

S'il fait de la crypto avec un PRNG, je suis pas sûr qu'il
mérite le titre de cryptographe..

Post by Paul Gaborit
certaine version de netscape dont les flux chiffrés via SSL étaient
facilement décryptables à cause d'un bug d'implémentation du PRNG (à
l'époque, les clés étaient limitées à 40 bits).

Pas franchement un bug, ça marchait.. Mais ils initialisaient le
PRNG avec très peu d'entropie / des valeurs facilement prédictibles
(le nombre d'unités disk, la taille mémoire, des trucs comme ça
je crois..)

[Etienne Rousee]

Post by xtof.pernod

Post by Paul Gaborit
À (at) Mon, 17 May 2010 22:27:15 +0200,

Post by xtof.pernod

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

??? Je suis pas sur de te suivre, là..
pour un échantillon suffisamment grand, la répartition tend vers
l'équilibre. Sinon ça implique qu'il y a des fréquences.

Prenons l'exemple d'une pièce de monnaie. Il est très rare qu'une série
de tirages comporte autant de pile que de face. Et si on regarde combien
de fois on revient à l'équilibre, on s'aperçoit que plus on augmente le
nombre de tirages et plus la fréquence de retour à l'équilibre
diminue...

Ah ouais.. vu sous cet angle.
Très fin. Je vais tester ça.
Pendant que j'y suis, tu aurais la formule qui donne le nombre
théorique de passages par la ligne 1/2 en fonction de N (nbre
d'échatillons) ?

Post by Paul Gaborit
Un générateur pseudo-aléatoire qui donnerait souvent des séries de
tirages bien répartis entre pile et face serait suspect... de ne pas
être aléatoire.

je suis pas totalement convaincu. pour moi la moyenne va tendre assez
vite (pour un flux bien réparti) vers 1/2 +/- epsillon(N), et de là
à en déduire que ceci || cela..

Lire: "Pile ou Face" d'Emmannuel Lesigne, paru en 2001 chez Ellipses.
(une centaine de pages)

[xtof.pernod]

Post by Etienne Rousee

Post by Paul Gaborit
À (at) Mon, 17 May 2010 22:27:15 +0200,

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

(...)

Un générateur pseudo-aléatoire qui donnerait souvent des séries de
tirages bien répartis entre pile et face serait suspect... de ne pas
être aléatoire.

En effet: la moyenne du nombre d'échantillons nécessaires pour que la
moyenne des échantillons franchisse la moyenne théorique (1/2 dans ce
cas) diverge d'autant plus rapidement que l'agitation du flux d'entrée
est "artificielle" (cryptée, compressée, prng..), que si c'est un flux
"réellement aléatoire"..

Ca en fait une bonne mesure discriminative. Bien le merci.

Post by Etienne Rousee
Lire: "Pile ou Face" d'Emmannuel Lesigne, paru en 2001 chez Ellipses.
(une centaine de pages)

Merci pour la ref'..

Sinon, rien de tel qu'un bout de code (une soixantaine de lignes) pour
s'autoconvaincre ;)

[Pascal J. Bourguignon]

Post by xtof.pernod

Post by Etienne Rousee

Post by Paul Gaborit
À (at) Mon, 17 May 2010 22:27:15 +0200,

Post by Paul Gaborit
(...)
Un flux réellement aléatoire n'est que rarement bien réparti...

(...)

Un générateur pseudo-aléatoire qui donnerait souvent des séries de
tirages bien répartis entre pile et face serait suspect... de ne pas
être aléatoire.

En effet: la moyenne du nombre d'échantillons nécessaires pour que la
moyenne des échantillons franchisse la moyenne théorique (1/2 dans ce
cas) diverge d'autant plus rapidement que l'agitation du flux d'entrée
est "artificielle" (cryptée, compressée, prng..), que si c'est un flux
"réellement aléatoire"..
Ca en fait une bonne mesure discriminative. Bien le merci.

Post by Etienne Rousee
Lire: "Pile ou Face" d'Emmannuel Lesigne, paru en 2001 chez Ellipses.
(une centaine de pages)

Merci pour la ref'..
Sinon, rien de tel qu'un bout de code (une soixantaine de lignes) pour
s'autoconvaincre ;)

Soixante lignes? Tu programme en assembleur?

(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

[Jérôme Benoit]

Post by Pascal J. Bourguignon
Soixante lignes? Tu programme en assembleur?

C'est un pur :)

Post by Pascal J. Bourguignon
(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

Je me demande par pure curiosité intellectuelle ce que çà donnerait en
mixant plusieurs source de PRNG ... en haskell c'est facilement
implémentable avec Random.split.

a +.

[xtof.pernod]

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
Soixante lignes? Tu programme en assembleur?

Que nenni, mon bon :

~/cd# wc -l cmf.c
65 cmf.c

Post by Jérôme Benoit
C'est un pur :)

Oui, en fait, '.C', c'est du C0B0L (langage très 'pur' s'il en est =)

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

ah oui, mais, hé, t'as pas le nombre de fois où la moyenne calculée
croise la moyenne théorique (0.5) !

ex: (mt est le prng 'mersenne twister',
== comp10 est 10Mo de flux compressé par lpaq8,
bits.60 vient du 'Marsaglia Random Number CDROM',
tea est le 'tiny encryption algorithm')

~/cd# mt 50000 | cmf
(...) pos: longueur somme moyennes
268284724: 13 -> 1394.8 ; x = 14794.57 : 18810.24
268284725: 1 -> 18134.0 ; x = 14793.75 : 18810.01
268284726: 1 -> 18135.0 ; x = 14792.94 : 18809.79
268284727: 1 -> 18136.0 ; x = 14792.12 : 18809.57
# final: 6892.1361 => 0.000017

~/cd# cmf < comp10
155574754: 1 -> 28889.0 ; x = 5385.07 : 3467.55
155574755: 1 -> 28890.0 ; x = 5384.89 : 3467.61
# final: 3467.6119 => 0.000022

~/cd# mt 50000 | tea 0x098137018 | cmf
136121150: 1 -> 7909.0 ; x = 17208.74 : 15602.28
136121159: 9 -> 878.9 ; x = 17206.57 : 15602.48
136121160: 1 -> 7911.0 ; x = 17204.39 : 15602.68
# final: 4485.8273 => 0.000011

~/cd# cat *.c | cmf
000001: 1 -> 0.0 ; x = 1.00 : 1.00
000006: 5 -> 0.2 ; x = 3.00 : 2.00
000017: 11 -> 0.2 ; x = 5.67 : 3.22
# final: 3.2222 =)

~/cd# cmf < files/rnd0/bits.60
77409657: 1 -> 5182.0 ; x = 14935.30 : 23945.35
77409658: 1 -> 5183.0 ; x = 14932.42 : 23943.61
77409667: 9 -> 576.0 ; x = 14929.54 : 23941.87
# final: 23941.8705 / 80000000 => 0.000299

Avec ça, on voit clairement que la moyenne globale est
d'autant plus petite que le flux d'entrée est artificiellement
"agité".

Sauf pour -surprise- le texte, ou ça "bloque" très vite en
crachant une valeur ridiculement bas.

Post by Jérôme Benoit
Je me demande par pure curiosité intellectuelle ce que çà donnerait en
mixant plusieurs source de PRNG ...

Mixer : par ou exclusif, entrelacement, 4eme dimension, ou autre..?

Post by Jérôme Benoit
en haskell c'est facilement
implémentable avec Random.split.

Cool, en cobol c'est plus chaud..

Post by Jérôme Benoit
a +.

[JKB]

Le 19-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
Soixante lignes? Tu programme en assembleur?

C'est un pur :)

Post by Pascal J. Bourguignon
(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

Je me demande par pure curiosité intellectuelle ce que çà donnerait en
mixant plusieurs source de PRNG ... en haskell c'est facilement
implémentable avec Random.split.

Chic un concours ;-)

#!/usr/local/bin/rpl -scp

RD
<<
{ "borosh13" "cmrg" "coveyou" "fishman18" "fishman20" "fishman2x"
"gfsr4" "knuthran" "knuthran2" "knuthran2002" "lecuyer21" "minstd"
"mrg" "mt19937" "mt19937_1998" "mt19937_1999" "r250" "ran0"
"ran1" "ran2" "ran3" "rand" "rand48" "random_bsd" "random_glibc2"
"random_libc5" "random128_bsd" "random128_glibc2" "random128_libc5"
"random256_bsd" "random256_glibc2" "random256_libc5" "random32_bsd"
"random32_glibc2" "random32_libc5" "random64_bsd" "random64_glibc2"
"random64_libc5" "random8_bsd" "random8_glibc2" "random8_libc5"
"randu" "ranf" "ranlux" "ranlux389" "ranlxd1" "ranlxd2" "ranlxs0"
"ranlxs1" "ranlxs2" "ranmar" "slatec" "taus" "taus113" "taus2"
"transputer" "tt800" "uni" "uni32" "vax" "waterman14" "zuf" }
1
-> GEN POSITION
<<
cls

1 1000000 for I
if
I 1000 mod 1 same
then
GEN POSITION get dup disp rdgn
POSITION incr GEN size mod 1 + 'POSITION' sto
rand s+
ns mean 2 ->list disp
else
rand s+
end
next

ns mean 2 ->list disp
Bon, c'est du goret-codage tout ce qu'il y a de plus sous-optimal,
mais c'est fait en 5 minutes sur un coin de table, et en évitant les
dérives numériques dues au calcul de la moyenne. Dans le programme
proposé plus haut, je ne suis pas sûr que la somme

(loop for i from 0 to 1e6 sum (random 1.0) into s

soit faite dans les règles de l'art, c'est-à-dire en sommant les
nombres du plus petit vers le plus grand.

Résultat :

...
{ 324001
0.499929666258953 }
...
random8_libc5
{ 361001
0.500055614694412 }
...
{ 448001
0.500336379198361 }
random256_glibc2
{ 449001
0.500332235992291 }
random32_bsd
{ 450001
0.500345894738089 }
random32_libc5
{ 451001
0.500336354630807 }
random64_glibc2
{ 452001
0.500357423152803 }
random8_bsd
{ 453001
0.500361602562264 }
random8_libc5
{ 454001
0.500340119956777 }
ranf
{ 455001
0.500304132972317 }
ranlux389
{ 456001
0.500324225031746 }
ranlxd2
{ 457001
0.500340350959623 }
ranlxs1
{ 458001
0.50034482631729 }
ranmar
{ 459001
0.500358943477625 }
taus
{ 460001
0.500383140460758 }
taus2
{ 461001
0.50039528570526 }
tt800
{ 462001
0.50038539017121 }
uni32
{ 463001
0.500378677095937 }
waterman14
{ 464001
0.500348716358563 }
borosh13
{ 465001
0.50035710505251 }
coveyou
{ 466001
0.500350425372611 }
fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

JKB

[xtof.pernod]

Le 19-05-2010, à propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
Soixante lignes? Tu programme en assembleur?

C'est un pur :)

Post by Pascal J. Bourguignon
(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))

C'est vrai que c'est court et élégant..

Mais ça donne pas de réponse à la question -- au demeurant
fort mal posée, je reconnais, j'ai un mal de chien..

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

Je me demande par pure curiosité intellectuelle ce que çà donnerait en
mixant plusieurs source de PRNG ... en haskell c'est facilement
implémentable avec Random.split.

#!/usr/local/bin/rpl -scp
(...)

la vaaache.. j'ai rien compris.

...
random8_libc5
{ 361001
0.500055614694412 }
...

(...)

Qu'est-ce tu voulais montrer ? que tes prng tendent tous
vers 1/2, avec une précision de 3 ou 4 décimales ?..

fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
Est-ce que ça corrige les défauts de la version précédente ?

Est-ce que ça 'tricrémente' la variable (incrément, bicrément, ...) spécifiée ?

</mode troll=off>

JKB

[JKB]

Le 20-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),

Post by xtof.pernod

Post by JKB
#!/usr/local/bin/rpl -scp
(...)

la vaaache.. j'ai rien compris.

Post by JKB
...
random8_libc5
{ 361001
0.500055614694412 }
...

(...)
Qu'est-ce tu voulais montrer ? que tes prng tendent tous
vers 1/2, avec une précision de 3 ou 4 décimales ?..

Je voulais juste gagner le concours ;-)

Post by xtof.pernod

Post by JKB
fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
Est-ce que ça corrige les défauts de la version précédente ?

Naon !... C'est un SIGINT envoyé depuis le clavier et le programme
répond : "+++Interruption". Faudrait voir à suivre un peu !

Post by xtof.pernod
Est-ce que ça 'tricrémente' la variable (incrément, bicrément, ...) spécifiée ?
</mode troll=off>

Post by JKB
JKB

[xtof.pernod]

Post by JKB
Le 20-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),

Post by xtof.pernod
(...)

Post by JKB
#!/usr/local/bin/rpl -scp

Désolé, nous ne faisons pas cet article n'est pas en stock.

Post by JKB

Post by xtof.pernod
(...)
Qu'est-ce tu voulais montrer ? que tes prng tendent tous
vers 1/2, avec une précision de 3 ou 4 décimales ?..

Je voulais juste gagner le concours ;-)

Hein ?! quel concours ?
Pinaise, on me dit jamais rien à moi..

Post by JKB

Post by xtof.pernod

Post by JKB
fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
Est-ce que ça corrige les défauts de la version précédente ?

Naon !... C'est un SIGINT envoyé depuis le clavier et le programme
répond : "+++Interruption". Faudrait voir à suivre un peu !

Quel programme ? Le tien, où y'a pas 1 gramme de gestion de signaux,
ou l'interpréteur de language de type "write-only", style Liste Infinie
de Stupides Parenthèses [traduction approx. & à l'arrache de :
"Lot of Insipid and Stupid Parenthesis", c'est pas moi kill édit]

<mode je_me_fais_des_amis = "off" />

Post by JKB

Post by xtof.pernod
(...)

Post by JKB
JKB

Naaaan, je déc*nne ..... Respect à tous les languages que les
machines daignent avaler, pour peu qu'elles soyent à peu près
bien programmées.

[JKB]

Le 20-05-2010, ? propos de
Re: Super-fête à Toire (Fût: Re: Question hyper-basique),

Post by xtof.pernod

Post by JKB
Le 20-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),

Post by xtof.pernod
(...)

Post by JKB
#!/usr/local/bin/rpl -scp

Désolé, nous ne faisons pas cet article n'est pas en stock.

Post by JKB

Post by xtof.pernod
(...)
Qu'est-ce tu voulais montrer ? que tes prng tendent tous
vers 1/2, avec une précision de 3 ou 4 décimales ?..

Je voulais juste gagner le concours ;-)

Hein ?! quel concours ?
Pinaise, on me dit jamais rien à moi..

Post by JKB

Post by xtof.pernod

Post by JKB
fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
Est-ce que ça corrige les défauts de la version précédente ?

Naon !... C'est un SIGINT envoyé depuis le clavier et le programme
répond : "+++Interruption". Faudrait voir à suivre un peu !

Quel programme ? Le tien, où y'a pas 1 gramme de gestion de signaux,
ou l'interpréteur de language de type "write-only", style Liste Infinie
"Lot of Insipid and Stupid Parenthesis", c'est pas moi kill édit]

C'est un _compilateur_, et j'aime assez ce genre de langage
'write-only'.

Post by xtof.pernod
<mode je_me_fais_des_amis = "off" />

Gagné :-P

Post by xtof.pernod

Post by JKB

Post by xtof.pernod
(...)

Post by JKB
JKB

Naaaan, je déc*nne ..... Respect à tous les languages que les
machines daignent avaler, pour peu qu'elles soyent à peu près
bien programmées.

C'est pour ça que j'utilise _mes_ bugs et pas ceux des autres. J'ai
assez fait dans ma vie de bugs reports pour arrêter de jouer avec
ça.

JKB

[Pascal J. Bourguignon]

Post by Jérôme Benoit

Post by Pascal J. Bourguignon
Soixante lignes? Tu programme en assembleur?

C'est un pur :)

Post by Pascal J. Bourguignon
(loop for i from 0 to 1e6 sum (random 1.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.54622734)
(100 0.49565795)
(1000 0.49771202)
(10000 0.5013775)
(100000 0.4994311)
(1000000 0.5000529)

Je me demande par pure curiosité intellectuelle ce que çà donnerait en
mixant plusieurs source de PRNG ... en haskell c'est facilement
implémentable avec Random.split.

Avec la fonction rand() de unix:

(loop for i from 0 to 1e6 sum (/ (linux:random) 2147483648.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.6423787)
(100 0.5499566)
(1000 0.5072906)
(10000 0.49707523)
(100000 0.49986368)
(1000000 0.50000274)
NIL

Mais ça ne veut rien dire, on obtient aussi des séquences comme:

-->
(10 0.4914257)
(100 0.51135695)
(1000 0.5026758)
(10000 0.49963745)
(100000 0.49932718)
(1000000 0.4999366)
NIL


Il y a des livres entiers sur l'analyse des pseudo-aléatoires.

[Joe Cool]

Post by Paul Gaborit
Prenons l'exemple d'une pièce de monnaie. Il est très rare qu'une série
de tirages comporte autant de pile que de face. Et si on regarde combien
de fois on revient à l'équilibre, on s'aperçoit que plus on augmente le
nombre de tirages et plus la fréquence de retour à l'équilibre
diminue...

Les probabilités sont basées sur les rapports de mesures, pas sur les
mesures absolues. Ce que vous dites est aussi vrai que stupide, sauf
sur un point: ce n'est pas la fréquence de retour à l'équilibre qui
diminue, mais la fréquence de retour à l'origine.

[Joe Cool]

Post by Paul Gaborit
Un flux réellement aléatoire n'est que rarement bien réparti...

Alors qu'on flux qui n'est pas aléatoire a plus de chance de l'être...

[Joe Cool]

Post by Paul Gaborit
J'attends donc toujours le nom de l'agorithme de tri qui réponde aux
exigences de Joe Cool et qui garantisse un ordre final aléatoire et
équiréparti si on lui fournit une fonction de comparaison totalement
aléatoire.

Déjà fait. Lisez l'historique du newsgroup.

Mais je me doute bien que même si je vous le mettais sous le
nez, vous prétendriez ne pas l'avoir vu. Alors je ne me fatiguerai
pas pour vous.

[JKB]

Le 12-05-2010, ? propos de
Re: Question hyper-basique,

Post by xtof.pernod

Post by JKB
Le 11-05-2010, ? propos de
Re: Question hyper-basique,

Post by Paul Gaborit
À (at) Tue, 11 May 2010 11:33:43 +0200,

Post by Joe Cool

Post by Jérôme Benoit
Complexité moyenne pour faire un tri : O(nlog(n)) (même avec une
récursion terminale)

Il y a des fonctions de tri de complexité linéaire.

C'est un peu court, jeune homme..
Je tiens le pari sur un tri en O(1) =)

Post by JKB

Post by Paul Gaborit
Références ?

Des tris sans comparaison, en O(N) : (de mémoire et en 'franglais')
. counting sort (tri par comptage ?), histogram sort
. bead sort (tri par boulier vertical (??))
. radix sort (tri par "radicelles" (????))
. bucket sort (tri par (?) emplacements)
. etc.
Tous ont des contraintes, ce qui fait qu'il ne sont pas applicables
dans le cas général, comme quick-sort par ex.
Pour les références, l'omnisciente Wikipedia doit en regorger.

Post by JKB
Ouaips, ça m'intéresse, justement, j'ai des listes chaînées de plus
de sept millions de maillons à trier !...

Peux-tu donner un peu plus de détails sur la clé de tri / le
critère de comparaison, et sur ce qui motive l'utilisation
de liste chainée ?..

Des métriques de toponymie avec un critère de vraisemblance par code
postal. Ça tient très mal dans un tableau statique pour un certain
nombre de raisons complexes.

JKB

[xtof.pernod]

Post by JKB

Post by xtof.pernod

Post by JKB
(...)
Ouaips, ça m'intéresse, justement, j'ai des listes chaînées de plus
de sept millions de maillons à trier !...

Peux-tu donner un peu plus de détails sur la clé de tri / le
critère de comparaison, et sur ce qui motive l'utilisation
de liste chainée ?..

Des métriques de toponymie avec un critère de vraisemblance par code
postal.

Ah ouais.. quand même !

Bon, si la clé de tri est le code postal (supposition), ca tient sur
17 bits : il doit bien avoir un tri en O(N) qui s'applique.

counting / histogram, ou radix, peut-être. A voir..

http://www.itl.nist.gov/div897/sqg/dads/HTML/rapidSort.html
http://fr.wikipedia.org/wiki/Tri_comptage

Post by JKB
Ça tient très mal dans un tableau statique pour un certain
nombre de raisons complexes.

Ahah. Mais un tableau peut être alloué dynamiquement, pour peu que tu aies
une idée du nombre maxi d'éléments, et sachant que la gestion de la liste
'consommme' 7.000.000 de pointeurs = ~28Mo sur une machine 32 bits.

De plus, si tu la maintiens en ordre en insérant les éléments à leur
place, ça fait un tri en O(N^2), à moins que j'ai loupé une marche..

D'où l'intérêt d'un tri en O(N) !

Post by JKB
JKB

Non ?..

[JKB]

Le 14-05-2010, ? propos de
Re: Question hyper-basique,

Post by xtof.pernod

Post by JKB

Post by xtof.pernod

Post by JKB
(...)
Ouaips, ça m'intéresse, justement, j'ai des listes chaînées de plus
de sept millions de maillons à trier !...

Peux-tu donner un peu plus de détails sur la clé de tri / le
critère de comparaison, et sur ce qui motive l'utilisation
de liste chainée ?..

Des métriques de toponymie avec un critère de vraisemblance par code
postal.

Ah ouais.. quand même !
Bon, si la clé de tri est le code postal (supposition), ca tient sur
17 bits : il doit bien avoir un tri en O(N) qui s'applique.

Non. Le tri n'est pas sur le code postal, mais sur un critère de
vraisemblance qui prend en compte _entre autres_ le code postal.
Trier les codes postaux, je sais faire, d'autant plus que la liste
est bornée. Là, je trie mes éléments en fonction d'un critère qui
dépend de la requête passée en entrée.

Post by xtof.pernod
counting / histogram, ou radix, peut-être. A voir..
http://www.itl.nist.gov/div897/sqg/dads/HTML/rapidSort.html
http://fr.wikipedia.org/wiki/Tri_comptage

Post by JKB
Ça tient très mal dans un tableau statique pour un certain
nombre de raisons complexes.

Ahah. Mais un tableau peut être alloué dynamiquement, pour peu que tu aies
une idée du nombre maxi d'éléments, et sachant que la gestion de la liste
'consommme' 7.000.000 de pointeurs = ~28Mo sur une machine 32 bits.
De plus, si tu la maintiens en ordre en insérant les éléments à leur
place, ça fait un tri en O(N^2), à moins que j'ai loupé une marche..
D'où l'intérêt d'un tri en O(N) !

Post by JKB
JKB

Non ?..

Sauf que je suis en 64 bits (la taille de l'exécutable données
comprises est supérieure à 2 Go) et que j'effectue plusieurs calculs
simultanément. Lorsque je lance un processus de calcul, un par
processeur de la machine, j'occupe déjà plus de 10 Go de mémoire (32
processeurs sur la machine, et ce n'est pas du x86).

JKB

[Joe Cool]

Post by Paul Gaborit
Concernant l'utilisation d'un algorithme de tri pour mélanger un
tableau, auriez-vous quelques références à nous citer pour tenter de
justifier vos allégations ?

Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

Post by Paul Gaborit
PS: un article scientifique n'est pas vérité par essence...

Dans ce cas, qu'est-ce qui vous apporte autant de suffisance?
La douce chaleur du troupeau?

[Paul Gaborit]

À (at) Tue, 11 May 2010 11:36:43 +0200,

Post by Joe Cool

Post by Paul Gaborit
Concernant l'utilisation d'un algorithme de tri pour mélanger un
tableau, auriez-vous quelques références à nous citer pour tenter de
justifier vos allégations ?

Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

Dea arguments sont certes présentés mais sans aucune référence ni même
esquisse de preuve... Et les contre-exemples n'ont pas été examinés (ni
même peut-être compris).

Post by Joe Cool

Post by Paul Gaborit
PS: un article scientifique n'est pas vérité par essence...

Dans ce cas, qu'est-ce qui vous apporte autant de suffisance ?

Quelle "suffisance" ?

Post by Joe Cool
La douce chaleur du troupeau?

Mais de quoi parlez-vous ?

[Joe Cool]

Post by Paul Gaborit

Post by Joe Cool
Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

Dea arguments sont certes présentés mais sans aucune référence ni même
esquisse de preuve...

Pas de bol: les esquisses sont là; mais il faut vouloir les lire et pouvoir
les comprendre. Évidemment, on ne peut pas faire boire un âne qui n'a pas soif...

Post by Paul Gaborit
Et les contre-exemples n'ont pas été examinés (ni
même peut-être compris).

En effet, les auteurs des «contre-exemples» n'ont rien compris.

[xtof.pernod]

^^^^^^^^
Tiens, t'es là, toi ?... Tu manquais pas.

T'en as fini, avec les goto, les maths, ta science infuse etc ?

Post by Joe Cool

Post by Paul Gaborit

Post by Joe Cool
Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

Dea arguments sont certes présentés mais sans aucune référence ni même
esquisse de preuve...

Pas de bol: les esquisses sont là;

^^
Où ça, exactement ? Là ? ------------------->
Ta précision est aussi grande que ta modestie.

Post by Joe Cool
mais il faut vouloir les lire et pouvoir
les comprendre. Évidemment, on ne peut pas faire boire un âne qui n'a pas soif...

En clair: "Je dis que la preuve existe, dém**dez vous pour
la trouver, sinon c'est que vous être trop c*ns".

Qu'est-ce que c'est constructif..


Sur sa copie, Jo Cool à mis : "Je sais q'une preuve existe".
Son professeur de maths lui a mis 20 (+ O(1)).

Post by Joe Cool

Post by Paul Gaborit
Et les contre-exemples n'ont pas été examinés (ni
même peut-être compris).

En effet, les auteurs des «contre-exemples» n'ont rien compris.

héééé oui... dure leçon de la vie, petit: "Seul JC a tout compris".


[Le pire, c'est qu'il y a un début de preuve de l'existence
d'un algo. qui utilise un tri en O(N) pour mélanger un tableau.
mais c'est tellement crétin que personne n'osera le faire.]

[Jérôme Benoit]

Post by Paul Gaborit
Concernant l'utilisation d'un algorithme de tri pour mélanger un
tableau, auriez-vous quelques références à nous citer pour tenter de
justifier vos allégations ?

Je vais en citer une ... de contre-référence :

http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html

Mais est-ce bien raisonnable de ma part ? ;-)

a +.

[Joe Cool]

Post by Jérôme Benoit
http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
Mais est-ce bien raisonnable de ma part ? ;-)

Non, ce n'est pas raisonnable. Cette «référence» a été citée dans
la discussion initiale et j'y ai répondu comme il se doit.

En résumé, le «calcul» douteux effectué par l'auteur du blog montre:
- soit que l'implémentation du tri testé est foireuse, ce qui ne remet
pas en cause la méthode, seulement la tentative de l'utiliser;
- soit que les outils statistiques utilisés sont foireux, ce qui remet
en cause la rigueur et l'intérêt de votre source.

Des calculs pseudo-aléatoires... Mais les preuves, où sont-elles?
Savent-ils au moins ce qu'est une preuve?

[Pascal J. Bourguignon]

Post by Joe Cool

Post by Jean-marc

Post by Joe Cool
C'est le cas, sauf chez les mauvais (ou les vieux) programmeurs.

Sauf avec les langages qui n'ont pas de mécanismes d'exception,
de try-catch, etc.

Il faut être vieux (ou mauvais) pour rédiger des programmes de haut
niveau en assembleur, en cobol ou en C.

Post by Jean-marc
Dans ce cas, le "goto avec contraintes" (une seule étiquette de saut
par fonction, saut toujours en avant, goto utilisé seulement
pour de la gestion d'erreur) est une bonne pratique, courante.

La bonne pratique est de changer de langage quand le langage est mauvais.

Post by Jean-marc
On a déjà évoqué le sujet ici même et la conclusion était la
même pour à peu près tous : il vaut mieux un "bon goto" qu'un
code à profondeur d'indentation ridicule.

Je suppose que «tous» fait référence aux vieux programmeurs en retraite
qui ont du temps à perdre dans les fora.

Post by Jean-marc
Finalement, peu de personnes ont réellement compris ce qu'avait
voulu dire Dijkstra dans son article et on le cite à tort et à
travers, un peu comme les gens qui n'y connaissent rien en maths
se gargarisent en citant le(s) "théorème(s) d'incomplétude de Gödel" ...

Dijkstra était très claire, aussi limpide que d'appeler un chat un chat.
Quand il dit «pas de goto», ça signifie «pas de goto».

Le fait d'être jeune n'excuse pas la méconnaissance des règles de base
de la grammaire (Dijkstra était un monsieur), ni l'histoire de
l'informatique. D'autant plus que même en ayant eu une éducation
lamentable (ce n'est pas de votre faute, mais pensez à voter pour des
politiciens proposant de libérer l'éducation pour vos enfants et
l'avenir du pays), vous avez la chance de nos jours de pouvoir accéder à
ces connaissances via Internet et le web.

En particulier, l'article du Pr. Edsger W. Dijkstra intitulé "Go To
Statement Considered Harmful" n'est pas intitulé "Interdisons le Go
To". Il mentionne simplement que l'usage de "Go To" peut faire du mal,
et qu'il préfèrerait qu'on l'évite dans les langages de haut niveau.
Mais ceci tient seulement une phrase sur tout un article. En lisant le
reste de l'article, on se rend compte que :

- ce n'est pas seulement le "Go To" qui est mauvais, mais toute
construction syntaxique dont le niveau d'abstraction ne correspond pas
au problème traité (et donc par voie de conséquence que toutes les
instructions de tous les langages peuvent être considérées mauvaise
(selon le niveau d'abstraction requis par le problème à résoudre),
sauf en Lisp oú on a les macros de lisp qui permettent d'introduire
des constructions syntaxiques du niveau d'abstraction voulu).

- ce n'est pas tant l'instructon "Go To" en soi qui est mauvaise,
(puisqu'on peut mécaniquement transformer un programme plein de "Go
To" en programme n'utilisant que des instructions "while"), mais la
façon dont on structure le programme. (Bien sur, si on a un langage
qui ne permet pas de créer ses propres abstractions syntaxiques
(parmis les langages connus, seul lisp le permet (Common Lisp, Scheme,
etc), on est bien obligé d'utiliser ce qu'on a. Des méthodes de
programmation comme L.C.P. ont été inventées afin de structurer
proprement un programme en utilisant des "Go To").

"The exercise to translate an arbitrary flow diagram more or less
mechanically into a jump-less one, however, is not to be recommended.
Then the resulting flow diagram cannot be expected to be more
transparent than the original one." -- Dijkstra

[Olivier Miakinen]

Bonjour Pascal,

Le 31/03/2010 11:33, Pascal J. Bourguignon répondait à un vieux troll de

Post by Pascal J. Bourguignon

Post by Joe Cool
Dijkstra était très claire, aussi limpide que d'appeler un chat un chat.
Quand il dit «pas de goto», ça signifie «pas de goto».

Le fait d'être jeune n'excuse pas la méconnaissance des règles de base
de la grammaire (Dijkstra était un monsieur) [...]
[...] que toutes les
instructions de tous les langages peuvent être considérées mauvaise

Hum... quand on reprend quelqu'un sur sa grammaire, il vaut mieux ne pas
faire d'erreur du même genre dans le même article.

De toute manière, pourquoi déterrer ce troll vieux de trois semaines ?

Post by Pascal J. Bourguignon
[...]
sauf en Lisp oú on a les macros de lisp qui permettent [...]
[...] (Bien sur, si on a un langage
qui ne permet pas [...]
[...] seul lisp le permet [...]

Ah oui, bien sûr, c'est parce que tu voulais troller toi aussi ! Ok, ok.

[suivi adapté]

[Joe Cool]

Post by Pascal J. Bourguignon

Post by Joe Cool
Dijkstra était très claire, aussi limpide que d'appeler un chat un chat.
Quand il dit «pas de goto», ça signifie «pas de goto».

Le fait d'être jeune n'excuse pas la méconnaissance des règles de base
de la grammaire (Dijkstra était un monsieur), ni l'histoire de
l'informatique.

Puisque vous maîtrisez à la perfection la science des imbéciles, vous
remarquerez avec quelle aisance je manie l'ellipse: la pensée de Dijkstra
s'accorde effectivement au féminin.

Maintenant que la civilisation est sauvée, passons aux détails.

Post by Pascal J. Bourguignon
En particulier, l'article du Pr. Edsger W. Dijkstra intitulé "Go To
Statement Considered Harmful" n'est pas intitulé "Interdisons le Go
To". Il mentionne simplement que l'usage de "Go To" peut faire du mal,
et qu'il préfèrerait qu'on l'évite dans les langages de haut niveau.

Vous glosez pour sauver le goto; mais Dijkstra ne peut pas être plus clair
en disant que le goto est très dangereux: il faut être stupide ou
malfaisant pour utiliser le goto. Effectivement, Dijksra n'interdit pas
la stupidité, sinon vous ne seriez pas là.

Post by Pascal J. Bourguignon
- ce n'est pas seulement le "Go To" qui est mauvais, mais toute
construction syntaxique dont le niveau d'abstraction ne correspond pas
au problème traité

Dijkstra parle du goto et c'est tout. Ne changez pas de sujet.

Post by Pascal J. Bourguignon
- ce n'est pas tant l'instructon "Go To" en soi qui est mauvaise,
(puisqu'on peut mécaniquement transformer un programme plein de "Go
To" en programme n'utilisant que des instructions "while"), mais la
façon dont on structure le programme.

Quand Dijkstra a publié sont pamphlet, dans les années 60, le goto n'admettait
aucune sémantique formelle. Encore aujourd'hui, personne ne sait interpréter
le goto de manière satisfaisante dans la logique de Floyd-Hoare, encore moins
dans une autre logique: des meilleurs que vous se sont vautrés en tentant de le
faire. Le fait est que personne n'est actuellement capable de définir ce qu'est
un programme correct en présence de goto, et les quelques formalisations qui
semblent fonctionner sont un cauchemar à utiliser. Seul un abruti fini peut
s'imaginer programmer correctement avec des goto.

Je vous conseille d'aller immédiatement réclamer le prix Turing qui vous
revient de droit pour votre clairvoyance.

[debug this fifo]

Post by Joe Cool
un programme correct en présence de goto, et les quelques formalisations qui
semblent fonctionner sont un cauchemar à utiliser. Seul un abruti fini peut
s'imaginer programmer correctement avec des goto.

keywords : "datamation, comefrom"

désolé, j'ai un jour de retard.

[Joe Cool]

Post by debug this fifo

Post by Joe Cool
un programme correct en présence de goto, et les quelques
formalisations qui semblent fonctionner sont un cauchemar à
utiliser. Seul un abruti fini peut s'imaginer programmer
correctement avec des goto.

keywords : "datamation, comefrom"
désolé, j'ai un jour de retard.

Je dirais même quelques milliers d'années de retard.
Les informaticiens en sont encore au stade chamanique,
à vénérer les «wizards» et à juger la qualité des
programmes à l'aide de considérations esthétiques.

Le goto est objectivement dangereux car la notion de
«bon» usage du goto n'existe pas actuellement: c'est
un cadre informel basé sur le talent supposé des
informaticiens, chacun d'eux se croyant assez bon pour
défier trois mille ans de mathématiques.

Il n'y a pas pire qu'une bande de médiocres incapables
d'appréhender leur propre médiocrité.

[Wykaaa]

Post by Joe Cool

Post by debug this fifo

Post by Joe Cool
un programme correct en présence de goto, et les quelques
formalisations qui semblent fonctionner sont un cauchemar à
utiliser. Seul un abruti fini peut s'imaginer programmer
correctement avec des goto.

keywords : "datamation, comefrom"
désolé, j'ai un jour de retard.

Je dirais même quelques milliers d'années de retard.
Les informaticiens en sont encore au stade chamanique,
à vénérer les «wizards» et à juger la qualité des
programmes à l'aide de considérations esthétiques.
Le goto est objectivement dangereux car la notion de
«bon» usage du goto n'existe pas actuellement: c'est
un cadre informel basé sur le talent supposé des
informaticiens, chacun d'eux se croyant assez bon pour
défier trois mille ans de mathématiques.
Il n'y a pas pire qu'une bande de médiocres incapables
d'appréhender leur propre médiocrité.

Je ne veux pas poursuivre la polémique mais il faut tout de même, pour
être tout à fait complet sur le sujet, lire cet article. D'accord, il
date de 1974 mais il n'a pas été écrit par n'importe qui...

Donald Knuth " Structured programming with goto statement" paru en
décembre 1974 dans la revue de l'ACM, Computing Survey.
C'est là : pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf

[Joe Cool]

Post by Wykaaa
Je ne veux pas poursuivre la polémique mais il faut tout de même, pour
être tout à fait complet sur le sujet, lire cet article. D'accord, il
date de 1974 mais il n'a pas été écrit par n'importe qui...
Donald Knuth " Structured programming with goto statement" paru en
décembre 1974 dans la revue de l'ACM, Computing Survey.
C'est là : pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf

Pourquoi est-ce vrai? Parce que Knuth l'a dit. L'argument ad hominen,
voilà le seul mode de pensée maîtrisé par les médiocres. Le document,
une succession d'exemples ad hoc et de conseils de grand mère, n'a
absolument aucun intérêt.

Pour Knuth, le summum de la programmation structurée c'est l'assembleur
macro-expansé; on n'en attend pas moins d'un type ayant fait ses classes
à l'époque des cartes perforées.

[Etienne Rousee]

Post by Joe Cool

Post by Wykaaa
Je ne veux pas poursuivre la polémique mais il faut tout de même, pour
être tout à fait complet sur le sujet, lire cet article. D'accord, il
date de 1974 mais il n'a pas été écrit par n'importe qui...

C'est vrai.

Post by Joe Cool
Pourquoi est-ce vrai? Parce que Knuth l'a dit.

Il ne lui donne pas raison, il dit seulement que c'est article est digne
d'intérêt, et c'est historiquement exact, qu'on soit d'accord
ou non.

Post by Joe Cool
L'argument ad hominen,
voilà le seul mode de pensée maîtrisé par les médiocres. Le document,
une succession d'exemples ad hoc et de conseils de grand mère, n'a
absolument aucun intérêt.

Que ce soit votre avis n'est pas une preuve.

Post by Joe Cool
Pour Knuth, le summum de la programmation structurée c'est l'assembleur
macro-expansé; on n'en attend pas moins d'un type ayant fait ses classes
à l'époque des cartes perforées.

Etes vous capable de faire mieux ? Prouvez le.

Vous avez amplement démontré votre capacité de dénigration et votre
volonté de destruction.
Nous aimerions voir une démonstration de votre capacité de construction.

Je ne sais pas si j'en suis moi même capable, mais j'ai l'humilité de ne
pas le prétendre.

[Joe Cool]

Post by Etienne Rousee
Etes vous capable de faire mieux ? Prouvez le.

Je n'ai pas envie de faire un concours de bite avec vous.

Post by Etienne Rousee
Vous avez amplement démontré votre capacité de dénigration et votre
volonté de destruction. Nous aimerions voir une démonstration de
votre capacité de construction.

Je ne peux détruire ce qui n'existe pas. J'apporte la connaissance de
ce qui est et de ce qui n'est pas; mais on ne saurait faire boire un
âne qui n'a pas soif.

Post by Etienne Rousee
Je ne sais pas si j'en suis moi même capable, mais j'ai l'humilité de
ne pas le prétendre.

Vous avez l'humilité de vous cacher derrière vos maîtres. Habituellement,
ça porte un autre nom.

[Bertrand Lenoir-Welter]

Seul un abruti fini peut s'imaginer programmer correctement
avec des goto.

Je dois vivre dans un monde largement peuplé d'abrutis. Mais ça me
semble préférable à un monde peuplé d'intégristes pétris de dogmes et
jetant leurs anathèmes. Au moins, on se parle d'égal à égal.

Ceci dit, je dois être un abruti amateur : dans un projet de plus de 450
000 lignes de code, je n'utilise que 4 goto - que je pourrais certes
remplacer par une enfilade de if() histoire de rendre le code moins
lisible et moins performant, mais certes plus plaisant aux yeux d'un
ayatollah s'il venait à en passer un.

Par contre, j'utilise beaucoup les return, qui ne sont jamais que des
goto masqués. Est-ce que l'aiguille de votre abrutimètre remonte ?

[Joe Cool]

Post by Bertrand Lenoir-Welter

Seul un abruti fini peut s'imaginer programmer correctement avec
des goto.

Je dois vivre dans un monde largement peuplé d'abrutis.

C'est exact.

Post by Bertrand Lenoir-Welter
Mais ça me semble préférable à un monde peuplé d'intégristes pétris
de dogmes et jetant leurs anathèmes.

Face à la science du savant, l'abruti n'a pas d'autre choix que
de croire: sans possibilité de comprendre, il accepte ou rejette
avec la même naïveté. Pour l'abruti, il n'y a pas de bon ni de
mauvais, ni de vrai, ni de faux: tout se vaut. Son jugement se
limite à ces facultés partagés avec les grands singes: d'un côté
il a ses potes, les gentils qui répètent la même chose que lui,
et de l'autre les méchants, dogmatiques forcément.

Post by Bertrand Lenoir-Welter
Au moins, on se parle d'égal à égal.

Tout abruti préfère les abrutis aux savants, c'est évident.

[Pascal J. Bourguignon]

Post by Joe Cool

Post by Pascal J. Bourguignon

Post by Joe Cool
Dijkstra était très claire, aussi limpide que d'appeler un chat un chat.
Quand il dit «pas de goto», ça signifie «pas de goto».

Le fait d'être jeune n'excuse pas la méconnaissance des règles de base
de la grammaire (Dijkstra était un monsieur), ni l'histoire de
l'informatique.

Puisque vous maîtrisez à la perfection la science des imbéciles, vous
remarquerez avec quelle aisance je manie l'ellipse: la pensée de Dijkstra
s'accorde effectivement au féminin.
Maintenant que la civilisation est sauvée, passons aux détails.

Post by Pascal J. Bourguignon
En particulier, l'article du Pr. Edsger W. Dijkstra intitulé "Go To
Statement Considered Harmful" n'est pas intitulé "Interdisons le Go
To". Il mentionne simplement que l'usage de "Go To" peut faire du mal,
et qu'il préfèrerait qu'on l'évite dans les langages de haut niveau.

Vous glosez pour sauver le goto; mais Dijkstra ne peut pas être plus clair
en disant que le goto est très dangereux: il faut être stupide ou
malfaisant pour utiliser le goto. Effectivement, Dijksra n'interdit pas
la stupidité, sinon vous ne seriez pas là.

Le coeur de l'article de Dijsktra est:

[...] our intellectual powers are rather geared to master static
relations and that our powers to visualize processes evolving in time
are relatively poorly developed. For that reason we should do (as
wise programmers aware of our limitations) our utmost to shorten the
conceptual gap between the static program and the dynamic process, to
make the correspondence between the program (spread out in text
space) and the process (spread out in time) as trivial as possible.

Ça ne concerne pas que le "Go To", et ça montre clairement qu'il peut y
avoir des situations oú un "Go To" peut être indiqué.

Post by Joe Cool

Post by Pascal J. Bourguignon
- ce n'est pas seulement le "Go To" qui est mauvais, mais toute
construction syntaxique dont le niveau d'abstraction ne correspond pas
au problème traité

Dijkstra parle du goto et c'est tout. Ne changez pas de sujet.

Non. Voir le paragraphe cité ci-dessus.

Post by Joe Cool

Post by Pascal J. Bourguignon
- ce n'est pas tant l'instructon "Go To" en soi qui est mauvaise,
(puisqu'on peut mécaniquement transformer un programme plein de "Go
To" en programme n'utilisant que des instructions "while"), mais la
façon dont on structure le programme.

Quand Dijkstra a publié sont pamphlet, dans les années 60, le goto n'admettait
aucune sémantique formelle.

Tout processeur explicite une sémantique formelle. Elle peut ne pas
satisfaire les besoins esthétiques des mathématiciens, mais elle est
aussi valide que n'importe quelle autre formulalisation.

Post by Joe Cool
Encore aujourd'hui, personne ne sait interpréter
le goto de manière satisfaisante dans la logique de Floyd-Hoare, encore moins
dans une autre logique: des meilleurs que vous se sont vautrés en tentant de le
faire. Le fait est que personne n'est actuellement capable de définir ce qu'est
un programme correct en présence de goto, et les quelques formalisations qui
semblent fonctionner sont un cauchemar à utiliser. Seul un abruti fini peut
s'imaginer programmer correctement avec des goto.

Ou avec des while. Je recite l'article de Dijkstra:

In [2] Guiseppe Jacopini seems to have proved the (logical)
superfluousness of the go to statement. The exercise to translate an
arbitrary flow diagram more or less mechanically into a jump-less
one, however, is not to be recommended. Then the resulting flow
diagram cannot be expected to be more transparent than the original
one.

Post by Joe Cool
Je vous conseille d'aller immédiatement réclamer le prix Turing qui vous
revient de droit pour votre clairvoyance.

[Joe Cool]

Post by Pascal J. Bourguignon
[...] our intellectual powers are rather geared to master static
relations and that our powers to visualize processes evolving in time
are relatively poorly developed. For that reason we should do (as
wise programmers aware of our limitations) our utmost to shorten the
conceptual gap between the static program and the dynamic process, to
make the correspondence between the program (spread out in text
space) and the process (spread out in time) as trivial as possible.
Ça ne concerne pas que le "Go To", et ça montre clairement qu'il peut y
avoir des situations oú un "Go To" peut être indiqué.

Outre le fait que votre citation est hors propos, il est clair que le type
voulant programmer un processeur sans utiliser l'instruction «jump» n'ira
pas bien loin. Mais nous sommes encore hors propos: le code machine n'est pas
un langage de programmation structuré.

Post by Pascal J. Bourguignon

Post by Joe Cool
Dijkstra parle du goto et c'est tout. Ne changez pas de sujet.

Non. Voir le paragraphe cité ci-dessus.

«Go To Statement Considered Harmful»

Tous vos sophismes ne changeront jamais le titre de l'article.

Post by Pascal J. Bourguignon
Tout processeur explicite une sémantique formelle. Elle peut ne pas
satisfaire les besoins esthétiques des mathématiciens, mais elle est
aussi valide que n'importe quelle autre formulalisation.

Vous faites références à une sémantique opérationnelle, non pas formelle.
Les informaticiens ne sont pas stupides au point d'utiliser des langages
de programmation sans pouvoir les exécuter. Mais ils sont ignorants de
la signification des instructions qu'ils manipulent: ils savent comment
exécuter un programme, mais ils sont incapables de savoir ce que calcule
leur programme faute d'une sémantique formelle.

Post by Pascal J. Bourguignon

Post by Joe Cool
Encore aujourd'hui, personne ne sait interpréter
le goto de manière satisfaisante dans la logique de Floyd-Hoare, encore moins
dans une autre logique: des meilleurs que vous se sont vautrés en tentant de le
faire. Le fait est que personne n'est actuellement capable de définir ce qu'est
un programme correct en présence de goto, et les quelques formalisations qui
semblent fonctionner sont un cauchemar à utiliser. Seul un abruti fini peut
s'imaginer programmer correctement avec des goto.

Oui, vous récitez, mais sans comprendre ni même chercher à comprendre.

«Guiseppe Jacopini seems to have proved the (logical) superfluousness
of the go to statement.»

Avez-vous lu l'article de Böhm et Jacopini? Non, bien sûr, sinon vous
auriez remarqué (du moins si vous en aviez les capacités) que:
- l'article précise que c'est impossible en toute généralité: «It is not
possible to decompose all flow diagrams into a finie number of given base
diagrams.»
- des transformations existent, vu qu'un langage équipé de boucles while et
de l'arithmétique de base est Turing-complet, mais elles ne préservent pas
la topologie des flux de données (un exemple typique est la donnée d'un
interpréteur sans goto opérant sur des programmes avec goto).

Ce n'est pas pour rien que Dijkstra évite de se mouiller en disant qu'il «semble»
qu'on puisse remplacer les goto par des while. Dans des articles plus récents,
comme «Eliminating go to's while preserving program structure» de Ramshaw,
l'élimination du goto n'est possible que dans certains cas et l'usage d'une
instruction break reste nécessaire. Toutes les autres tentatives ont également
leurs cas boiteux, et leur complexité dépasse de loin les misérables capacités
cérébrales des informaticiens consommateurs de goto. Quand à la sémantique formelle,
elle brille toujours par son absence: la transformation du goto n'étant pas uniforme,
cette instruction reste dénuée de sens.

[xtof.pernod]

Post by JLH974
Bonjour à tous
Je sais que c'est une question idiote mais j'avoue humblement que je
Comment -avec un algo très simple dont vous avez les secret- générer
toutes les combinaisons à n objets pris parmi une collection de m objets
(m>=n)?
Combinaisons sans répétition et sans ordre (ABC = ACB = CAB etc...)
On sait très facilement calculer combien il y en a mais comment les généger?
JLH La Réunion

Sympatique question, pour un dimanche soir =)

J'avais trouvé cet algo (je ne sais plus où), que je trouve assez
élégant (ma foi), sans goto, sans récursivité, sans plus de 2 niveaux
de boucles imbriquée..

Ca génère les n! permutations possibles des nombres de 0 à n-1, mais
tu dois pouvoir l'adapter à ton cas. (je ne vois pas ce que tu entends
par "sans ordre" ?)


void gen_perm( n )
{
char buf[ MAX_B ];
int i, j;
int f;
int perm;

// nbre de permutations possibles: //
f = factorielle( n );
for (i = 0; i < n; i++)
buf[ i ] = i;

for (perm = 0; perm < f; perm++) {
// a cet endroit, buf[0..n-1] contient //
// la permutation courante : //
faire_qeq_chose( buf, n );

// rech. du plus petit element: //
i = n - 1;
while (buf[ i - 1 ] > buf[ i ])
i--;

// ici, si i < 1, il n'y a plus de //
// permutation possible. (code optionnel) //
if (i < 1)
break;

j = n;
while (buf[ j - 1 ] < buf[ i - 1 ])
j--;

SWAP( buf[ i - 1 ], buf[ j - 1 ] );
i++;
j = n;

while (i < j) {
SWAP( buf[ i - 1 ], buf[ j - 1 ] );
i++;
j--;
}
}
}

Ca donne par ex. ça :

~/$ perm 4
# 0: 0 1 2 3 :
# 1: 0 1 3 2 :
# 2: 0 2 1 3 :
# 3: 0 2 3 1 :
# 4: 0 3 1 2 :
# 5: 0 3 2 1 :
# 6: 1 0 2 3 :
# 7: 1 0 3 2 :
# 8: 1 2 0 3 :
# 9: 1 2 3 0 :
# 10: 1 3 0 2 :
# 11: 1 3 2 0 :
# 12: 2 0 1 3 :
# 13: 2 0 3 1 :
# 14: 2 1 0 3 :
# 15: 2 1 3 0 :
# 16: 2 3 0 1 :
# 17: 2 3 1 0 :
# 18: 3 0 1 2 :
# 19: 3 0 2 1 :
# 20: 3 1 0 2 :
# 21: 3 1 2 0 :
# 22: 3 2 0 1 :
# 23: 3 2 1 0 :


Si ça peut t'aider..