[Python 3.X] Création de coordonnées aléatoires sans répétition

Version imprimable

Salut à tous !

Je suis actuellement en 1ère année de CPGE et j'ai pour projet de travailler sur un TIPE lié à python, et je rencontre un "petit" problème qui suite à des recherches sur Google, ne semble pas pouvoir se résoudre simplement (du moins, je pense) :?

Du coup voilà ce que je veux faire : créer un tableau contenant NbPt points de coordonnées aléatoires, et leurs coordonnées doivent être toutes différentes les unes des autres (pas de répétition de coordonnées du genre 2 points au même endroit, ni 2 points de mêmes abscisses/ordonnées). La fonction Point est créer , et à priori marche très bien (j'ai vérifier sur plusieurs cours en ligne, ça c'est bon) 8-)

Ce que je n'arrive pas à faire : justement, c'est cette histoire de coordonnées totalement différentes qui n'aboutit pas... J'ai essayé plusieurs méthode et voilà le code qui, selon moi, est le plus aboutit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 import random def Tableau(NbPt): liste=[] for i in range (NbPt): a=random.randint(0,20) b=random.randint(0,20) if a!=b : for i in range (len(liste)): if liste[i]!=a and liste[i]!=b : liste.append(Point(a,b)) return liste
Ici je veux des coordonnées aléatoires comprises entre 0 et 20 ; mais le problème c'est que j'ai ce messages d'erreur (:weird:) :

Citation:

File "H:\TIPE1.py", line 15, in Tableau
if liste[i]!=a and liste[i]!=b :
IndexError: list index out of range

Du coup, semblerait il que je ne puisse pas comparer à chaque fois les coordonnées aux précédentes pour vérifier qu'elles soient non seulement différentes entre elles mais aussi différentes à celles qui les précèdent :calim2:
J'avais également tenter de créer 2 listes de nombres tous différents et d'ensuite piocher dans ces listes avec la fonction "sample" mais pas moyen d'aboutir, j'ai des messages d'erreurs ou alors des points qui ont parfois les mêmes abscisses/ordonnées :aie:

Est ce qu'un petit coup de main serait possible ? :)

Merci d'avance !

EDIT : j'ai oublié de préciser (même si ça pourrait peut être sembler logique pour certains, je sais pas) mais "a" c'est l'abscisse du point et "b" l'ordonnée :)

16/12/2016, 17h17
tbc92

Ton tableau Liste contient des points (c.a.d des couples d'entiers) et non des entiers.
Je verrais donc plutôt :

if liste[i,1] != a and liste[i,2] != b ... mais je ne suis pas sûr du tout de la syntaxe.

Sinon, comme ton nombre de valeurs (21*21) est assez limité, je ferais d'une autre façon :

Etape 1. Tu prépares un tableau de 21x21 couples d'entiers : tous les points possibles (un peu moins peut-être car tu t'interdis les points de la diagonale de ce tableau). Appelons ce tableau complet le catalogue.

Etape 2: Si tu veux X points différents, tu boucles X fois, et à chaque passage , tu sélectionnes aléatoirement 1 des points de ce tableau.
Au 1er passage, tu choisis donc un nombre aléatoire entre 0 et 440, et tu prends l'élément correspondant.
Bien entendu, tu retires ce couple du 'catalogue'
Et au n-ième passage, tu choisis un nombre entre 0 et 440-n (puisqu'il n'y a plus que 441-n points dans le catalogue ), et tu prends ce point.
16/12/2016, 17h56
wiztricks
Salut,

Citation:

Envoyé par BlackShark68

Est ce qu'un petit coup de main serait possible ? :)

Le code que vous montrez ne peut pas produire cette erreur.
Relisez:
Code:

1 2 3 for i in range (len(liste)): if liste[i]!=a and liste[i]!=b : liste.append(Point(a,b))
Comme liste est initialisée à [], len(liste) est 0 et range(0) retournant une liste vide, on entrera jamais dans le corps de la boucle.
nota: si la liste contient des objets Point(a,b), liste[i] sera toujours différents de a et b qui sont "entiers"... liste[i].a et liste[i].b sont peut être les valeurs à tester (mais on ne sait pas comment sont construits ces Points). Vous ajoutez un nouveau Point dans liste autant de fois qu'il y aura de points avec différents dans la liste (et non quand la liste ne contient pas le nouveau candidat...)

Par ailleurs, écrire:
Code:

1 2 3 4 5 6 def Tableau(NbPt): ... for i in range (NbPt): ... for i in range (len(liste)): ...
i.e. utiliser dans une boucle interne le même indice que la boucle externe va peut être fonctionner dans ce cas particulier mais a tendance à créer des effets de bords indésirables (et des comportements difficiles à comprendre).

Enfin réfléchissez un peu, votre fonction est supposée retourner une liste de longueur NbPt, si vous écrivez "for i in range (NbPt):" vous allez essayez d'ajouter NbPt fois... et comme il y aura de mauvais points, à la sortie, la liste sera <= NbPt. Ce n'est pas ce que vous voulez!

Ca fait quand même pas mal de problèmes pour ces quelques lignes de code...

Ne serait-il pas plus "simple" de formuler "tant que la liste ne contient pas NbPt éléments essayons d'ajouter un point..."?

Après côté technique, pour choisir (a, b) distincts dans 0..19 x 0..19, il est plus simple d'écrire:
Code:

1 2 >>> numbers = list(range(0, 20)) >>> random.shuffle(numbers)
i.e. on prend 20 nombres différents, on mélange et on prend les deux premiers:

Code:

>>> ab = numbers[:2]

Par construction, ab[0] et ab[1] sont différents.
Pour tester qu'ils ne sont pas dans liste, on peut utiliser "in":
Code:

1 2 3 >>> if ab not in liste: ... liste.append(ab) ...
In fine, il n'y a plus de boucle "for" qui traînent et comme on ne fait que des .append à la liste, impossible d'avoir des IndexError...

- W

Salut,

Soyons Python, soyons simple.

Code:

1
2
3
4
5
6
7
 
import random
def Tableau(npts):
    points = set()
    while len(points) < npts:
        points.add((random.randint(0,20), random.randint(0,20)))
    return points

Citation:
Envoyé par VinsS
Salut,

Soyons Python, soyons simple.
Code:

1 2 3 4 5 6 7 import random def Tableau(npts): points = set() while len(points) < npts: points.add((random.randint(0,20), random.randint(0,20))) return points
Rien n'exclut la diagonale... N'est ce pas trop simple?

- W

16/12/2016, 23h02
picodev
Bonjour,

Si tu choisis N points P_i de coordonnées entières tels que leurs coordonnées (x_i,y_i) vérifient 0≤x_i<MaxX et 0≤y_i<MaxY avec 0≤i≤N≤min(MaxX,MaxY) alors je pense que le plus simple est de créer une permutation de [0,MaxX[ et une permutation de [0,MaxY[ et de prendre les abscisses dans la première permutation, les ordonnées dans la seconde.
Code:

1 2 3 4 5 abs = list(range(0,MaxX)) ord = list(range(0,MaxY)) random.shuffle(abs) random.shuffle(ord) points = list(zip( abs[:N+1], ord[:N+1]))
17/12/2016, 00h43
VinsS

Citation:

Envoyé par picodev

Bonjour,

Si tu choisis N points P_i de coordonnées entières tels que leurs coordonnées (x_i,y_i) vérifient 0≤x_i<MaxX et 0≤y_i<MaxY avec 0≤i≤N≤min(MaxX,MaxY) alors je pense que le plus simple est de créer une permutation de [0,MaxX[ et une permutation de [0,MaxY[ et de prendre les abscisses dans la première permutation, les ordonnées dans la seconde.

Est-ce que tu te comprends toi-même ?
17/12/2016, 00h49
VinsS

Citation:

Envoyé par wiztricks

Rien n'exclut la diagonale... N'est ce pas trop simple?

- W

Salut wiztricks,

Mon intention n'est, bien sur, pas de réduire à rien le travail de l'OP mais de proposer d'abord le travail principal par la simplicité et puis le détail on verra après.
17/12/2016, 00h56
tbc92

On est sur un forum python, c'est donc bien de montrer la syntaxe python. Si l'OP était intéressé par le côté algorithme, c'est vrai qu'il aurait posé la question sur un forum algorithme.
17/12/2016, 01h17
picodev

Ce que le PO désire :

Citation:

Envoyé par BlackShark68

Du coup voilà ce que je veux faire : créer un tableau contenant NbPt points de coordonnées aléatoires, et leurs coordonnées doivent être toutes différentes les unes des autres (pas de répétition de coordonnées du genre 2 points au même endroit, ni 2 points de mêmes abscisses/ordonnées). La fonction Point est créer , et à priori marche très bien (j'ai vérifier sur plusieurs cours en ligne, ça c'est bon) 8-)

C'est en gros «j'ai un carré et je veux y prendre une liste de plusieurs points. Ces points sont tous différents (pas deux pareils) et en plus aucun point ne partage la même abscisse ou ordonnée qu'un autre point = il est seul sur sa ligne et sur sa colonne».

Citation:

Envoyé par VinsS

Est-ce que tu te comprends toi-même ?

Bah, si tu n'as pas compris mon explication (désolé de parler math) ce n'est pas grave ; je pense que tu auras mieux compris le code python qui répond exactement à la demande du PO. En plus simple c'est une sorte de fisher yates en 2D (désolé de parler algo …).

A priori le code que j'ai donné est le seul qui répond à sa demande en permettant le choix de n'importe quel point de la surface d'origine.
17/12/2016, 10h55
BufferBob

salut,

Citation:

Envoyé par picodev

Si tu choisis N points P_i de coordonnées entières tels que leurs coordonnées (x_i,y_i) vérifient 0≤x_i<MaxX et 0≤y_i<MaxY avec 0≤i≤N≤min(MaxX,MaxY) alors je pense que le plus simple est de créer une permutation de [0,MaxX[ et une permutation de [0,MaxY[ et de prendre les abscisses dans la première permutation, les ordonnées dans la seconde.

parce que si on prend 20 fois une valeur aléatoire, on est pas assuré à la fin d'avoir 20 valeurs uniques
du coup on prend la liste de nombres jusqu'à Max{x,y} dans sa totalité, on la mélange, et on en récupère les 20 premières valeurs

quant à l'histoire de la diagonale, j'ai plutôt compris ça comme le fait qu'on ne doit pas avoir un point (15,10) et un point (15,8) par exemple, mais un point (6,6) est autorisé

c'est bien ça ?

Le fait que des abscisses ou ordonnées ne puissent être utilisées deux fois est ce que j'appelle le "détail" dans mon poste précédent.

Et n'a franchement rien de compliqué.
Code:

1 2 3 4 5 6 7 8 9 10 11 >>> import random >>> base = [i for i in range(20)] >>> random.shuffle(base) >>> abscisses = base[:] >>> while abscisses == base: ... random.shuffle(base) ... >>> points = [(a, o) for a, o in zip(abscisses, base)] >>> points [(18, 10), (2, 9), (14, 8), (9, 1), (12, 16), (8, 15), (15, 17), (5, 7), (16, 3), (1, 6), (0, 14), (6, 5), (11, 4), (19, 0), (10, 18), (3, 2), (4, 13), (7, 19), (13, 11), (17, 12)]
Faudra sans doute rajouter une vérification de coordonnées identiques si celles-ci sont indésirables aussi.

17/12/2016, 12h23
tbc92

L'intitulé est très ambigu sur ces questions. Dans le code initial, il y a un test si a <> b , ce qui sous-entend que la diagonale serait interdite.
Ca ne m'étonnerait pas que le vrai problème soit une généralisation mal comprise du problème des 8 dames.

Citation:

Envoyé par tbc92

L'intitulé est très ambigu sur ces questions. Dans le code initial, il y a un test si a <> b , ce qui sous-entend que la diagonale serait interdite.
Ca ne m'étonnerait pas que le vrai problème soit une généralisation mal comprise du problème des 8 dames.

Si on essaye de décoder le code du PO :
Code:

1 2 3 4 5 6 7 8 9 10 11 import random def Tableau(NbPt): liste=[] for i in range (NbPt): a=random.randint(0,20) b=random.randint(0,20) if a!=b : for i in range (len(liste)): if liste[i]!=a and liste[i]!=b : liste.append(Point(a,b)) return liste
On peut imaginer que la ligne 7 essaye d'éviter des points sur la diagonale, et que la ligne 9 essaye de contraindre un point par abscisse et un point par ordonnée.
D'un certain point de vue ça simplifie les choses car on peut réduire le problème à trouver un dérangement (une permutation sans point fixe) dans lequel on choisi les points.
Pour donner un exemple simple on va partir d'une grille 6×6. Un dérangement de (0,1,2,3,4,5) peut être (5,2,1,0,3,4). À ce dérangement correspondent les points [ (0,5), (1,2), (2,1), (3,0), (4,3), (5,4) ]. Après il faut en choisir uniformément le nombre voulu.
C'est une méthode simple pour une grille carrée. Pour une grille plus large que haute on ne peut plus se contenter d'énumérer les éléments d'un dérangement. Pour une grille plus haute que large on peut réduire le problème au cas précédent par transposition.

Donc dans le cas d'une grille carrée de taille grid_size×grid_size on a un code relativement simple pour choisir count points :
Code:

1 2 3 4 5 6 7 from random import shuffle, sample def pick( grid_size, count ): ys=list(range(grid_size)) while not all(i!=y for i,y in enumerate(ys)): shuffle(ys) return sample( list(enumerate(ys)), count )

17/12/2016, 20h42
wiztricks

Soit on lit l'énoncé, soit on essaie de déchiffrer ce qu'essaie de faire le code (et il fait autre chose) et de comprendre pourquoi il plante en IndexError.
Ce qui fait pleins de sujets tant côté algo. que programmation.

Côté programmation, un des soucis du PO est d'être encore trop débutant pour écrire des lignes de code sans trop comprendre ce que la machine va bien pouvoir en faire. C'est un problème que lui seul pourra résoudre en passant du temps à pianoter à la console Python... Et proposer une solution toute faite l'aidera sans doute à reporter à plus tard ce pianotage mais ne le fera pas beaucoup progresser.

- W