Elm - liste de nombres aléatoires sans doublons

Question

Je fais un jeu en orme et essaye de placer aléatoirement N robots maléfiques sur une grille avec des cellules ROWS x COLS.

Ce que je voudrais, c'est une paire List (Int, Int) qui spécifie où placer les N robots.

je peux faire une liste de paires de coordonnées avec

makeGrid : Seed -> List (Int, Int) 
makeGrid seed = 
    let gen = list n <| pair (int 0 rows) (int 0 cols) 
in 
    fst (generate gen seed) 

C'est très bien. Mais si je veux générer une liste de unique paires?

Dois-je faire la solution impérative où je garde un ensemble de mes choses et en ajoutant jusqu'à ce que j'en ai assez?

Peut-être quelque chose comme ça (probablement tort, n'a pas vérifié dans le REPL):

makeN : Int -> Seed -> (List (Int, Int), Seed) 
makeN n seed = 
    let gen = list n <| pair (int 0 rows) (int 0 cols) 
in 
    generate gen seed 

makeGrid : List(Int, Int) -> Seed -> Int -> List (Int, Int) 
makeGrid partial seed n = 
    case of List.length partial 
    n -> partial 
    current -> 
     let (new_elems, new_seed) = makeN (n - current) seed 
     makeGrid Set.toList (Set.fromList <| append partial new_elems) new_seed n 

Cela se sent hors tension. J'ai pensé à 3 alternatives:

1. Faire ma grille une liste de lignes * COLS paires de coordonnées avec, puis mélangez liste de type (Int, Int), et prendre les premières paires N dans la liste de lieu mes robots. Cela semble très concis et propre, mais inefficace/mauvais si le nombre de points uniques dont j'ai besoin est beaucoup plus petit que ma grille, et si ma grille est grande (comme Fisher-Yates est O (n log (n)) je pense). Utilisez quelque chose comme this package pour échantillonner à partir de ma grille sans remplacement, mais j'ai besoin de changer ma grille dans un tableau et il semble qu'il y ait beaucoup de division et d'épissage des opérations de tableaux, ce qui semble coûteux.

2. Utilisez le JS FFI pour l'implémenter dans une boucle JS à 4 lignes.

Aucune de ces solutions ne se sent bien, y a-t-il quelque chose qui me manque? Je vais probablement simplement changer la mécanique du jeu pour que chaque cellule ait une probabilité P d'avoir un robot dessus, donc c'est plus simple à implémenter.

Answer 1

J'ai ouvert an issue sur elm-random-extra, et mgold m'a aidé à développer une fonction similaire à celle de la question, puis l'ai ajouté à elm-random-extra 2.1.1. Merci beaucoup mgold!

La fonction est set en orme-aléatoire supplémentaire Random.Set de, et a le type:

set : Int -> Generator comparable -> Generator (Set comparable) 

vous passez un n, un generator, et il renvoie un generator d'ensembles de n choses votre generator d'origine.Par exemple:

$ fst <| generate (set 5 <| int 0 1000) seed 
Set.fromList [286,398,618,961,1000] : Set.Set Int 

ou pour répondre à ma question initiale, de paires uniques sur une grille (par exemple) 100x100:

$ fst <| generate (set 10 <| pair (int 0 100) (int 0 100)) seed 
Set.fromList [(2,54),(4,55),(25,50),(35,32),(46,9),(55,9),(62,22),(65,77),(88,74),(95,31)] 
: Set.Set (Int, Int) 

Il y a une mise en garde: La fonction ne sait pas combien d'éléments uniques le générateur qu'il a a, donc il y a la chance que vous lui demandiez 100 nombres uniques et lui donniez un générateur de dés (int 1 6), il se coince en essayant d'obtenir un 7ème nombre unique pour toujours, menant à un débordement de pile probablement.

Il y avait deux options: planter sur le débordement de la pile, ou retourner de mauvaises données, s'arrêter tôt après un certain nombre de coups. Nous avons choisi le second. S'il ne peut pas trouver un nombre unique 10 fois de suite, il retournera simplement ce qu'il a trouvé jusqu'à présent. Je pense que cela va dans le sens de la philosophie "Pas d'erreurs d'exécution" de l'orme un peu plus.