Implement a bag without replacement

Question

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

• This is code-golf, so lowest byte count wins!
• Standard loopholes are forbidden.
• You can use any reasonable I/O method.

"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.

Answer 1

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:

• 5 bytes for Arbitrary n items: {Þ℅⟑,. Implicitly takes an integer as the input.
• 5 bytes for Generic bag: {Þ℅⟑,. Implicitly takes a list as the input. Same program as above :P
• 8 bytes for Draw n items: {7Þ℅?Ẏ⟑,. Slices the list until the input before applying it to the lambda.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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:

Answer 8

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!

Answer 9

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.

Answer 10

Go, 182 165 bytes

import(."math/rand";."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).

• -17 bytes by using the now-stdlib slices package. Also applies to all "bonuses" below.

"Bonuses"

Arbitrary n distinct items, 204 187 bytes

import(."math/rand";."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 191 bytes

import(."math/rand";."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 271 bytes

import(."math/rand";."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.

Answer 11

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

Answer 12

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

Answer 13

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
};

Answer 14

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!

Answer 15

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

Answer 16

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!

Answer 17

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!

Answer 18

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!

Answer 19

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.

Answer 20

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

[7R7zPZw{ZK

Attempt This Online!

Port of mathcat's Vyxal answer.

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

Answer 21

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
}

Answer 22

Perl 5 -MList::Util=shuffle, 29 bytes

$,=$/;1while say shuffle 1..7

Try it online!