Discussion :

[CliffeCSTL]

Bonjour,

J'ai besoin d'un algorithme qui me génère 'n' nombres aléatoires compris entre 0 et 'N_MAX' et avec un minimum d'écart 'ep_min' entre 2 nombre (Le plus optimiser possible).
Je tiens à préciser que j'ai déjà un algo qui fonctionne et je souhaite l'améliorer
Merci.

[foetus]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define N_MAX 256
 
int main(void)
{
    unsigned short ep_min = 8;
    unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0;
 
    srand( time(NULL) );
 
    last_nb = (1 + rand()% N_MAX);
 
    for(; i < 15000; i++) {
        do {
            count_ite++;
            nb = (1 + rand()% N_MAX);
 
            diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb));
        } while(diff  < ep_min);
 
        if (diff < ep_min) { count++; }
        if (nb > max) { max = nb; }
        if (nb < min) { min = nb; }
        if (diff > max_diff) { max_diff = diff; }
        if (diff < min_diff) { min_diff = diff; }
 
        printf("%d (%d)\n", nb, diff);
 
        last_nb = nb;
    }
 
    printf("Miss: %d - %d%% / %d - %d -> %d - %d, %d", count, ((count * 100) / 15000), count_ite, min, max, min_diff, max_diff);
 
    return 0;
}

Édit: Avec une notion de pages (N_MAX / ep_min) c'est chaud, mais peut-être qu'un forumeur a un algo avec
C'est chaud, parce qu'on connait la dernière page prise et il faut éviter de la reprendre pour le nouveau nombre
Simple, mais:

1. Si le nombre de pages est petit cela complique
2. Il faut contrôler le modulo: % nombre de pages
3. Sans modulo, il faut gérer au moins 3 ou 4 cas: si on veut un nombre avant ou après, si c'est la première ou la dernière page, ...
4. Si la nouvelle page sélectionnée est juste à côté de l'ancienne (juste avant ou juste après), il faut gérer le déplacement de l'ancien nombre dans l'ancienne page (*)

L'algo naïf est très bien surtout si ep_min est petit

* -> |<-Ok: X-><-Not Ok: Y->||<-X->Ancien Nombre<-Y->||<-Not Ok: X-><-Ok: Y->|, avec (X + Y + 1) = ep_min

[Iradrille]

Je tiens à préciser que j'ai déjà un algo qui fonctionne et je souhaite l'améliorer

Hello,

Montres ce que tu as, quelle est la complexité de ton algo ?

L'écart doit être entre 2 nombres consécutifs ? ou 2 nombres générés ?
(Je part du principe que c'est entre 2 nombres générés)

As-tu des contraintes sur n, N_MAX, ep_min ?
si N_MAX - (n*ep_min*2) est petit, il va falloir faire gaffe au choix des nombres aléatoires, un mauvais choix et il n'y à plus de solution possible.


Si tu as N_MAX / n grand et N_MAX / (n*ep_min*2) grand, alors un algo naïf marchera bien. Malgré le temps d'exec non borné tu seras quasiment en O(n).
Algo naïf : générer un nombre, s'il ne convient pas, on en génère un autre, niveau code, quelque chose du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct hash {
	int ep_min2;
 
	bool operator()(int a) const {
		return std::hash(a - (a % ep_min2));
	}
};
 
struct comp {
	int ep_min;
 
	bool operator()(int a, int b) const {
		return std::abs(a-b) < ep_min;
	}
};
 
std::unordered_set<int, hash{ep_min * 2}, comp{ep_min}> nbs(2*n);
 
for(int i=0; i<n; ++i) {
	int nb;
	do {
		nb = rand() % nMax;
	} while(nbs.find(nb) != nbs.end());
	std::cout << nb << endl;
}

(Oui je sais, rand() c'est mal, à remplacer).


Sinon tu peux utiliser un arbre pour stocker les intervalles valides, tu auras un temps d'exec borné en O(n log(n)) (je crois ?)
Par exemple si tu veux générer des nombres entre 0 (inclus) et 100 (exclus), avec ep_min == 5 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
		]-1; 100[ (100%)
			20
 
]-1; 16[ (17.58%)		]24; 100[ (82.42%)

Tu commences avec un seul intervalle : ]-1; 100[, tu as donc 100% de chance d'utiliser cet intervalle. Tu génère un premier nombre : 20
Tu crée 2 intervalles fils et leur attribue leur probabilité d'être utilisés.

Pour chaque nombre à générer, tu effectue un parcours de l'arbre en profondeur en respectant les probabilités de prendre chaque branche.
Dès que tu arrives sur une feuille de l'arbre, tu as ton intervalle final, et tu es sur que le nombre généré sera correct.

Pour éviter que ça se transforme en un algo en O(n²), il faut maintenir un arbre équilibré.

[foetus]

Algo Scolaire:

PS: On peut supprimer quelques variables

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define N_MAX 256
 
int main(void)
{
    unsigned short ep_min = 8;
    unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0;
 
    unsigned short direction = 0, max_N_MAX = (N_MAX - ep_min + 1);
 
    srand( time(NULL) );
 
    last_nb = (1 + rand() % N_MAX);
 
    for(; i < 30000; i++) {
        if (last_nb >= max_N_MAX) {
            nb = (1 + rand() % (last_nb - ep_min));
        } else if (last_nb <= ep_min) {
            nb = (last_nb + ep_min + rand() % (max_N_MAX - last_nb));
        } else {
            direction = (rand() % 2);
 
            if (direction == 1) {
                nb = (last_nb + ep_min + rand() % (max_N_MAX - last_nb));
            } else {
                nb = (1 + rand() % (last_nb - ep_min));
            }
        }
 
        diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb));
 
        if (diff < ep_min) { count++; }
        if (nb > max) { max = nb; }
        if (nb < min) { min = nb; }
        if (diff > max_diff) { max_diff = diff; }
        if (diff < min_diff) { min_diff = diff; }
 
        printf("%d: (%d) - %d\n", nb, diff, direction);
 
        last_nb = nb;
    }
 
    printf("Miss: %d - %d%% / %d - %d -> %d - %d, %d", count, ((count * 100) / 30000), count_ite, min, max, min_diff, max_diff);
 
    return 0;
}

Et celui avec les pages, mais pas optimal

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define N_MAX 256
 
int main(void)
{
    unsigned short ep_min = 8;
    unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0;
    unsigned range = (floor(N_MAX / ep_min) + (((N_MAX % ep_min) != 0)? 1: 0)), current_page = 0, last_page = 0;
 
    srand( time(NULL) );
 
    last_page = (rand() % range);
 
    if (range <= 5) { return 0; }
 
    for(; i < 15000; i++) {
//      range - 3: une de moins pour l'ancienne, et 2 autres pour chaque côté
        current_page = (last_page + 2 + rand() % (range - 3));
        if (current_page >= range) { current_page -= range; }
 
        nb = (current_page * ep_min + (1 + rand() % ep_min));
 
//      Seulement pour tronquer la dernière page si (N_MAX % ep_min) != 0
        if (nb > N_MAX) { nb = N_MAX; }
 
        diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb));
 
        if (diff < ep_min) { count++; }
        if (nb > max) { max = nb; }
        if (nb < min) { min = nb; }
        if (diff > max_diff) { max_diff = diff; }
        if (diff < min_diff) { min_diff = diff; }
 
        printf("%d: %d -> %d (%d)\n", nb, last_page, current_page, diff);
 
        last_nb = nb;
        last_page = current_page;
    }
 
    printf("%d - Miss: %d - %d%% / %d - %d -> %d - %d, %d", range, count, ((count * 100) / 15000), count_ite, min, max, min_diff, max_diff);
 
    return 0;
}

[skeud]

J'ai rapidemment survolé le sujet, tu voudrais un générateur de nombre aléatoire mais lissé? Du style bruit de perlin?

Cette manière permet de généré des nombre aléatoire mais en fesant en sorte que chaque nombre soit lié avec celui qui le précède pour évité les grands écarts. Avec un peu de modification, tu pourrais limiter le MAX et le MIN pour avoir ce que tu veux non?

[Iradrille]

J'ai rapidemment survolé le sujet, tu voudrais un générateur de nombre aléatoire mais lissé? Du style bruit de perlin?

Cette manière permet de généré des nombre aléatoire mais en fesant en sorte que chaque nombre soit lié avec celui qui le précède pour évité les grands écarts. Avec un peu de modification, tu pourrais limiter le MAX et le MIN pour avoir ce que tu veux non?

Justement, il faut un écart > ep_min entre 2 nombres.

[skeud]

Beh tu peux modifier le retour du bruit de perlin pour avoir cet écart, en le relançant tant que tu n'as pas cet écart de respecté non?

[CliffeCSTL]

Mon problème initial c'est de positionner des points sur un cercle aléatoirement en s'arrurant qu'ils sont suffisamment éloigner (un angle minimal de "ep_min" entre 2 points).

[JolyLoic]

Je ne sais pas d'où vient ta contrainte d'espacement minimum, mais selon les cas, une solution hyper simple est de tirer des valeurs comme multiple de cet intervalle minimal. Genre, si c'est 5°, plutôt que de tirer des valeurs entre 0 et 360, tu tires des valeurs entre 0 et 72, et multiplie le résultat par 5...