Unique array of random numbers using functional programming

Question

I'm trying to write some code in a functional paradigm for practice. There is one case I'm having some problems wrapping my head around. I am trying to create an array of 5 unique integers from 1, 100. I have been able to solve this without using functional programming:

let uniqueArray = [];

while (uniqueArray.length< 5) {
  const newNumber = getRandom1to100();
  if (uniqueArray.indexOf(newNumber) < 0) {
    uniqueArray.push(newNumber)
  }
}

I have access to lodash so I can use that. I was thinking along the lines of:

const uniqueArray = [
  getRandom1to100(), 
  getRandom1to100(), 
  getRandom1to100(), 
  getRandom1to100(), 
  getRandom1to100()
].map((currentVal, index, array) => {
      return array.indexOf(currentVal) > -1 ? getRandom1to100 : currentVal;
    });

But this obviously wouldn't work because it will always return true because the index is going to be in the array (with more work I could remove that defect) but more importantly it doesn't check for a second time that all values are unique. However, I'm not quite sure how to functionaly mimic a while loop.

Answer 1

This is a very good question. It's actually quite common. It's even sometimes asked as an interview question.

Here's my solution to generating 5 integers from 0 to 100.

let rec take lst n =
  if n = 0 then []
  else
    match lst with
    | [] -> []
    | x :: xs -> x :: take xs (n-1)

let shuffle d =
  let nd = List.map (fun c -> (Random.bits (), c)) d in
  let sond = List.sort compare nd in
  List.map snd sond

let rec range a b =
  if a >= b then []
  else a :: range (a+1) b;;

let _ = 
    print_endline 
        (String.concat "\t" ("5 random integers:" :: List.map string_of_int (take (shuffle (range 0 101)) 5)))

Answer 2

Here is a stream-based Python approach.

Python's version of a lazy stream is a generator. They can be produced in various ways, including by something which looks like a function definition but uses the key word yield rather than return. For example:

import random

def randNums(a,b):
    while True:
        yield random.randint(a,b)

Normally generators are used in for-loops but this last generator has an infinite loop hence would hang if you try to iterate over it. Instead, you can use the built-in function next() to get the next item in the string. It is convenient to write a function which works something like Haskell's take:

def take(n,stream):
    items = []
    for i in range(n):
        try:
            items.append(next(stream))
        except StopIteration:
            return items
    return items

In Python StopIteration is raised when a generator is exhausted. If this happens before n items, this code just returns however much has been generated, so perhaps I should call it takeAtMost. If you ditch the error-handling then it will crash if there are not enough items -- which maybe you want. In any event, this is used like:

>>> s = randNums(1,10)
>>> take(5,s)
[6, 6, 8, 7, 2]

of course, this allows for repeats.

To make things unique (and to do so in a functional way) we can write a function which takes a stream as input and returns a stream consisting of unique items as output:

def unique(stream):
    def f(s):
        items = set()
        while True:
            try:
                x = next(s)
                if not x in items:
                    items.add(x)
                    yield x
            except StopIteration:
                raise StopIteration
    return f(stream)

this creates an stream in a closure that contains a set which can keep track of items that have been seen, only yielding items which are unique. Here I am passing on any StopIteration exception. If the underlying generator has no more elements then there are no more unique elements. I am not 100% sure if I need to explicitly pass on the exception -- (it might happen automatically) but it seems clean to do so.

Used like this:

>>> take(5,unique(randNums(1,10)))
[7, 2, 5, 1, 6]

take(10,unique(randNums(1,10))) will yield a random permutation of 1-10. take(11,unique(randNums(1,10))) will never terminate.

Answer 3

Here's an example in OCaml, the key point is that you use accumulators and recursion.

let make () =
  Random.self_init ();
  let rec make_list prev current max accum =
    let number = Random.int 100 in
    if current = max then accum
    else begin
      if number <> prev
      then (number + prev) :: make_list number (current + 1) max accum
      else accum
    end
  in
  make_list 0 0 5 [] |> Array.of_list

This won't guarantee that the array will be unique, since its only checking by the previous. You could fix that by hiding a hashtable in the closure between make and make_list and doing a constant time lookup.

Answer 4

How's this:

const addUnique = (ar) => {
    const el = getRandom1to100();
    return ar.includes(el) ? ar : ar.concat([el])
}

const uniqueArray = (numberOfElements, baseArray) => {
    if (numberOfElements < baseArray.length) throw 'invalid input' 
    return baseArray.length === numberOfElements ? baseArray : uniqueArray(numberOfElements, addUnique(baseArray))
}
const myArray = uniqueArray(5, [])