Elm - список случайных чисел без дубликатов

Question

Я делаю игру в вяза и пытаюсь случайно разместить N злых роботов на сетке с ячейками ROWS x COLS.

Что я хотел бы, это пары (Int, Int), которые определяют, где разместить N роботов.

я могу сделать список координатных пар с

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

Это нормально. Но если я хочу сгенерировать список уникальных пар?

Должен ли я сделать императивное решение, где я держу набор своих вещей и цикл, добавляя до тех пор, пока у меня не будет достаточно?

Может быть что-то вроде этого (вероятно, неправильно, не проверить это в РЕПЛ):

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 

Это чувствует себя прочь. Я думал, что из 3-х вариантов:

1. сделать мою сетку список РЯДОВ * COLS пара координат со списком типа (Int, Int), затем перетасовать ее и взять первые N пар в списке место мои роботы. Это кажется очень кратким и чистым, но неэффективным/плохим, если количество уникальных точек, которые мне нужны, намного меньше, чем моя сетка, и если моя сетка большая (поскольку Fisher-Yates - O (n log (n)), я думаю).

2. Используйте что-то наподобие this package для образца из моей сетки без замены, но мне нужно сменить сетку на массив, и похоже, что он много расщепляет и сращивает массивные операции, которые выглядят дорого.

3. Используйте JS FFI для реализации этого в четырехстрочном цикле JS.

Ни одно из этих решений не чувствует себя хорошо, есть ли что-то, что мне не хватает? Я, вероятно, собираюсь просто изменить механику игры, чтобы каждая клетка имела вероятность P иметь на ней робота, так что ее проще реализовать.

Answer 1

Я открыл an issue на elm-random-extra, и mgold помог мне разработать функцию, аналогичную той, что находится в вопросе, а затем добавила ее в elm-random-extra 2.1.1. Большое спасибо!

Функция в вяза случайных дополнительных Random.Set-х set, и имеет тип:

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

вы передаете ему n, generator, и она возвращает generator наборов n вещей из ваш оригинал generator.Например:

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

или ответить на мой первоначальный вопрос, уникальных пар на (например) 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) 

Существует один нюанс: функция не знает, сколько уникальных элементов генератор, который он задал, имеет, поэтому есть вероятность, что вы попросите его 100 уникальных номеров и дадите ему кубик (int 1 6), он застрянет, пытаясь получить 7-й уникальный номер навсегда, что приведет к переполнению стека, вероятно.

Было два варианта: сбой при переполнении стека или возврат плохих данных, остановка на раннем этапе после нескольких ударов. Мы выбрали вторую. Если он не может найти уникальный номер 10 раз подряд, он просто вернет то, что он нашел до сих пор. Я думаю, что это еще больше напоминает философию «Нет ошибок времени выполнения».