Generate random numbers without repeating a value: Difference between revisions
(Added Java and Rust solutions) |
|||
| Line 145: | Line 145: | ||
4 14 17 15 1 6 12 11 2 3 19 10 9 18 7 13 8 20 16 5 |
4 14 17 15 1 6 12 11 2 3 19 10 9 18 7 13 8 20 16 5 |
||
13 12 8 3 9 17 14 10 6 2 11 20 19 18 4 7 16 1 15 5 |
13 12 8 3 9 17 14 10 6 2 11 20 19 18 4 7 16 1 15 5 |
||
</pre> |
|||
=={{header|Java}}== |
|||
<lang java>import java.util.*; |
|||
public class RandomShuffle { |
|||
public static void main(String[] args) { |
|||
Random rand = new Random(); |
|||
List<Integer> list = new ArrayList<>(); |
|||
for (int j = 1; j <= 20; ++j) |
|||
list.add(j); |
|||
Collections.shuffle(list, rand); |
|||
System.out.println(list); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
[19, 15, 10, 6, 17, 13, 14, 9, 2, 20, 3, 18, 8, 16, 7, 12, 1, 4, 5, 11] |
|||
</pre> |
</pre> |
||
| Line 320: | Line 339: | ||
2 7 1 9 12 5 11 14 20 4 10 8 13 6 16 18 3 15 19 17 |
2 7 1 9 12 5 11 14 20 4 10 8 13 6 16 18 3 15 19 17 |
||
done... |
done... |
||
</pre> |
|||
=={{header|Rust}}== |
|||
<lang rust>// [dependencies] |
|||
// rand = "0.7.2" |
|||
fn main() { |
|||
use rand::seq::SliceRandom; |
|||
use rand::thread_rng; |
|||
let mut rng = thread_rng(); |
|||
let mut v: Vec<u32> = (1..=20).collect(); |
|||
v.shuffle(&mut rng); |
|||
println!("{:?}", v); |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
[11, 19, 1, 7, 15, 4, 13, 10, 16, 3, 2, 18, 20, 17, 9, 8, 5, 6, 12, 14] |
|||
</pre> |
</pre> |
||
Revision as of 12:21, 29 August 2021
Many puzzle games such as the 15 puzzle game need a way to randomize the order of the pieces. One way to do this is to create an array and fill it with random values, with each element's index in that array being its position. Unfortunately, most random number generators can produce the same value more than once, which in this case isn't what we want.
- Task
Create a random number generator and have it output the numbers 1 through 20 (inclusive), in a random order. It cannot produce the same value more than once.
- Or
Given the output of an existing random number generator that does produce repeated output, create a function that constrains the output to numbers 1 through 20 (inclusive), and no number is output more than once. (Technically it stops being "random" at that point, but that's beyond the scope of this task.) Try your best not to make the process take too long at runtime.
For the second version of the task, the random number generator itself need not be implemented; however you must specify its possible range of values before your constraint function is applied. (e.g "Assume the random number generator creates a value from 0 to 255, and values are allowed to repeat")
- Related Tasks
F#
<lang fsharp> // Generate random numbers without repeating a value. Nigel Galloway: August 27th., 2021 MathNet.Numerics.Combinatorics.GeneratePermutation 20|>Array.map((+)1)|>Array.iter(printf "%d "); printfn "" </lang>
- Output:
12 7 17 8 10 13 16 19 20 14 18 5 9 11 3 4 1 15 6 2
Factor
Generating a random permutation of 1..20:
<lang factor>USING: kernel math.combinatorics math.ranges prettyprint random sequences ;
- random-permutation ( seq -- newseq )
[ length dup nPk random ] keep permutation ;
20 [1,b] random-permutation .</lang>
- Output:
{ 7 10 12 9 5 8 20 14 18 4 13 3 17 16 19 6 15 1 2 11 }
Shuffling 1..20:
<lang factor>USING: math.ranges prettyprint random vectors ;
20 [1,b] >vector randomize .</lang>
- Output:
V{ 20 7 8 17 18 1 15 13 12 10 3 14 19 2 5 9 16 11 6 4 }
Sampling 20 elements from 1..20:
<lang factor>USING: math.ranges prettyprint random ;
20 [1,b] 20 sample .</lang>
- Output:
{ 12 3 16 13 1 9 8 11 5 19 15 18 17 20 10 4 7 14 6 2 }
Go
This uses Go's 'native' random number generator which internally uses a custom algorithm attributed to D P Mitchell and J A Reeds and can generate non-negative random integers in the 64-bit range. <lang go>package main
import (
"fmt" "log" "math/rand" "time"
)
// Generates and prints all numbers within an inclusive range whose endpoints are // non-negative 64-bit integers. The numbers are generated in random order with // any repetitions being ignored. func generate(from, to int64) {
if to < from || from < 0 {
log.Fatal("Invalid range.")
}
span := to - from + 1
generated := make([]bool, span) // all false by default, zero indexing
count := span
for count > 0 {
n := from + rand.Int63n(span) // upper endpoint is exclusive
if !generated[n-from] {
generated[n-from] = true
fmt.Printf("%2d ", n)
count--
}
}
fmt.Println()
}
func main() {
rand.Seed(time.Now().UnixNano())
// generate 5 sets say
for i := 1; i <= 5; i++ {
generate(1, 20)
}
}</lang>
- Output:
Sample run:
16 7 5 11 10 12 1 19 9 2 4 14 6 18 17 8 20 3 13 15 10 3 5 7 14 9 20 6 11 8 13 18 1 17 15 12 4 2 16 19 12 14 16 11 15 2 8 13 3 19 6 17 18 4 10 5 20 1 7 9 4 11 9 17 14 16 2 7 6 1 12 20 8 15 5 13 10 18 19 3 19 13 9 7 5 12 11 17 1 3 16 4 15 14 20 8 6 18 2 10
Alternatively and far more efficiently, we can simply create a list of the required numbers and randomly shuffle them. Go has a standard library function for this which uses the Fisher-Yates (aka Knuth) shuffle.
<lang go>package main
import (
"fmt" "math/rand" "time"
)
func main() {
rand.Seed(time.Now().UnixNano())
numbers := make([]int, 20)
for i := 0; i < 20; i++ {
numbers[i] = i + 1
}
for i := 1; i <= 5; i++ {
rand.Shuffle(20, func(i, j int) {
numbers[i], numbers[j] = numbers[j], numbers[i]
})
s := fmt.Sprintf("%2d ", numbers)
fmt.Println(s[1 : len(s)-2])
}
}</lang>
- Output:
13 10 18 7 3 5 17 4 1 11 16 20 9 12 14 2 15 19 6 8 19 12 11 1 3 14 7 20 2 18 4 10 9 5 8 6 15 13 16 17 10 6 11 3 5 13 15 4 16 12 1 14 20 7 2 19 8 17 9 18 4 14 17 15 1 6 12 11 2 3 19 10 9 18 7 13 8 20 16 5 13 12 8 3 9 17 14 10 6 2 11 20 19 18 4 7 16 1 15 5
Java
<lang java>import java.util.*;
public class RandomShuffle {
public static void main(String[] args) {
Random rand = new Random();
List<Integer> list = new ArrayList<>();
for (int j = 1; j <= 20; ++j)
list.add(j);
Collections.shuffle(list, rand);
System.out.println(list);
}
}</lang>
- Output:
[19, 15, 10, 6, 17, 13, 14, 9, 2, 20, 3, 18, 8, 16, 7, 12, 1, 4, 5, 11]
Julia
Julia's Random module contains a function called `randperm(n::Integer)` which constructs a random permutation of integers from 1 to n. <lang julia>using Random @show randperm(20)
</lang>
- Output:
randperm(20) = [20, 2, 5, 6, 18, 14, 12,4, 13, 7, 15, 3, 19, 17, 1, 9, 16, 11, 10]
Nim
Nim standard module random provides a PRNG based on xoroshiro128+ algorithm whose period is 2^128 − 1. It also provides the shuffle procedure to shuffle an array or a sequence using Knuth algorithm.
Here, we have defined a procedure which accepts a slice a..b as argument and returns a shuffled sequence of values from a to b. It uses the same algorithm as in Wren solution, i.e. a list to keep track of generated values.
<lang Nim>import random
randomize()
proc generate(s: Slice[int]): seq[int] =
assert s.a <= s.b
var count = s.b - s.a + 1
var generated = newSeq[bool](count) # Initialized to false.
while count != 0:
let n = rand(s)
if not generated[n - s.a]:
generated[n - s.a] = true
result.add n
dec count
for i in 1..5:
echo generate(1..20)</lang>
- Output:
@[11, 15, 13, 9, 10, 6, 14, 1, 16, 4, 20, 17, 5, 7, 2, 3, 8, 12, 19, 18] @[11, 3, 15, 12, 10, 16, 6, 18, 4, 13, 14, 19, 1, 7, 2, 5, 9, 20, 17, 8] @[16, 10, 8, 1, 2, 18, 19, 4, 5, 11, 14, 15, 3, 13, 9, 12, 7, 20, 17, 6] @[4, 7, 1, 15, 11, 2, 10, 6, 19, 5, 12, 9, 14, 13, 17, 3, 18, 20, 8, 16] @[10, 9, 15, 2, 17, 8, 3, 20, 18, 12, 11, 14, 16, 13, 4, 5, 6, 1, 7, 19]
Perl
Just shuffle... <lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Generate_random_numbers_without_repeating_a_value use warnings; use List::Util qw( shuffle );
print "@{[ shuffle 1 .. 20 ]}\n" for 1 .. 5;</lang>
- Output:
9 15 11 14 17 10 13 1 2 7 19 3 6 12 4 16 8 5 18 20 20 17 18 6 1 19 14 10 2 7 4 12 8 15 3 16 9 11 5 13 4 3 9 15 6 20 14 8 18 5 19 17 1 10 11 16 12 2 13 7 17 9 3 15 1 20 7 19 13 8 11 10 6 5 4 14 12 18 16 2 13 1 5 18 12 11 3 14 10 9 19 4 20 16 8 6 17 2 7 15
Phix
Trival use of standard builtins. Progressively filtering the output of rand(20) would gain nothing except wasted cycles. Normally I would use "with javascript_semantics", or equivalently just "with js", to explicitly specify/verify the code can be run on both the desktop and in a web browser, however here that somehow seems like overkill.
?shuffle(tagset(20))
- Output:
{13,6,8,1,9,19,5,18,2,12,11,20,4,17,10,3,15,7,14,16}
Python
<lang python> import random
print(random.sample(range(1, 21), 20))
</lang>
- Output:
[14, 15, 3, 18, 4, 11, 16, 10, 12, 20, 13, 1, 6, 7, 2, 17, 5, 9, 19, 8]
Raku
Raku has three distinct "random" functions built in. rand() for when you want some fraction between 0 and 1. roll() when you want to select elements from a collection with replacement (rolls of a die). And pick() for when you want to select some elements from a collection without replacement. (pick a card, any card, or two cards or 10 cards...). If you want to select all the elements in random order, just pick 'whatever'. Here we'll pick all from 1 to 20, 5 times using the repetition operator.
<lang perl6>.put for (1..20).pick(*) xx 5</lang>
- Sample output:
20 4 5 7 15 19 2 16 8 6 3 12 14 13 10 18 9 17 1 11 4 5 18 10 13 3 1 11 6 2 19 8 12 7 16 17 14 20 15 9 14 8 15 11 17 4 3 10 18 7 16 13 1 20 12 9 6 5 19 2 7 5 15 11 12 18 17 3 20 6 13 19 14 2 16 10 4 9 8 1 19 12 4 7 3 20 13 17 5 8 6 15 10 18 1 11 2 14 16 9
REXX
The REXX solution to this task is performed in essentially three parts:
: Part 1. (The DO i ...) build a list of sequential integers.
: Part 2. (The DO r ...) build an array of random integers, using the list as a selection template.
: Part 3. (The DO o ...) display a grid of the random integers with title and formatting.
With the method/algorithm used herein, there are no random numbers being discarded (due to possible
duplicates) because there cannot be any duplicates.
<lang rexx>/*REXX program generates & displays a list of random integers (1 ──► N) with no repeats.*/
parse arg n cols seed . /*obtain optional argument from the CL.*/
if n== | n=="," then n= 20 /*Not specified? Then use the default.*/
if cols== | cols=="," then cols= 10 /* " " " " " " */
if datatype(seed, 'W') then call random ,,seed /*Specified? Then use the seed. */
w= 6
title= ' random integers (1 ──► ' n") with no repeats"
say ' index │'center(title, 1 + cols*(w+1) ) /*display the output title. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " " " separator*/ a=
do i=1 for n; a= a i /*create a list of possible integers. */
end /*i*/ /*step through the (random) integers. */
pool= n
do r=1 for n; ?= random(1, pool) /*obtain a random integer from the list*/
@.r= word(a, ?); a= delword(a, ?, 1) /*obtain random integer; del from pool.*/
pool= pool - 1 /*diminish size of the allowable pool. */
end /*r*/ /*step through the (random) integers. */
$=; idx= 1
do o=1 for n; x= @.o /*obtain a random integer from random @*/
$= $ right( x, w) /*add an integer to the output list. */
if o//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible show residual output.*/ say '───────┴'center("" , 1 + cols*(w+1), '─'); say exit 0 /*stick a fork in it, we're all done. */</lang>
- output when using the default inputs:
index │ random integers (1 ──► 20) with no repeats ───────┼─────────────────────────────────────────────────────────────────────── 1 │ 20 7 5 12 11 6 19 8 4 10 11 │ 9 17 15 13 1 16 3 18 14 2 ───────┴───────────────────────────────────────────────────────────────────────
Ring
<lang ring> see "working..." + nl
for num = 1 to 5
pRand()
next
see "done..." + nl
func pRand
randCheck = list(20)
while true
rnd = random(19)+1
if randCheck[rnd] = 1
loop
else
randCheck[rnd] = 1
see "" + rnd + " "
ok
nr = 1
for n = 1 to len(randCheck)
if randCheck[nr] = 1
nr++
ok
next
if nr = 21
see nl
exit
ok
end
</lang>
- Output:
working... 3 16 2 5 18 19 8 11 15 7 17 9 1 20 12 10 14 6 4 13 15 9 13 19 17 20 16 11 8 1 18 5 10 12 14 3 7 4 6 2 19 2 9 11 18 20 12 5 13 15 3 6 8 1 4 10 16 17 7 14 13 1 11 3 10 5 6 12 15 17 14 4 20 18 2 9 8 7 16 19 2 7 1 9 12 5 11 14 20 4 10 8 13 6 16 18 3 15 19 17 done...
Rust
<lang rust>// [dependencies] // rand = "0.7.2"
fn main() {
use rand::seq::SliceRandom;
use rand::thread_rng;
let mut rng = thread_rng();
let mut v: Vec<u32> = (1..=20).collect();
v.shuffle(&mut rng);
println!("{:?}", v);
}</lang>
- Output:
[11, 19, 1, 7, 15, 4, 13, 10, 16, 3, 2, 18, 20, 17, 9, 8, 5, 6, 12, 14]
Wren
This uses Wren's 'native' pseudo-random number generator which internally uses WELL512a and can generate random integers in the 32-bit range. <lang ecmascript>import "random" for Random import "/fmt" for Fmt
var rand = Random.new()
// Generates and prints all numbers within an inclusive range whose endpoints are 32 bit integers. // The numbers are generated in random order with any repetitions being ignored. var generate = Fn.new { |r|
var generated = List.filled(r.to - r.from + 1, false) // zero indexing
while (generated.any { |g| !g }) {
var n = rand.int(r.from, r.to + 1) // upper endpoint is exclusive
if (!generated[n - r.from]) {
generated[n - r.from] = true
Fmt.write("$2d ", n)
}
}
System.print()
}
// generate 5 sets say for (i in 1..5) generate.call(1..20)</lang>
- Output:
Sample run:
4 16 10 5 1 2 9 19 7 12 15 11 18 3 13 17 20 14 6 8 16 1 9 11 8 10 19 5 4 6 17 20 12 15 3 7 14 18 2 13 5 15 13 1 17 19 16 2 7 12 18 8 14 6 20 9 10 11 3 4 9 6 20 16 2 14 19 1 7 18 11 12 4 15 5 17 3 8 10 13 16 1 8 14 5 19 3 4 18 12 20 2 10 6 13 11 7 15 9 17
Alternatively and far more efficiently, we can simply create a list of the required numbers and randomly shuffle them. Wren has a built-in function for this which uses the Fisher-Yates (aka Knuth) shuffle.
<lang ecmascript>import "random" for Random
import "/fmt" for Fmt
var rand = Random.new() var numbers = (1..20).toList for (i in 1..5) {
rand.shuffle(numbers)
Fmt.print("$2d", numbers)
}</lang>
- Output:
3 19 16 12 7 5 9 10 15 13 6 11 20 14 8 18 4 17 1 2 15 1 18 14 4 20 11 2 6 3 12 5 7 10 16 17 9 13 19 8 19 6 14 1 13 2 18 20 11 8 5 3 9 12 15 17 4 16 10 7 16 15 5 10 1 13 17 6 8 9 20 3 14 11 18 2 19 12 4 7 17 6 10 13 20 5 3 11 18 12 16 2 14 15 19 9 8 1 4 7