# Implement a bag without replacement

## Intro

The Tetris Guidelines specify what RNG is needed for the piece selection to be called a Tetris game, called the Random Generator. Yes, that's the actual name ("Random Generator"). In essence, it acts like a bag without replacement: You can draw pieces out of the bag, but you cannot draw the same piece from the bag until the bag is refilled.

Write a full program, function, or data structure that simulates such a bag without replacement.

## Specification

Your program/function/data structure must be able to do the following:

• Represent a bag containing 7 distinct integers.
• Draw 1 piece from the bag, removing it from the pool of possible pieces. Output the drawn piece.
• Each piece drawn is picked uniformly and randomly from the pool of existing pieces.
• When the bag is empty, refill the bag.

## Other Rules

### "Bonuses"

These bonuses aren't worth anything, but imaginary internet cookies if you are able to do them in your solution.

• Your bag can hold an arbitrary n distinct items.
• Your bag can hold any type of piece (a generic bag).
• Your bag can draw an arbitrary n number of pieces at once, refilling as needed.

# Vyxal, 5 bytes

Inspired by Kevin Cruijssen's 05AB1E answer
6 bytes without the bonus:

{7Þ℅⟑,


Try it Online!

Explanation

{7Þ℅⟑,
{         Loop forever
7Þ℅      Random permutaton of range(7)
⟑,    Lazily evaluated lambda, print each item


Bonuses:

# R, 50 40 bytes

-10 bytes thanks to inspiration from Giuseppe

{b=n=1;\()(b<<-c(b,sample(7)))[n<<-n+1]}


Attempt This Online!

A reuseable function that on each call returns a single random nunber in the range 1..7, sampled across calls using the 'tetris' distribution.
This is how I interpret the intent of the challenge.

A 62-byte recursive variant of this satisfies all 3 bonuses (try it here):

f={b=n=1;\(m,p)if(m)c((b<<-c(b,sample(p)))[n<<-n+1],f(m-1,p))}


# R, 24 bytes

repeat cat(sample(7),"")


Attempt This Online!

Alternative: a full program that outputs an infinite sequence of random permutations of 1..7.
This probably satisfies the letter of the challenge, and other answers have used this approach, although it does seem rather trivial.

• print is a byte shorter for your second response. And I think \(n)replicate(n,sample(7))[n] would be good for the first one? Jan 13, 2023 at 18:36
• @Giuseppe or show instead of print? Jan 13, 2023 at 19:18
• @Giuseppe & @pajonk - re: print or show - I considered this, but didn't like the way that the output is separated into chunks of 7, which seemed to go against the "Draw 1 piece from the bag" notion... Jan 13, 2023 at 22:19
• @Giuseppe - re: suggestion for first one - I interpreted "Your program/function/data structure must ... Draw 1 piece from the bag ... from the pool of existing pieces ... [and] When the bag is empty, refill the bag" to imply that the function should output one-at-a-time, and sequential runs should keep in account the pieces left in the bag. Jan 13, 2023 at 22:24
• @Giuseppe - But a variant of your suggestion that remembers the pieces in each bagful seems to work well: thanks a lot! Jan 13, 2023 at 22:40

# JavaScript (ES6), 50 bytes

A function that draws one piece at a time.

m=f=_=>m^(m|=1<<(i=Math.random()*7))?-~i:f(m%=127)


Try it online!

### Commented

m =               // m (aka "the bag") is a global bitmask holding
// drawn pieces, initialized to a zero'ish value
f = _ =>          // f is a recursive function ignoring its argument
m ^ (             // if m is modified when ...
m |= 1 << (     //   ... the floor(i)-th bit of m is set
i =           //   where i is uniformly chosen
Math.random() //   in [0, 7[
* 7           //
)               //
) ?               // then:
-~i             //   return floor(i + 1)
:                 // else:
f(              //   try again
m %= 127      //   and reset m to 0 if it's 127 (0b1111111),
)               //   meaning that the bag is empty


# Raku, 23 bytes

{grab $||=SetHash(^7):}  Try it online! Ungolfed: { state$bag ||= SetHash(0..6);
$bag.grab; }  This is a function which, when called repeatedly, will return the integers 0-6 in a random order, then the same integers in a (likely) different random order, and so on, ad infinitum. Raku has a built-in data type SetHash which stores a set of objects, and has a grab method that chooses one of them randomly, removes it from the set, and returns it. All that's left to do for this challenge is the refilling. A state variable ($ in the golfed version, $bag in the ungolfed one) stores the SetHash, which is reset to a new object with full contents (using ||) when the variable is undefined, as on the first call to the function, or has become empty, as after every seventh call. # 05AB1E, 9 bytes [7L.r)˜ć,  Uses a bag with integers [1,2,3,4,5,6,7]. Outputs the random piece indefinitely on separated newlines. Try it online. 1. (9 bytes) Replace 7 with I for the first bonus, where n is given as input-integer: try it online. 2. (8 bytes) Replace 7L with I for the second bonus, where the bag is given as input-list: try it online. 3. (11 bytes) Add Iô after ˜ for the third bonus, where n is given as input-integer and it'll output those n items as a list each iteration: try it online. Will use a combination of the existing list and a new shuffled list if the bag doesn't hold enough items anymore (e.g. let's say $$\n=3\$$ and the first two iterations where [4,2,5] and [1,7,3], then the third iteration will be [6,a,b], where the 6 is from the existing bag, and a,b are two random integers from a new bag). Explanation: [ # Loop indefinitely: 7L # Push a list in the range [1,7] .r # Randomly shuffle it ) # Wrap the entire stack into a list ˜ # Flatten it to a single list ć # Extract head; pop and push remainder-list and first item separately , # Pop and output this first item  # JavaScript (Node.js), 62 bytes f=_=>x.match(i=Math.random()*7|0)?f(x=x[6]?'':x):(x+=i,i);x=''  Try it online! I hope I understood question correctly # Excel (ms365), 121 bytes Formula in A1: =LET(p,7,n,8,DROP(TAKE(REDUCE(0,SEQUENCE(ROUNDUP(n/p,0)),LAMBDA(a,b,VSTACK(a,SORTBY(SEQUENCE(p),RANDARRAY(p))))),n+1),1))  Idea here is that: • 'p' - Represents the amount of distinct items in our bag; • 'n' - Represents the amount of tokens we take out of the bag at once (with refilling it offcourse). You may change this to any reasonable integer; • 'SEQUENCE(p)' - Represents our array. In this specific case we create an array of integers, but SORTBY() can take any array of any type. This however will start changing byte-count! Below another sample where 'n' == 14 and another one where 'n' == 14 and 'p' == 3: # Jelly, 6 5 bytes ẊÐḶFY  Implements the first bonus Runs until a pattern is repeated -1 byte thanks to Jonathan Allan! How? ẊÐḶFY : Main Link, One arg(Number of pieces) Ẋ : Shuffle; return a random permutation ÐḶ : Loop; Repeat until the results are no longer unique F : Flatten list Y : Join z, separating by linefeeds  Attempt This Online! • @JonathanAllan idek how I didn't catch that while golfing, thanks for the spot! Jan 13, 2023 at 18:27 # Factor, 63 62 bytes [ 0 get [ 7 iota 7 sample >vector dup 0 set ] when-empty pop ]  Try it online! A quotation (anonymous function) that takes no arguments and outputs one piece each time it is called. You can look in the bag in between function calls with 0 get. # Go, 182 bytes import(."math/rand";."golang.org/x/exp/slices") func f()func()int{b:=[]int{} return func()int{n:=Intn(7) for;Contains(b,n);n=Intn(7){} b=append(b,n) if len(b)>6{b=[]int{}} return n}}  Attempt This Online! A generator function that returns a function. When the returned function is called, it returns an int in the range [0,7). ### "Bonuses" #### Arbitrary n distinct items, 204 bytes import(."math/rand";."golang.org/x/exp/slices") func f(I[]int)func()int{b,l:=[]int{},len(I) return func()int{e:=I[Intn(l)] for;Contains(b,e);e=I[Intn(l)]{} b=append(b,e) if len(b)>=l{b=[]int{}} return e}}  Attempt This Online! Generator function now takes a list of elements to choose from. #### Arbitrary n items + generic (comparable), 208 bytes import(."math/rand";."golang.org/x/exp/slices") func f[T comparable](I[]T)func()T{b,l:=[]T{},len(I) return func()T{e:=I[Intn(l)] for;Contains(b,e);e=I[Intn(l)]{} b=append(b,e) if len(b)>=l{b=[]T{}} return e}}  Attempt This Online! Works for any comparable type (bool, int, float, string, pointer, channel, struct of comparables, array of comparables, typeset of comparable). #### Arbitrary n items + generic (comparable) + k items at a time, 288 bytes import(."math/rand";."golang.org/x/exp/slices") func f[T comparable](I[]T)(func()T,func(int)[]T){b,l:=[]T{},len(I) A:=func()T{e:=I[Intn(l)] for;Contains(b,e);e=I[Intn(l)]{} b=append(b,e) if len(b)>=l{b=[]T{}} return e} return A,func(n int)(N[]T){for i:=0;i<n;i++{N=append(N,A())};return}}  Attempt This Online! A function that returns 2 functions. The first function takes 1 item, the second function takes k items. # Jelly, (4) 5 bytes 7ẊṄ€ß  A full program that prints forever. Try it online! $$\4\$$ bytes - ẊṄ€ß - taking either an arbitrary alphabet size TIO or an arbitrary alphabet (as a list) TIO. ### How? 7ẊṄ€ß - Main Link: no arguments 7 - seven Ẋ - (implicit range [1..7]) shuffle € - for each: Ṅ - print with trailing newline ß - call this link again with the same arity  # Pip, 11 bytes {l|:SHaPOl}  This is a function that takes as an argument a list of possible piece values (implementing the first two bonuses) and returns a single piece each time it is called. Attempt This Online! ### Explanation We store the current state of the bag in the global variable l. Initially, l is []. {l|:SHaPOl} { } Define a function: l|: If l is empty, set it to SHa the function argument, randomly shuffled POl Pop the first element from l and return it  # PHP, 79 bytes $y=function()use(&$a){$a=$a!=[]?$a:range(0,6);shuffle($a);echo array_pop($a);};


Try it online!

### Commented

$y = function() use (&$a) {   // anonymous function with use clause by-reference
$a =$a != []             // equal comparison, if $a is neither null nor empty array ?$a                  // then use $a : range(0,6); // else create range array shuffle($a);              // shuffle array
echo array_pop($a); // splice off and return last element of$a
};

• Welcome to Code Golf, and nice answer! Unless I'm missing something, I don't think the function calls itself anywhere, in which case you don't actually need the $y= under site rules. Jan 16, 2023 at 23:52 # Pip, 11 8 bytes LhP*SH,a  Implements the first bonus -3 bytes thanks to DLosc! How? LhP*SH,a : One arg(Number of items) a : First arg L : Loop x times; h : Literal for 100 , : Range zero to a SH : Shuffle: random permutation of iterable * : Map P : Print  Try It Online! • @DLosc thanks for the spot! :) Jan 13, 2023 at 18:33 # Zsh, 35 bytes exec<<(while shuf -i1-7) f()read -e  Attempt This Online! Uniquely for zsh, this is a function f, not a full program. If you want to cheat and output infinitely, you only need the while shuf -i1-7. Setup: • while shuf -i1-7: repeatedly output the shuffled range 1 to 7 • <(): create a pipe from the output of that loop • exec<: move that pipe to standard input f: • read: read one word from standard input • -e: and print it # Python 3, 59 bytes -6 bytes thanks to @att from random import* while[*map(print,sample(range(7),7))]:1  Try it online! Infinitely prints integers. I dont know if this is valid: (54 bytes) Prints all 7 integers of permutation in one line before a newline. from random import* while 1:print(*sample(range(7),7))  Try it online! • *map(print,sample(range(7),7)) – att Jan 14, 2023 at 3:43 # Haskell, 149 bytes import System.IO.Unsafe import System.Random import Data.List d(o,[])=d([],o) d(o,p)=(\n->(n:o,p\\[n]))$(p!!)$unsafePerformIO$randomRIO(0,length p-1)


Try it online!

# Clojure, 56 bytes

(run! #(run! println %)(repeatedly #(shuffle(range 7))))


Creates an infinite list containing random permutations of 0 to 6 and prints each number.

Try it online!

# Brachylog, 7 bytes

7>ℕ≜₁|↰


Try it online!

This is a predicates that unifies its output with a random integer between 0 and 6, exhausting each possibility before beginning a new cycle.

Try generating 14 random unifications here!

You can change 7 to any other number to get bigger bags.

### Explanation

7>ℕ        Take an unknown integer between 0 and 6
≜₁     Assign a value to it, with a random choice
|    Else
↰   Recursive call


Since our variable is constrained in [0..6], ≜₁ will randomly unify it with one of those 7 values, leaving a choice point for each one. Brachylog will try each choice point when asked (e.g. with ᶠ - findall, failure loops, or by pressing ; in Prolog’s REPL), so each integer value. | creates another choice point that will get called only once all the choice points created by ≜₁ are exhausted.

# Thunno, $$\ 11 \log_{256}(96) \approx \$$ 9.05 bytes

[7R7zPZw{ZK


Attempt This Online!

#### Explanation

[7R7zPZw{ZK
[            # Forever:
ZK  #   Print
{    #   Each element of
Zw     #   A random element of
7zP       #   The permutations
7R          #   Of range(7)


#### Bonuses

• Arbitrary n items: $$\ 13 \log_{256}(96) \approx \$$ 10.70 bytes, [z0Rz0zPZw{ZK
• Generic bag: $$\ 12 \log_{256}(96) \approx \$$ 9.88 bytes, [z0DLzPZw{ZK

# C (gcc), 60 bytes

b;f(i,j){b-127||(b=0);for(;b&1<<(i=rand()%7););b|=1<<i;j=i;}


Try it online!

## Explanation

b; // Bag: initialized with nothing selected
f(i,j){
b-127||(b=0); // Reset bag when all 7 pieces selected
for(;b&1<<(i=rand()%7);); // Find a random unselected piece
b|=1<<i; // Mark it as selected
j=i; // Return the piece
}