Draw X numbers from range Y

Question

Inspired by this question

Task:

Given integers X and Y:
Randomly select an int in 1..Y (inclusive), X times. This selection is to be performed without replacement until all values in 1..Y are exhausted, at which point they all become replaced at the same time. This could happen several times.

X may (but is not guaranteed to) be greater than Y and always greater than 0.

Y is greater than 0.

"random" means that for each selection, each value not yet exhausted has about an equal chance of being selected. Relevant defaults (notably, no xkcd 221) apply.

You may not select in 0..Y or any other range instead.

Output format is flexible (array, ordered list, stdout) but each Y-length run may not be differentiable. For example, it is forbidden to output a newline after each Y-wide selection run if selections aren't normally separated by newlines.

examples (obviously since this is random the actual results may vary):

x=5, y=10 -> [ 10, 6, 2, 8, 9 ]
x=10, y=10 -> [ 5, 3, 1, 7, 6, 4, 10, 8, 9, 2 ]
x=15, y=10 -> [ 5, 6, 2, 4, 9, 3, 8, 1, 7, 10, 7, 1, 2, 9, 3 ]

This is code-golf.

• Jitse: By 1..Y, do you mean including 1 and Y? Also, can we use a zero-indexed range (0..Y-1)?
• Jitse: Possible duplicate
• Jonathan Allan: I'm not sure this should be closed as a duplicate of that since the requirements there limit the bag to exactly seven items, and so most of the answers use that fact. Answers here would, however, be pretty similar to answers there, so maybe it should be a duplicate? Since this was closed by one user vote and the community bot I'll cast a reopen vote (which will reopen it!) and see what the community decide.
• Jonathan Allan: (Also, that one allows answers to draw ad-infinitum.)
• Themoonisacheese: @madeforlosers examples added.

Answer 1

JavaScript (ES7), 79 bytes

Expects (y)(x).

y=>g=(x,n,i=Math.random()*y)=>x?n>>i&1?[-~i,...g(x-1,n^1<<i)]:g(x,n||2**y-1):[]

Try it online!

Commented

y => // outer function taking y
g = ( // inner recursive function taking:
 x, // x
 n, // n = bit-mask, initially undefined
 i = Math.random() // i = random value in [0, y[
 * y // (implicitly floored in bitwise operations)
) => //
x ? // if x is not zero:
 n >> i & 1 ? // if the i-th bit of n is set:
 [ // update the output array:
 -~i, // append floor(i) + 1
 ...g( // do a recursive call:
 x - 1, // decrement x
 n ^ 1 << i // clear the i-th bit of n
 ) // end of recursive call
 ] // end of array update
 : // else:
 g( // do a recursive call:
 x, // pass x unchanged
 n || // pass either n unchanged,
 2 ** y - 1 // or with y bits set if cleared
 ) // end of recursive call
: // else:
 [] // stop

• Jonathan Allan: Gratz on 200K :)
• Arnauld: @JonathanAllan Thank you!

Answer 2

Python 3, 77 bytes

f=lambda x,y:x*[x]and sample(range(1,y+1),y)[:x]+f(x-y,y)
from random import*

Try it online!

-3 bytes thanks to Jonathan Allan

Answer 3

Ruby, 42 bytes

Rather conveniently, calling sample with a number bigger than the length of the array shuffles it (as if you called it with the array length), saving bytes over having to get the minimum of x and y.

f=->x,y{x>0?[*1..y].sample(x)+f[x-y,y]:[]}

Try it online!

Answer 4

Julia, 90 bytes

+(X,Y)=begin Z=[];map(x->begin(Z==[])&&(Z=[1:Y...]);popat!(Z,rand(1:length(Z)))end,1:X)end

Attempt This Online!

Grateful that rand() is in Base.

ATO doesn't have StatsBase but the following is 85 bytes:

using StatsBase
+(x,y)=[sample([1:y...],min(x,y);replace=false);(x>y) ? (x-y+y) : []]

• MarcMush: 65 bytes small improvements: +(X,Y) => X+Y, begin ... ; ... end => ( ... ; ... ), 1:length => keys

Answer 5

Jelly, 5 bytes

Ẋ{ⱮFḣ

A dyadic Link that accepts the range size, \$Y\$, on the left and the desired count, \$X\$, on the right and yields a list of the \$X\$ draws from \$[1,Y]\$.

Try it online!

How?

Shuffle each of \$X\$ copies of \$[1,Y]\$, flatten this list of lists, and then only keep the first \$X\$.

Ẋ{ⱮFḣ - Link: non-negative integer, Y; non-negative integer, X
 Ɱ - map across {v in [1..X]} with - f(Y, v):
 { - using Y as the arguments - f(Y, Y):
Ẋ - shuffle {[1..Y]}
 F - flatten
 ḣ - head to index {X}

Answer 6

Wolfram Language (Mathematica), 43 bytes

Table[##&@@RandomSample@Range@#2,#]~Take~#&

Try it online!

Input [X, Y].

Answer 7

APL+WIN, 20 bytes.

Prompts for y followed by x.

x↑∊y? ̈(⌈(x←⎕)÷y)⍴y←⎕

Try it online! Thanks to Dyalog Classic

Answer 8

Google Sheets, (削除) 103 (削除ここまで) 91 bytes

^{-12 bytes thanks to Jonathan Allan}

Expects \$X\$ in A1 and \$Y\$ in A2.

=QUERY(REDUCE(,SEQUENCE(A1),LAMBDA(a,_,{a;SORT(SEQUENCE(A2),RANDARRAY(A2),)})),"limit "&A1)

Stacks on top of each other \$X\$ randomized sequences of numbers from \1ドル..Y\$ and constrains the result to the first \$X\$ values.

• Jonathan Allan: More sequences internally, but the same result: CEILING(A1/A2) -> A1.

Answer 9

TI-BASIC (TI-83 Plus), (削除) 72 (削除ここまで) (削除) 67 (削除ここまで) 65 bytes

-5 bytes thanks to MarcMush

Input A
Input B
B→dim(L1
For(N,1,A
If not(max(L1
cumSum(1 or L1→L1
Repeat L1(E
randInt(1,B→E
End
Disp L1(E
0→L1(E
End

TI calculators with OS 2.53MP (and the TI-84+/SE) have a RandIntNoRep function that would make this a lot easier, but I don't have one of those anymore. gotta look into upgrading

• MarcMush: you can use Repeat instead of While to spare the 1 line and combine with not(L1(E
• MarcMush: you can save 2 extra bytes by using named lists (codegolf.stackexchange.com/a/143898)
• madeforlosers: MarcMush can you show me the code for this? can't seem to get it to work / save any bytes
• MarcMush: you can do {0→A which is the same as {0→ʟA but ʟA(1 cannot be shorten. L1 is 2 bytes and ʟ is 1 only

Answer 10

Vyxal, 7 bytes

ẋvÞc/of0Ẏ

Try it Online!

Taking a L here because shuffle is two bytes and because input cycling works against me

Answer 11

Charcoal, 27 bytes

NθFN«F∧¬υθ⊞υ⊕κ≔⟦‽υ⟧ι≔−υιυIι

Try it online! Link is to verbose version of code. Takes inputs in the order Y, X. Explanation:

Nθ

Input Y.

FN«

Repeat X times.

F∧¬υθ⊞υ⊕κ

If all of the values are exhausted, replace all the values 1..Y.

≔⟦‽υ⟧ι

Pick a random value and wrap it in a list.

≔−υιυ

Perform list subtraction to remove it from the values.

Iι

Output it. (As a list, this outputs each value on its own line.)

Answer 12

05AB1E, 8 bytes

иL€.r ̃1£

Inputs in the order \$X,Y\$. Outputs as a list.

Try it online.

A program derived from my answer to the related challenge would be 1 byte longer:

FIL.r) ̃ć,

Inputs in the order \$X,Y\$. Outputs each value on a separated newline.

Try it online.

Explanation:

и # Repeat the second (implicit) input `Y` the first (implicit) input `X`
 # amount of times as list
 L # Convert each inner `Y` to a list in the range [1,Y]
 € # Map over each of those inner [1,Y]-lists
 .r # Randomly shuffle it
 ̃ # Flatten this list of lists
 1£ # Only keep the first input `Y` amount of leading values
 # (after which this list is output implicitly)
F # Loop the first (implicit) input `X` amount of times:
 IL # Push a list in the range [1, second input Y]
 .r # Randomly shuffle it
 ) # Wrap everything on the stack into a list
 ̃ # Flatten it
 ć # Extract its head; push remainder-list and first item separately
 , # Pop and print this first item with trailing newline

• juanferrer: The first one doesn't work if Y > 9.
• Kevin Cruijssen: @juanferrer Thanks for noticing! Should be fixed now.

Answer 13

Perl 5 -MList::Util=min -MList::MoreUtils=samples -ln, 54 bytes

map{say}samples min($_,$t//=<>),1..$_;($t-=$_)>0&&redo

Try it online!

Answer 14

Uiua 0.16.0-dev.1, ^{(削除) (削除ここまで)} 11 bytes ^SBCS

 ̃↙♭≡°⍆+1↯⤙⇡

Try on Uiua Pad!

Takes Y X on stack.

Explanation

 ̃↙♭≡°⍆+1↯⤙⇡
 +1↯⤙⇡ # X copies of range 1...Y
 ≡°⍆ # randomize each (literally "un"-"sort")
 ̃↙♭ # flatten and take the first X

Answer 15

PowerShell, 51 bytes

param($x,$y)for(;$x-gt0;$x-=$y){1..$y|random -c $x}

Try it online!

Answer 16

C# 10, (削除) 202 (削除ここまで) (削除) 154 (削除ここまで) 140 bytes

f=(x,y)=>{Random r=new();List<int> a=new();for(int i=-1;i<x/y;i++)a.AddRange(Enumerable.Range(1,y).OrderBy(x=>r.Next(y)));return a.Take(x);}

Accepts 2 ints and returns an IEnumerable<int>.

Try it on JDoodle.

Ungolfed:

Random r = new();
List<int> a = new();
for (int i = -1; i < x / y; i++) // Repeat 1 + x/y times:
 a.AddRange(Enumerable.Range(1, y).OrderBy(x => r.Next(y))); // Get the range 1-y, sort it randomly and append to list
Console.WriteLine(string.Join(',', a.Take(x))); // Take the first x numbers from list and print them

C# 12, (削除) 198 (削除ここまで) (削除) 150 (削除ここまで) 138 bytes

Shorter empty list initialiser ([] vs new()).

f=(x,y)=>{Random r=new();List<int> a=[];for(int i=-1;i<x/y;i++)a.AddRange(Enumerable.Range(1,y).OrderBy(x=>r.Next(y)));return a.Take(x);}

Edit: Turned it into a function thanks to Themoonisacheese's comment.

• Themoonisacheese: Fyi, you're allowed to sumbit functions that assume they are passed the correct type, and return their result instead of printing it, that's usually shorter, especially in C# :)
• juanferrer: Well, if that's the case, I'll have to go and edit all my answers! xD Thanks, I'll update the question.

Answer 17

Maple, 112 bytes

proc(x,y)L:=[$y];S:=();to x do r:=rand(1..nops(L))();S,=L[r];L:=subsop(r=(),L);if L=[] then L:=[$y] fi od;S end;

proc(x,y)
L:=[$y]; # initialize list to [1..y]
S:=(); # initialize output sequence to NULL
to x do
 r:=rand(1..nops(L))(); # find random index into current list
 S,=L[r]; # augment sequence with new value
 L:=subsop(r=(),L); # remove value from list
 if L=[] then L:=[$y] fi # reset list if empty
od;
S; # return sequence
end;

I thought a recursive function would be shorter, but it wasn't

Answer 18

C (gcc), 99 bytes

f(x,y){int i,a[y],n=0;for(;x--;a[i]=a[--n]){
if(!n)for(;n<y;a[n++]=n);printf("%d ",a[i=rand()%n]);}}

Try it online!

A simple algorithm that (re)generates the pool when empty, and swaps each picked value with the shrinking end.

• ceilingcat: 97 bytes

Answer 19

CASIO BASIC (CASIO fx-9750GIII), (削除) 92 (削除ここまで) 76 bytes

?→A
?→B
{0→List1
For 1→N To A
Not Max(List1⟹Seq(K,K,1,B,1→List1
Do
RanInt#(1,B
LpWhile Not List1[Ans
List1[Ans◢
0→List1[Ans
Next

I think this is right

input x first, then y

try a longer version online at basic.crevola.org

Answer 20

R, (削除) 44 (削除ここまで) 36 bytes

\(x,y)sapply(1:x,\(i)sample(y))[1:x]

Attempt This Online!

Answer 21

Arturo, 46 bytes

$[x y]->take flatten [email protected]:[email protected]=>shuffle x

Try it!

Answer 22

Pharo, 63 bytes

[:x :y|((1to:x)flatCollect:[:x|(1to:y)asArray shuffle])first:x]

Answer 23

Google Sheets, 82 bytes

=query(tocol(map(1:1,lambda(_,sort(sequence(A3),randarray(A3),))),,1),"limit "&A2)

Put \$X\$ in cell A2, \$Y\$ in cell A3 and the formula in cell B2.

screenshot

^{(cheats a bit)}

Answer 24

Zsh + GNU coreutils, 32 bytes

(repeat 1ドル shuf -i1-2ドル)|head -1ドル

Expects x, y as arguments.

Attempt This Online!

Answer 25

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}14 bytes ^SBCS

∊⊢?⍨ ̈|⍨,⍨⌊⍤÷⍴⊢

X is the left argument, Y is the right.

Try it on APLgolf!

Explanation

 ⊢ right argument, Y
 ⍴ reshape
 ÷ divide
 ⍤ postprocess
 ⌊ floor
 ⌊⍤÷ floor division; X//Y
 ⌊⍤÷⍴⊢ repeat Y (X//Y) times
 ⍨ swap left and right arguments
 , concatenate
 ,⍨ append left argument to the end 
 ⍨ 
 | modulo
 |⍨ Y%X (arguments are swapped)
 |⍨,⍨⌊⍤÷⍴⊢ repeat Y while the sum is less than X, append the remainder
 ̈ each
 ⍨ 
 ? deal: A?B returns A different numbers in range 1..B
 ⊢ 
 ⊢?⍨ ̈ for each number N on the right: deal N times in range Y
 ⊢?⍨ ̈|⍨,⍨⌊⍤÷⍴⊢ solution but as vector of vectors: new subvector starts after exhausting all values in 1..Y
∊ enlist: make one vector from all values in order
∊⊢?⍨ ̈|⍨,⍨⌊⍤÷⍴⊢ solution