text:
Output all distinct permutations of a vector
Challenge:
Output all distinct permutations of a, potentially long, list of positive integers. You may assume that the vector has less than 1,000 numbers when testing, but the process should in theory work for any vector with more than one number regardless of size.
Restrictions:

You must restrict the memory usage to O(n^2), where n is the number of elements in the input vector. You can't have O(n!). That means you can't store all permutations in memory.
You must restrict the time complexity to O(result size * n). If all numbers are equal, then this will be O(n), and if all are distinct, then this will be O(n!*n). That means you can't create a permutation and check it against all other permutations to ensure distinctness (that would be O(n!^2*n)).
Empirical measurements to show that time and memory restrictions are met are accepted.
You must actually print/output the permutations (since it's impossible to store them).

If you run your program long enough, then all permutations should be outputted (in theory)!
Distinct permutations:
The list [1, 1, 2] has three permutations, not six: [1, 1, 2], [1, 2, 1] and [2, 1, 1]. You may choose the order of the output.

Manageable test cases:
Input:
[1, 2, 1]
Output:
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

Input:
[1, 2, 3, 2]
Output:
[1, 2, 2, 3]
[1, 2, 3, 2]
[1, 3, 2, 2]
[2, 1, 2, 3]
[2, 1, 3, 2]
[2, 2, 1, 3]
[2, 2, 3, 1]
[2, 3, 1, 2]
[2, 3, 2, 1]
[3, 1, 2, 2]
[3, 2, 1, 2]
[3, 2, 2, 1]

Input:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Larger test case:
It's impossible to output all permutations for this one, but it should work in theory if you gave it enough time (but not unlimited memory).
Input:
[1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900]

You must explain how you know that all permutations are distinct, and that all permutations will be printed, eventually.
This is code-golf so the shortest code in bytes win.

Is there a reference implementation that meets these complexity requirements?

It shouldn't be too hard to come up with an algorithm that meets the requirements (it might not be very golfy though). I'm not a programmer or mathematician, I'm nothing but a humble challenge writer. I'll leave the tricky stuff for you guys/girls :)

I think given the restrictions characteristics this would come better as a fastest code, since code golf is usually for clever use of built ins and language features.

"It shouldn't be too hard" ≠ "it is possible"

Is the memory limitation only for RAM? As in can I store temporary results in a file to not technically have them "in memory"?

The so-called larger test case has binomial(905,6)*899! permutations.

Is a generating function acceptable or must we add boilerplate to such a solution to print/output?

Is it mandatory that the answerer prove the time complexity and memory usage of the code, or are empirical measurements sufficient (e.g. by using built-in benchmarks)?

@JungHwanMin empirical measurements are sufficient.

@JeppeStigNielsen I know. That's why it's not in the list of test cases that can be tested properly. The large test case should in theory output every permutation if you kept it running long enough. It can't print all permutations, but it shouldn't fail due to memory usage.

@MagicOctopusUrn will that help you? There aren't enough atoms in the universe to store even a tiny fraction of the total number of permutations for the large test case, so you can't store permutations in order to check for distinctness, if that's what you're aiming for.

@JonathanAllan I don't know exactly what a generator is to be honest, but if I'm not mistaken, you would need to create all permutations and return that list when you're finished. I think (but I'm not sure) that it would require O(n!) memory? If you can create all permutations for large lists, given enough time (but not unlimited memory), then it's OK.

Why 3 down vote ? Is it one impossible exercise ?

JavaScript (ES6), 177 169 bytes
a=>{s=''+a
do{console.log(a)
k=a.findIndex((e,i)=>a[i-1]>e)
if(~k)t=a[k],a[k]=a[l=a.findIndex(e=>e>t)],a[l]=t,a=a.map((e,i)=>i<k?a[k+~i]:e)
else a.reverse()}while(a!=s)}

Uses the well-known next lexicographic permutation generation algorithm, which I believe has memory O(len(array)) and time O(len(array)*len(output)). (Note that the array elements are considered to be in reverse order, so that e.g. 2, 2, 1, 1 will enumerate to 2, 1, 2, 1; 1, 2, 2, 1 etc.

Python 3 with sympy, (50?) 81 bytes
lambda a:[print(v)for v in sympy.iterables.multiset_permutations(a)]
import sympy

Try it online!
50 bytes if a generator function is acceptable:
import sympy
sympy.iterables.multiset_permutations

The implementation is open source and currently available on git hub, at the time of writing the function is at line 983.
I think it does, but do let me know if it does not, fulfil the asymptotic bounds.

Python 2, (411?) 439 bytes
A golfed version (also ignoring cases we are not required to cover) in Python 2 (still using the built-in itertools.permutations function) comes in at 439 bytes, or 411 with no additional boilerplate to print rather than generate (the for v in h(input()):print v):
from itertools import*
def h(a,z=-1,g=1):
 x=[v for v in[g,[[v,a.count(v)]for v in set(a)]][g==1]if 0<v[1]];S=sum([v[1]for v in x])
 if x==x[:1]:k,v=x[0];yield[k for i in range([[0,z][z<=v],v][z<1])]
 elif all(v<2for k,v in x):
    for p in permutations([v[0]for v in x],[z,None][z<0]):yield list(p)
 else:
    z=[S,z][z>-1];i=0
    for k,v in x:
     x[i][1]-=1
     for j in h([],z-1,x):
        if j:yield[k]+j
     x[i][1]+=1;i+=1
for v in h(input()):print v

(note: this uses the Python 2 golf of alternating tab and spaces for indents)

There's no need to write "at the time of writing the function is at line 983", you can permalink to the latest commit: https://github.com/sympy/sympy/blob/8ada3462d6c1fbf3d7f733af494da1e055529d92/sympy/utilities/iterables.py#L983 .

@orlp Isn't there a permalink to there already?

@EriktheOutgolfer I linked to a specific commit, not 'the latest version', so that means my link will not be made out-of-date by future changes.

JavaScript (Node.js), 137 128 123 bytes
s=>f(x=c=[],s.map(g=i=>g[i]=-~g[i]));f=i=>Object.keys(g).map(i=>g(i,--g[i]||delete g[i],f(x[c++]=i),c--))<1&&console.log(x)

Try it online!
s=>
    f(
        x=c=[],
        s.map(g=i=>g[i]=-~g[i]) // O(n) if all same, <=O(n^2) if different
    )
;
f=i=>
    Object.keys(g).map( // for(i in g) breaks when other items get removed
        i=>g(
            i,
            --g[i]||delete g[i], // O(left possible numbers)<O(child situations)
            f(x[c++]=i),
            c--
        )
    )<1
&&
    console.log(x)

C++ (gcc), 203 bytes
Apparently C++ has this as a builtin function...
#import<bits/stdc++.h>
using namespace std;main(){vector<int>v;int x;while(cin>>x)v.push_back(x);sort(v.begin(),v.end());do{for(int y:v)cout<<y<<' ';puts("");}while(next_permutation(v.begin(),v.end()));}

Try it online!
Ungolfed code: TIO link.
This use O(n) memory (guaranteed by std::vector) and optimal runtime.
Some optimizations in code:

Use import instead of include (G++ deprecated extension)
Use bits/stdc++.h (precompiled header contains all other headers) instead of multiple necessary headers. Often this makes compile time slower.
using namespace std which is known to be a bad idea.
Use puts("") instead of cout<<'\n' for writing a newline. This is normal for C program, but feels weird for me. So I think this should be mentioned.
main return value (int) can be omitted.

Otherwise (apart from whitespace deletion) it's the same way how I often program in C++.
Some possible optimizations: (I don't know if that is allowed by default):

Enter array size before enter elements. This will allow dynamic-size array, overall save 30 bytes.
Not separate the outputs with separators. So the output will like 1 1 2 3 1 1 3 2 1 2 1 3 1 2 3 1 1 3 1 2 1 3 2 1 2 1 1 3 2 1 3 1 2 3 1 1 3 1 1 2 3 1 2 1 3 2 1 1 for 1 2 1 3. This allows save more 9 bytes.
While in C it is allowed to omit headers, I don't know if there is a shorter way to use those functions without #import the headers in C++, or a shorter header name.

Maybe you should mention why std::sort doesn't make time complexity overflow

Also 2 bytes saved using namespace std;main(){vector<int>v;for(int x;cin>>x;v.push_back(x));sort(v.begin(),v.end());do for(int y:v)cout<<y<<' ';while(puts(""),next_permutation(v.begin(),v.end()));}

#import<bits/stdc++.h>@#define Q v.begin(),v.end())@using namespace std;main(){vector<int>v;for(int x;cin>>x;v.push_back(x));sort(Q;do for(int y:v)cout<<y<<' ';while(puts(""),next_permutation(Q);} @ is newline

Scala (48 bytes)
def%(i:Seq[Int])=i.permutations.foreach(println)

Try it online
permutations returns an iterator over distinct permutations.

APL(NARS), 156 chars, 312 bytes
r←d F w;i;k;a;m;j;v
r←w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m
   v←m,¨(d,m)∇w[a∼i]
   →H×⍳0=↑⍴v⋄⎕←∊d,v
H: j←m
B: i+←1
C: →A×⍳i≤k

G←{⍬F⍵[⍋⍵]}

They, F and G would be 2 function to use togheter...
G first order the array than apply to the that ordined array the function F and write
permutations using the observation that if the element is already found, better not to go
to recursion (because all the result would be already found). I don't know if this fit all
restritions... Test:
  G 1 1 2
1 1 2
1 2 1
2 1 1

  G 1 2 3 2
1 2 2 3
1 2 3 2
1 3 2 2
2 1 2 3
2 1 3 2
2 2 1 3
2 2 3 1
2 3 1 2
2 3 2 1
3 1 2 2
3 2 1 2
3 2 2 1

  G 'abb'
abb
bab
bba


text:
That's a lot of monkeys
The infinite monkey theorem states that, given infinite time, a machine sending an endless stream of random characters will always type any given text.
That sounds to me like a great idea for a challenge.
Process
In order to monkey-ize a string A, the following steps should be taken:

Take an empty string. We will call this string B.
Pick a uniformly random printable ASCII character (characters in the range 0x20 to 0x7E) and add that character to B.
If A is a substring of B, B is our monkey-ized string. Otherwise, repeat step 2 until A is a substring of B.

This process is only an example, easier methods may exist depending on your language. You do not need to follow this method exactly, as long as the same distribution of outputs is achieved.
The challenge
Write a program or function that, given a non-empty string in any reasonable format, returns a monkey-ized version of that string.
Your program only has to practically work for inputs of length 3 or less. For longer inputs, it is allowed to terminate early with or without outputting anything.
Example
Unfortunately, it's kind of hard to create examples for this question due to the random nature of it and the large outputs.
However, I can supply a single example for the input hi, on Hastebin.
Scoring
Since this is code-golf, the submission with the fewest bytes wins.

Sandbox

Do we need to follow the described procedure to produce the output? If yes, that's an unobservable requirement, which is problematic. If not, we can generate B directly by prepending a non-negative number n of random characters to A. The only real problem then is to know the distribution of n (I bet on a geometric distribution)

@LuisMendo I have clarified that in the question body.

@LyricLy I attempted to clarify a small bit more, feel free to revert if you don't like my edit.

So I have a="ant" then b can be: b, be, bet, beta, betan, betant which a is a substring of. Is this correct?

@Goodra I'm not sure what you mean. The challenge is to create random characters until a given text is generated. For example, if the input was hi, the output could be ps.6@}7}RII!x^hi (although this is very improbable; the string is likely to be much longer)

how fast does the case of 3 need to execute?

@Jonah It has no time limit, as long as it returns a valid result.

Can I prepend the generated character to B? The resulting string for hi, would look for ex. like hi%/2T'uF)XS, where i and h were the last 2 chars generated before exiting.

@seshoumara You may not.

@LuisMendo I thought along these lines, and it's actually not easy to generate the prefix directly. It can't contain the target string, including crossing the boundary where it meets the appended string. And the distribution of prefix lengths depends not just on the length of the target string, but its structure as well.

Related.

Some of the solution computer programs below, such as .W!}zH+ZOrd\k, look a lot like what a monkey has typed.

I knocked this up a while back http://monkeys.geotheory.co.uk/

Unless I am misunderstanding I think the theorem states "almost surely", not "always." You could just end up with an infinite string of as if you are exceedingly unlucky lol

C, 192 bytes
i;g(s,b,i,n,j)char*s,*b;{for(b[i+1]=0;b[n+j];++n)s[n]-b[n+j]&&(n=-1,++j);return n;}f(char*s){char*b=calloc(strlen(s),1);for(i=0;s[i];)i=(b[i]=putchar(rand()%95+32))-s[i]?i?g(s,b,i,0,0):0:i+1;}

Try it online!
It's a mess now, but at least it works even for the corner cases...

C,  63   62  61 bytes
Thanks to @Jonathan Frech for saving a byte!
i;f(char*s){for(i=0;s[i=putchar(rand()%95+32)-s[i]?0:i+1];);}

Try it online!

I have absolutely no idea why this halts when it hits s, +1

@ATaco It halts when i grows large enough that s[i] refers to the null terminator of the string (character 0).

Oh, so instead of throwing random characters at it until s is accidentally created, it throws random characters at it until it reaches s. Smart.

As much as I like this answer, I believe it breaks for an input such as "ab" when the rand monkeys type "aab".

I guess you need something like KMP so that this approach can be valid. Assume the input string is ababc and the monkey generate !!abababc will your program halt?

@zennehoy Thanks for pointing that out. It's fixed (and ugly and long) now.

@user202729 Thanks. It's fixed now.

167 bytes

Python, 79 bytes
f=lambda x,s='':x in s and s or f(x,s+chr(randint(32,126)))
from random import*

Try it online!
This is theoretically sound, but will crash early due to python's recursion limits (you can set them further to get longer results)
Python, 84 bytes
from random import*
x,s=input(),''
while x not in s:s+=chr(randint(32,126))
print(s)

Try it online!
This one is ought to work for relatively longer strings, since it doesn't rely on recursion, at the cost of 5 bytes.

You can save three bytes by using backticks to do the string conversion
(shown here as single quotes to the the markdown right) s+'randint(32,126)'

@wnnmaw backticked randint(32,126) would produce a string of the number, not the ascii char mapping

Ohm v2, 10 bytes
Ý£D³ε‽α@§↔

Try it online!
Explanation:
Ý£D³ε‽α@§↔  Main wire, arguments: a (string)

Ý           Push empty string to top of stack
 £          Start infinite loop
  D³ε‽        If a is a substring of the ToS, break out of the loop
      α@§     If not, select a random printable ASCII character...
         ↔    ...and concatenate it with the ToS

C# (.NET Core), 86 bytes
a=>{var b="";for(var r=new Random();!b.Contains(a);b+=(char)r.Next(32,127));return b;}

I don't really like how much creating the Random instance takes, but I don't think there's a way around it.
Try it online!

Welcome to PPCG! Currently your solution does not properly generate a random character since according the the docs, the upper bound passed to Random.Next(Int32,Int32) is exclusive and so not one of the numbers generated. This can be fixed by replacing 126 by 127.

@0                            ' Whoops, I thought about it while writing, but I forgot to check it before posting. Thanks!

There is actually a way around that long Random, you can remove the variable declaration! 79 bytes

@FlipTack Interesting, I tried that in C# Interactive and it didn't work because it just kept generating the same number. Weird to see that it does work in TIO.

Funky, 64 bytes
s=>{S=""whileS::sub((#S)-#s)!=s S+=S.char(math.random(32,126))S}

This uses a few tricks I've been wanting to use in Funky, like a variable name after a keyword as in whileS, and using the fact that strings implicitly parent to the string library.
Ungolfed
function monkey(target){
    monkeyCode = ""
    while (monkeyCode::sub((#monkeyCode)-#target)!=target){
        monkeyCode += string.char(math.random(32,126))
    }
    monkeyCode
}

Try it online!

So would that be... Funky monkeys?

GNU sed + coreutils, 75 + 1(r flag) = 76 bytes
h
:
s:.*:shuf -i32-126|dc -e?P:e
H;g
s:\n::2g
/^(.+)\n(.*)\1/{s::\2\1:;q}
b

Try it online! (It takes a lot of runs to get an answer for a length 2 input, because most of the time you run out of allowed TIO computation time.)
Explanation:
h                                # copy input string 'A' to hold space
:                                # start loop
    s:.*:shuf -i32-126|dc -e?P:e # run shell script: shuf outputs a rnd permutation
                                 #of the set of numbers from 32 to 126, and '?P' in
                                 #dc converts the 1st read decimal to an ASCII char
    H;g                          # append char to hold space ('A\n.'), then copy
                                 #result back to pattern space
    s:\n::2g                     # remove all '\n's from pattern space, but first
    /^(.+)\n(.*)\1/{             # if pattern is 'A\n.*A' (A substring of B), then
        s::\2\1:;q               # search previous regex used and leave only '.*A',
                                 #then quit (implicit printing before exit)
    }
b                                # repeat loop

Benchmark: approximate, for scaling purposes only

input length: 1, 10 random inputs (runs), average time: < 1 s
input length: 2, 10 random inputs (runs), average time: 90 s
input length: 3, 10 random inputs (runs), average time: lots of hours!

Haskell, 100 bytes
import System.Random
s#(a:b)|and$zipWith(==)s$a:b=s|1>0=a:s#b
m a=(a#).randomRs(' ','~')<$>newStdGen

Try it online!
Basic idea is to generate an infinite list of characters with randomRs and stop it once we find the string.

A shame isPrefixOf isn't in the standard Prelude…

Japt, 26 bytes
@(PbU >-1}a@P+=(Mq95 +32 d

Try it online!

Very quick golf while on a smoke break: 22 bytes. Welcome to Japt :)

R, 79 76 75 bytes
-3 bytes thanks to MickyT for changing the random sampler
-1 byte thanks to Robin Ryder for tweaking the random sampler again
function(S){G=""
while(!grepl(S,G))G=paste0(G,intToUtf8(32+95*runif(1)))
G}

Try it online!

hi, your sample could be replaced with intToUtf8(runif(1,32,127))

@MickyT excellent, thank you!

You can save 1 byte with 32+95*runif(1) as your random sampler.

Charcoal, 15 14 12 bytes
Ｗ¬№ωθ≔⁺ω‽γωω

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes due to a subsequent bug fix in Charcoal. Explanation:
    θ           Input string
   ω            Predefined variable `w`
  №             Count number of occurrences
 ¬              Logical not
Ｗ               Loop while true
       ω        Predefined variable `w`
      ⁺         Concatenated with
         γ      Predefined printable characters
        ‽       Random element
     ≔    ω     Assign to predefined variable `w`
           ω    Predefined variable `w`
                Implicitly print

Perl 5, 31 +2 (-pa) bytes
}{$_.=chr 32+rand 95until/\Q@F/

Try it online

You can save 3 bytes since the \E$ is extraneous

indeed, thank you for having noticed

saved 2 more bytes

That's sneaky. Very nice indeed :)

and even more, -3bytes

Sweet. Those whitespaces are an eyesore... there's space in there, make it smaller ;)

Ruby, 42 bytes
->w,s=""{s+=[*" "..?~].sample;s[w]?s:redo}

Try it online!

Octave, 62 bytes
t=input(o="");while(~nnz(regexp(o,t)))o=[o,randi(95)+31];end;o

Try it online!
Explanation:
t=input(o="");               % get stdin and define output
while(~nnz(regexp(o,t)))     % while no matches
    o=[o,randi(95)+31];      % concatenate string with ascii char
end;
o                            % output result

Many thanks to Luis Mendo for the edits!

Welcome to the site! :)

Can't you replace isvector by nnz? And strfind by regexp. Also, you can use randi(95)+31, or maybe replace the whole sprintf statement by o=[o,randi(95)+31]; (implicit conversion to char)

Also, we usually require a function or a program that takes its input (as opposed to defining a variable containing the input) -- something like this

I attempted to do that, but I couldn’t think of a concise way so I skipped it. Nice revisions!

Feel free to incorporate those suggestions into your answer. That's standard on this site

Pyth - 14 bytes
.W!}zH+ZOrd\k

Try it online here.

W!}Qk=+kpOrd\   is 14 bytes as well, SE is messing with formatting because of unprintable but range is generated the same way

Mathematica, 65 bytes
""//.x_/;x~StringFreeQ~#:>x<>RandomChoice@CharacterRange[32,126]&

Try it online!
-3 bytes from Jonathan Frech

I think FromCharacterCode[RandomInteger@94+32] is equivalent to the shorter RandomChoice@CharacterRange[32,126].

@JonathanFrech yes,it is!

Lua, 99 102 bytes

Saved a bug thanks to ATaco, which added three bytes.

function f(B)s=string S=""while not(s.find(S,B,1,1))do S=S..s.char(math.random(32,126))end print(S)end

Try it online!

MATL, 17 16 bytes
''`6Y2TZrhtGXfn~

Try it online!
-1 byte thanks to Giuseppe

Japt, 16 14 11 bytes
;_øU}a@P±Eö

Try it
;_øU}a@P±Eö     :Implicit input of string U
 _              :Function taking a string as argument
  øU            :  Contains U
    }           :End function
     a@         :Get the first result of the following function that returns true
       P±       :  Append to P (initially the empty string)
;        E      :  ASCII
          ö     :  Random character

Java 8, 81 79 78 bytes
a->{String b="";for(;!b.contains(a);b+=(char)(32+Math.random()*95));return b;}

-1 byte thanks to @OlivierGrégoire for pointing me to a (big >.<) mistake I've made..
Explanation:
Try it here.
a->{                    // Method with String as both parameter and return-type
  String b="";          //  Result-String, starting empty
  for(;!b.contains(a);  //  Loop as long as the result does not contain the input
    b+=(char)(32+Math.random()*95)
                        //   Append a random character to `b`
  );                    //  End of loop
  return b;             //  Return the result-String
}                       // End of method

It should be 32+Math.random()*95. There... bug fixed and a byte saved! ;-)

@OlivierGrégoire Woops.. Looked at the hexadecimal code for the space, but regular decimal for tilde.. >.> Thanks for noticing. Not sure how I've missed that, since the output clearly had 'unprintable' symbols..

Alice, 21 bytes
/U!?"$~dr@
\idwz K"o/

Try it online!
Explanation
/...@
\.../

This is framework for mostly linear programs that operate entirely in Ordinal (string-processing) mode. The IP bounces diagonally up and down through the program twice, which means that the actual code is a bit weirdly interleaved. The commands in the order they're actually executed are:
i!w" ~"rUd?z$Kdo

Let's go through this:
i       Read all input.
!       Store the input on the tape for later.
w       Push the current IP address onto the return address stack.
        This marks the beginning of the main loop.

  " ~"    Push this string.
  r       Range expansion. Turns the string into " !...}~", i.e. a string
          with all printable ASCII characters.
  U       Random choice. Picks a uniformly random character from this
          string. This will remain on the stack throughout the rest of
          the program and will form part of the resulting string.
  d       Join stack. This takes all strings on the stack and joins them
          into a single string and pushes that (it does this without actually
          removing any elements from the stack).
  ?       Retrieve the input from the tape.
  z       Drop. If the joined string contains the input, everything up to
          and including the input will be discarded. Otherwise, nothing
          happens to the joined string. This means that the result will be
          an empty string iff the joined string ends with the input.
$K      If the top of the stack is not empty, jump back to the w to continue
        with another iteration of the main loop.
d       Join the stack into a single string once more.
o       Print it.

Perl 6, 39 bytes
{("",*~(" ".."~").pick...*~~/$_/)[*-1]}

Try it online!
(...)[*-1] returns the last element of the sequence defined by ..., of which:

"" is the first element;
* ~ (" " .. "~").pick generates the next element by appending a random character in the appropriate range to the previous element; and
* ~~ /$_/ is the ending condition, which is that the current element matches the main function's input argument $_ as a literal substring.

You can lose the *~~ for -3 https://tio.run/##K0gtyjH7n1upoJamYPu/WkNJSUerTkNJQUlPT6lOSVOvIDM5W09PT18lXl8zWkvXMLb2v7VCcWKlQpqGekamuqb1fwA

05AB1E, 10 9 bytes (-1 @ Emigna)
[žQΩJD¹å#

Try it online!

Do the monkey with me.

[              | Loop forever.
 žQ            | Push 0x20-0x7E as a single string.
   .R          | Pick from it randomly.
     J         | Join stack (B) with new char.
      D        | Duplicate (B).
       ¹å      | Push input (A) and check if input (A) is in (B).
         #     | If the previous statement is true, break loop.

You can do Ω instead of .R.

Lol, using an Ohm, to beat Ohm v2. How nice.

QBIC, 33 bytes
≈instr(Z,;)<1|Z=Z+chr$(_r32,126|)

Explanation
≈instr( , )<1|   WHILE InStr() can't find
         ;        the input (cmd line string argument) as part of
       Z          the output (Z$, which is printed automatically on exit)
Z=Z+             add to the output
chr$(         )  an ASCII character
     _r32,126|   with a random codepoint between 32 and 126 (incl)

Sample run:
Command line: hi

`;7L3f$qy )H99tZ@>(-Z1efL|Q-5'BE=P8BdX?Lem/fp|G#~WY[ Q4s9r~Af*T})P4`4d$#ud3AiuTwQPFS@8c7_59C$ GlJ%iJ[FA(rNt<y>Hl=r,wSbBB%q!8&#*CixWbnwE."wrZ:R53iKJkN*@hpQt aMj6Mw<KfT@hkik>_k'_>$~3)jl|J!S`n\Yw|lXi:WAKWp?K"F.cAGI/:~uR8*[;Die{]B*]@;Vhjv,$9]Ys:AIdy!j{aXlr:0=txCP-n{/3lgq,;jXaP\]u}.Zl/7eKF+N54[J9^r:>%/.e~*9aK%de>^TW%p%(_uJPvuV%d<&]zu`t;vkEPC>7pofok0Kj}j?9G{TUxSccth)[)J>@'E)NMzA(i!UV7%;$.Z#j3q@#9Q%}<" &VsbL*<SrG-$NC MAQ\`iIT+.P|5}nv )FZl5_.Kc*AUV9u&fvk.USt3Y!s7^UEL{|D$k#k8.9Fgqn#3dgr(0G.gw1#j$HfU3a|)3-O(d<)<A|`%pJ^/\{[w[H4N/>8J@z/YNsU,zY4o*X+h\Dy!~)Xr8.3"%.39v0d5_-8QBYR".Z]MZ}N>9e?f@hj#hor1IhJ[krrHOamRPxQC>^'dOh,cF_e2;8R@K**Jsx_~t9r~4J$Y;kPsb)8w~:o-`@MwP]OA{8yD%gL(=&M>$nTKw] R[}rS|~}&*gD 'g|gRSDLld+`,,}(1=]ao3Z%2*?wlqU$7=$8q$Fig:7n&+XKQ LV/Aq?BYl_*Ak-PqI$U_>`/`-yD5.3|Zg>,mC"RC`IV^szu:I;0ntn(l'/ZnK}T&i)9!zkd?7Ec/X+IN=-5wwsSV@^<?:K=9m%*@C;zDjc%:d>/E@f7@0NVt4Vz/E;8*0A25F1:JUQ/G#2)un9hQI>2^}&+cY+JP*-#$p+cFs}R|>E;w#q>pN"Jkv<>E_ZtCvV05Lh;0 9bCBXgA7aIe+9B1<G)YCH\Yqn.0%g$_4Q4 xIR)gt]W*a|gGX}hP4b)6#M:Dh!kmuX;nW]'n]Mm5y=ET|O9p\,j>Bc|7J5I%UCZla-2g(Mm9cE"}c1Q0@yTF|A\FJbR7_(F_G#@mE/~ [9T~|Ty9~0=g {a^IM{]C9%2FBJ:b&i5A{rqu/xw6q|_[$Sj&W\TnI}/>.EJ1dSbSOtr_Qtuf!IF .WU}&M51+VAnJ)W}^c5qwQ<G05}/aZ99l6iqyD|Zr8SV9L}8FbUz7_H<]A|.vFQXSu2@67%83HP4]Gw0PuPNQ6SOM_[BcdK-s}Z(~~i:^N$GZn_sMcp*i,w-2VfK*LA$Btmg6QEohqym3[RRqUAM"9pE>N)(.TNMQ"U~ e2($wz(Kdh;0ol8>SXHEnLvrs.Xtl^L?SL1$*ssD _={{}(`qKCy{]W:AZT}Zro5qN:;mNp#EPfg?_],,cFP?EhGs/OAt}fgVSR<JW^HkWf'@^Vd9\_Y?P*>C'YP jqvXu)ZFwzY)/MLHcRL/P?jBi9"d\  E$ngpq-i*;EW6R)J|[0FfZSTozuSq,sAJT<<4al<zM\F(|gTD0/Vt6JL.p_x_oC)V'zWZ`8eA9@*WgZ>',-}Q^5#e552&"\i1HI]{)]WcI.cY0n9J<jaT.!l{r4Dz~nt`AEP-6,FHhf6(PSywIedr }=9V>Q7!+~L^O3'Crdv"hfv#xrs@](EO;&#)0]oC][z*Eh`k!$V!r6~#-Vfk1p#w&Za6Ij\@V<TNf4njdynOch7l?XwU  `SON\iizU3%S^X2XKY.w%:zAVY^KlIhZ8]d39No3P89v`1FxKTLQa+7"rd9bm2)a^Pu=~.9VDh?v"%$9evl9+l7n$I?qA[b:kH2?5Tg&(!H(*}hZ3z@bg+Zj!# JnO2FV_glCMweT;b|>g4!h{4@ p w`lH \Y8(uPf7nbJY]r>('-$O?5Xd:h&:y!i%2dRC_8=3! |b="H|jxx)k!\D|]Lsdz1.v[a<l/Y3?0/&H%2.qvPp'ZNpO;rhvtnl0*Bs4Qlh0}_dv6g0`pJh'==]9LuzG+qUGz5.j[$I{4.b_o;S`QFucC9>`z7M.wHx!wy-JeOf)^9#Z.xl7e"9q)OE-SSD"VbLFm-u'-<4~(_h\KqNk7}vKh0E&!LaxAma|FOIY,\C$;!v^#4,eqwpE]Jqp,]IkTz,,L`kx|\i^#{PV0/8K?N,W!L=vbh\OJ7?:k=~{zLw8*/W<-qFDKAhx1F;\NL@{=rlo0''YB;B5<:0e5J)w"0l@FE?J:FW(I|)3BZ'hL7[}Ez=jc(rLkY9d{Zzgq7Cj)bej/X!@TP7x.r"Arz7IU;1|.3by~\h{V57}A^w7v5gMC]@B~1i5*uY 7?(IN6hQ/b/4bMpDmT_"n|;bBx|74(ReQ.^])bHC+:!s bk_S]R}<Ow:7CCu_P!$:mz{[aiGg*AD#}m~D_rhVr6!x]PY5n'qiMMlpqoU>C`,W}y9Yi4hHf<lcwvga`h(<=jURq\d+2SRGA1GP**D]i+Tp@*hpe([-JE^M@5jHgK~>hY>Bo&% \e/\&]"K])CV%oNJ}[_Q1}w(p3uJ+\/;{0TB8#{=&l8s;]L7Gr;a_[cN:#%$)?*:HLZ;&n|2_8/@=B [>|R3@xk<c+bIyb>h`]:c]RLt(M!69PNE?}>@CHT>jNevl81PCgHu0ap0~Pcq?Z@>+yTFw\E=10&fpS+=/l|.ioPn$B.M\4{2?q-^,)f&S4X44(Rycome[Ot[t(8CAphj[h}E/A~BR[6Y&Hm1_tsxs4BB0cwo\",r_c~s/vT}kKu3U(Emb|%"`OAmV7$,\<O7)c&F==mc~dM:qX^[K-9<3u8hfgTUP19aXk,7g(4>jLt,*N!EXGE#XzN}>7@EH4n}k!&a[j,Ynd#!M<suhnBP /J9}h>vRyXuADk"+v}?hOm6*U^x\G'!Y(TDC?EE|r}5yx4PB 1;9q.%/kg7p2ImS62+/|K,xSDf3b6JRY+8~mxikSU^&3A3|/j9}fIESN45kdi*h64!XE'_0?Pw{MeK$DeXP]5M{7sLD!dj5HrAc\N I`~o/%MqyIIsFee]A?j7ZZ}f'dN#"V''g-G0@zNajp=v<"r2s;>@.UM9L\Mq16e/961d.3a6h.hMrUREa^wR^s*\Tc6Yn]DT.Nc77p|h s2@hC\Rxy|XhXi.OL2$\pwPSJET;u7V`U!<]M(tibt>.gD'JKe{7r8?Z[]ExGHxyd\,/wjfBI'NKCpaU19-?f;;QVrWnFF,zvJY|d\DrcysAO'; 33CSNy_GlLr\v)Ir\qQfwT'I#t:N-{,x#zGR.)gJqq%!zF.oJ;]*TI+4z>JQAGQM3w&zgani8JwZW6S!r-ig\3jD}]2*.Aen8O)L?X.UTZ6)mOtUIm_=3fA'_::vV_#+c+=evf#{8lk+`)M\_c+I<|*LRZOU]:eQ*/KER#f,vEC?4yXE*8wlzk?b)&[gF'(0|$@+4CT4#lfEKxP~;oo%1+=yw#J*s}D7p1fU~^gD1Ib{H|PWer^q"q=?Pxf<)tvu7{HDvl\kqb"b/|s>|h.qQu[$F/:~*dy9cl16}dKXY~N7aptCSv+da/S5-,qnwBhRi+lh8=Qy{er:#Oos|e?(US>"767KVe^nz<$]gM)~J>{I7n~!k[U\1{8Z8u6T(ft?kgdQO,LvY/TDAe\wS~Y U>\.aQYhQ;h1nuW$R/wpz_EiB-%gf87qgQei(P-ft:TSW,HtsPez"5<8?yR`wm7pjMn^|8Y.4[RVWq#aW$0EB9"O:%@q[&F[_'2yt2k]S5~HCN1+^bS>N2C/7ChHCHNrJ8,kBbNsu}37LH^n.B+tyE*s7l(Tc<;4.tvBw3LP=nK4G'6M(z086;"??9XE.(X>nvmm()P2m\"LeqbcOC~Vw;u/Q^T)52/pM3+<GkFWJ?30{/n2FQq QjO#pt8oN$kK/a+|Hbw@5m8M[EFWq>%cV2[X@q}gJ"9kt9'~]4p+2~LT9|4Ss^qoXw%P#M!!]TBQbp;PYg{WCj,RF<#bNJTS,CUH{][hY"q;[?#apc%Cl&QWVi]ffYG}bzx .;*/rqRhb[XatPu.Piws<mo=]!e>p%yu\;fCzJ0Xz]6]9S:WRlYS,mC&7Zjb)+DjJUkSF3TJG;8fQ4|>t%qgW1$_V:p;|Q":Z!UngSL{*Ky+/zh [I{_3?]h^x37"`^'/U>EPqal'&Txf,I>gr2HO_y!QM-ch~%m-(AE6U~[A"D@j1hu?6p2"Wc'3nyqfs!.UQy}I%0(z5dPmORFBK1,<PfYersnLe<fLhB=^g pwXnWDOQNuIPEpnm8.Q6jN|a7tcuSH$9T;! d~VQn{'(-4{caLa;t?~|>q:on:Bgs'FQ'2-<%W<3Px=4Uf;@;R3yZECK?f(5K?`^lQY\ok},`Q9*Q}3].Y!BkRt"3@]Lz&ec'NB?n[%0kQ9/55BOZ)o!P>fpXZI:#?Ly#\o.`+HX Kb0@P^1qS%bGip1`)qH@-k\oOGs%;}_Nq{uPq |!K)01w(?X=>bSR[(]ZQ<Z1]bD9M.F<<.8EB6JlEUOk6r;SrVZNT2 m>zp3]a_sK eq8]rK^.U&!d62HBt`v?t6uc#3s<{[CmYE24+ujEx`$##R2g\b!PvK<8+lUhyT|p"SUco/aUh.fXBV(!!)8PfQIr6R,r8c-F-mjua;:z4!Q1pA!H0E%)"K2oUv|DV+lg,h8W?<JnIkiV/us::*l&I<OI6NO)Tnq0-uDRG5*LX#wU{8WpMlw3Z'7zGi*loo2{=hWSY*0/o9BwtJ$Hw}l94nA^9>48(3gDnt8CS|R3? OH[N/9j1r%vUcox\68{yFemlmmtp*q5kfrlIo`3yQB??6jW:TW+)':K#]^=ilF_/N!)=}y@k.y//nhChX!3b`=t,1_KhR,n]/_.-P>B80W#'E%J[g?ti)*;Yl]}r0>qh/X[{=)Gr '[+pz|DI=mA8zj~yAT*^7w%tV0l=V^/#2W>)f)X%f^L&+Un}VlQt3.%gEKbE!7`adTb#`}i!F$-Gug]@*G,hKe;/p,`Mb@wBJ4<V&jJd&_H4VR{Hc"{2<l<QapiLw(JK-2-[1_.WR.@CG$?\1<&( QX5c9 :z^jDW09(=iH V/vkcJ8D<uLAr$dbc$Hl'2KTUlbrd8kD{B0Eeu<&oL2s.S4@Jo$zVq~BqeLsb;k-NG/'iU|)W_:X-.XUc<v\elx57ZZ"R!y_yzve*Wlt>.fE,#Eh:(#gn1kSQ+/3NYjD']I;"+@pnW[1EA.AyqM4,0,dJt.?r2oab.j\k@)BsZ|s39FdL87xyuJ0nXX=yz^~W,}acDZp8ukCpv^<^{CkRS<=GsS$}#fbP5%A$GHdg)+WZLLN9[ue073Q!F"J;X^49*$R'W%C.r~Fj&B`)tq[01a4En%H,kvyZG|,)%$44rJg[tq<wG9FjN<m@larki#;Bns%D}v_efPRH(OeRq0{=>Uc[~xcTcV_9|k54Q2*N.3]LlmFasY3"p =$$onbg$M+ReRsnH|9gV~#2?c1-V$35."DZH-O$~,c.gs]%,]p4\OFIW%l:,E,YT8FCeU8hy#lNq1lCpS 0I&q_*q>|=,(-dHuzi~6$GW22*A\w*&R< W`$HPRr,2A}3w\"Y?d%{2^xP:GqI\26A|.e'H2Z[M4=P.H87O~{)9|B*tHAC\j^S,StW!*snsz82R!:eD@uB4x+x&zSIN(3V|.^N_$=i=p}iK4h'v"$:I<t e:Y/XrSOF83=lkVNa0^k@jB@{ARE@r=Bja`(Bw>@?+`Wo,= u5HhXPeRMXS4@H#$-Jwg2"2-]%7p.o2Ar9J6Y1Ra?"3<oee&bpO^O{nw9=%\0brVNXrelWGoJyb/5W%MB0UBaPsc*29K<N~``NriWM$"eY0@xh^<$b:E/J~S%{#ry~6d?4Vv@^&9'=iBA#2U]bj9>UoJ#wQDN~6cB&/_Pu-XF?_hu3><(M7RW\%Ly@rTC9^b`?kVL~w%[{!&{#aS7<mc@J>ZaN7s}Y.c0:Y.\d&_[L{m|>|>%J^@!i9y0_lwejChi

PHP, 55+1 bytes
while(!strpos(_.$argn,_.$s.=chr(rand(32,126))));echo$s;

Run as pipe with -nR. Not suitable for TIO cause of probable timeout.
Insert a space between the quotation marks for PHP older than 7.1.
This 51+1 bytes version will fail if input is 0:
while(!strstr($argn,$s.=chr(rand(32,126))));echo$s;

Javascript 74 bytes
s=(a,b='')=>~b.search(a)?b:s(a,b+String.fromCharCode(32+Math.random()*95))

call like this:
s('hi')

@Giuseppe thx, I have it added in the byte count

I think you have to change 94 to 95 for the code to be valid

@Hawkings Yea, you're right, fromCharCode ignores decimals it seems. Thanks for pointing it out!

Save a byte with ~b.search instead of b.includes.

@Shaggy Nice! Didn't know about search

Pushy, 20 18 bytes
LFZ^tCN[,` ~`U'x?i

Try it online!
The program keeps a stack len(input) characters long, and constantly removes the first and appends a new random char, until the initial input string is reached. Each character is printed as it is added, creating the desired effect.
Explanation:
                      \ == SETUP ==
 F                    \ Put input on second stack
L Z^tC                \ On the main stack, make length(input) copies of 0
      N               \ Remove printing delimiter (newline by default)

                      \ == MAIN LOOP ==

       [              \ Infinitely:
        ,             \    Pop the first item on stack
         ` ~`U        \    Add a new random character (between 32 and 126)
              '       \    Print this new character
               x?     \    If the stacks are now equal:
                 i    \        Exit program

Julia 0.6, 53 bytes
a->(s="";while !contains(s,a) s*=randstring(1) end;s)

Try it online!

Brachylog, 17 bytes
I⁰∧Ẹ{sI⁰&|;Ṭṛᵗc↰}

Try it online!
I⁰                   The global variable I⁰
                     is the input,
  ∧                  and
   Ẹ                 starting with the empty string
    {          ↰}    call this sub-predicate again
            ṛ        with a random
           Ṭ         printable ASCII character
          ;  ᵗc      appended to the string we're building
         |           unless
      I⁰             I⁰ (which is the input)
     s               is a substring of the string we've been building
        &            in which case the string is output.

Can randomly stack overflow. This makes use of two recently added features in Brachylog: global variables, and the apply-to-tail metapredicate ᵗ.

Bash 94 bytes
p=printf\ -v;until [[ $s = *"$1" ]];do $p x %x $[32+RANDOM%95];$p c \\x$x;s+=$c;done;echo "$s"

Try it online

Excel VBA, 84 bytes
Dim b
Sub m(a)
b=b &Chr(Int(113*Rnd+14))
If InStr(1,b,a)Then [A1]=b Else m a
End Sub

It's a straightforward implementation. Output is to cell A1 in the active sheet

Pyth, 13 bytes
W!}z=akpOrd\

where the unprintable character is 0x7F.
Test

Jelly, 17 bytes
³ẇ®¬
ḟµ;©ØṖX¤ø¢¿Ḋ

Try it online!
Explanation
³ẇ®¬            First link
³               Program input...
 ẇ              ...is a contiguous sublist of...
  ®             ...the register?
   ¬            Logical NOT

ḟµ;©ØṖX¤ø¢¿Ḋ    Main link
ḟ               Filter: With only one input this returns the empty list. Note ⁸ doesn't work here.
 µ              New monadic chain
    ØṖX¤        Random (X) element from printable ASCII (ØṖ).
  ;             Concatenate with the above
   ©            Copy the result of the concatenation with the above to check if program input is a sublist.
        ø       New niladic chain.
         ¢      Calls first link.
          ¿     Repeat the monadic chain until the first link returns false.
           Ḋ    Removes the first element of the result.
                For some reason (???) the integer 0 is always at the beginning of the result which needs to be removed.

Tested with one and two character inputs (two character sometimes takes a long time or seems to stall) but should work in theory for any length input.
The recursive solution I came up with below is slightly longer.
Jelly, 19 bytes
³ẇ®¬
;©ØṖX¤ßµ¢¡
ḟ`Ç

Try it online!

J, 38 33 30 29 bytes
-9 bytes thanks to FrownyFrog
(],a.{~32+?@95}.~1#.E.)^:_&''

Try it online!

(],a.{~32+?@95}.~1 e.E.)^:_&''

Nice.  I didn't know that '' -: 99 + ''

1 e.E.-> 1#.E.

PowerShell, 55 73 bytes
+18 thanks to mazzy bringing it up to spec
for(;$args-cne-join($b+=[char](32..126|random))[-"$args".Length..-1]){}$b

Try it online!
First, it picks randomly an int from the printable range, casts that to a character, and appends it to our accumulator string. The monkeys will always form the word with the last character so keeps going until the ending of our generated string is the target word. So with that fact, it then compares the last n characters joined into a string (via reserve indexing) to the target.

nice. but it works incorrect when $args contains the special chars * and ?.

Try it online!

@mazzy Danggit. Thanks for the fix

Why don't you go back to your previous version, but do -cmatch"\$args" instead of -clike"*$args"? Try it online!

@AdmBorkBork Because that breaks in multiple ways depending on what the target string is

Haha, yes, I was just coming back to delete my comment after realizing that. lol

@AdmBorkBork Shoot, wish your version worked.

too many chars to escape with \  : 87 bytes. And I'm not sure that special characters can be escaped in like operator.

Thunno 2, 11 bytes
""($Ƈ~;kcɼ+

Attempt This Online!
Explanation
""($Ƈ~;kcɼ+  # Implicit input
""           # Starting with an empty string,
  ($Ƈ~       #  while the input is not in the top of stack:
      ;kcɼ+  #   add a random printable ASCII character
             # Implicit output

Vyxal, 14 13 11 bytes (Test it)
¤{:?c¬|kQ℅+

Thanks to lyxal for -2 bytes!

Try it Online! for 12 bytes

or Try it Online! for 11 bytes

JavaScript 91 bytes
for(b="",a=prompt();b.search(a)<1;b+=String.fromCharCode(~~(Math.random()*95+32)));alert(b)

Noether, 24 bytes
I~a""~b1(b94R32+BP+~ba/)

Try it online!

Perl 6, 52 bytes
{("",*~(' '..'~').roll...*).grep(*.contains($_))[0]}

Try it online!

Emacs Lisp, 113 bytes
(lambda(a)(let((case-fold-search)(b""))(while(not(string-match a b))(setq b(concat b(string(+(random 95)32)))))))

Try it online!
Try-it-online version has an additional byte for printing purposes.
(case-fold-search) assures string-match proper casing, it can be omitted
depending on your Emacs configurations (18 bytes).
Better readable version:
((lambda (a)
    (let ((case-fold-search) (b ""))
      (while (not (string-match a b))
    (setq b (concat b (string (+ (random 95) 32)))))
      )))

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Draw 'Til You Drop
In Dungeons & Dragons 5th edition (as well as most other editions), there exists a magic item called the Deck of Many Things. It is an incredibly powerful item, as the cards all have very strong positive or negative effects. To use the deck, a character declares a number, and then draws up to that number of cards, with the effects applying in sequence. If the character does not draw all of the cards that they declared, and it has been at least 1 hour since the last card has been drawn, the rest of the cards are automatically drawn for them and the effects applied. After each card is drawn, it is returned to the deck, and the deck is shuffled.
The following is a list of the effects of drawing each of the cards1:

Balance: Your mind suffers a wrenching alteration, causing your alignment to change. Lawful becomes chaotic, good becomes evil, and vice versa. If you are true neutral or unaligned, this card has no effect on you.
Comet: If you single-handedly defeat the next hostile monster or group of monsters you encounter, you gain experience points enough to gain one level. Otherwise, this card has no effect.
Donjon: You disappear and become entombed in a state of suspended animation in an extradimensional sphere. Everything you were wearing and carrying stays behind in the space you occupied when you disappeared. You remain imprisoned until you are found and removed from the sphere. You can’t be located by any divination magic, but a wish spell can reveal the location of your prison. You draw no more cards.
Euryale. The card’s medusa-like visage curses you. You take a -2 penalty on saving throws while cursed in this way. Only a god or the magic of The Fates card can end this curse.
The Fates: Reality’s fabric unravels and spins anew, allowing you to avoid or erase one event as if it never happened. You can use the card’s magic as soon as you draw the card or at any other time before you die.
Flames: A powerful devil becomes your enemy. The devil seeks your ruin and plagues your life, savoring your suffering before attempting to slay you. This enmity lasts until either you or the devil dies.
Fool: You lose 10,000 XP, discard this card, and draw from the deck again, counting both draws as one of your declared draws. If losing that much XP would cause you to lose a level, you instead lose an amount that leaves you with just enough XP to keep your level.
Gem: Twenty-five pieces of jewelry worth 2,000 gp each or fifty gems worth 1,000 gp each appear at your feet.
Idiot: Permanently reduce your Intelligence by 1d4 + 1 (to a minimum score of 1). You can draw one additional card beyond your declared draws.
Jester: You gain 10,000 XP, or you can draw two additional cards beyond your declared draws. Discard this card after drawing it.
Key: A rare or rarer magic weapon with which you are proficient appears in your hands. The GM chooses the weapon.
Knight: You gain the service of a 4th-level fighter who appears in a space you choose within 30 feet of you. The fighter is of the same race as you and serves you loyally until death, believing the fates have drawn him or her to you. You control this character.
Moon: You are granted the ability to cast the wish spell 1d3 times.
Rogue: A nonplayer character of the GM’s choice becomes hostile toward you. The identity of your new enemy isn’t known until the NPC or someone else reveals it. Nothing less than a wish spell or divine intervention can end the NPC’s hostility toward you.
Ruin: All forms of wealth that you carry or own, other than magic items, are lost to you. Portable property vanishes. Businesses, buildings, and land you own are lost in a way that alters reality the least. Any documentation that proves you should own something lost to this card also disappears.
Skull. You summon an avatar of death - a ghostly humanoid skeleton clad in a tattered black robe and carrying a spectral scythe. It appears in a space of the GM’s choice within 10 feet of you and attacks you, warning all others that you must win the battle alone. The avatar fights until you die or it drops to 0 hit points, whereupon it disappears. If anyone tries to help you, the helper summons its own avatar of death. A creature slain by an avatar of death can’t be restored to life.
Star: Increase one of your ability scores by 2. The score can exceed 20 but can’t exceed 24.
Sun: You gain 50,000 XP, and a wondrous item (which the GM determines randomly) appears in your hands.
Talons: Every magic item you wear or carry disintegrates. Artifacts in your possession aren’t destroyed but do vanish.
Throne: You gain proficiency in the Persuasion skill, and you double your proficiency bonus on checks made with that skill. In addition, you gain rightful ownership of a small keep somewhere in the world. However, the keep is currently in the hands of monsters, which you must clear out before you can claim the keep as yours.
Vizier: At any time you choose within one year of drawing this card, you can ask a question in meditation and mentally receive a truthful answer to that question. Besides information, the answer helps you solve a puzzling problem or other dilemma. In other words, the knowledge comes with wisdom on how to apply it.
The Void: This black card spells disaster. Your soul is drawn from your body and contained in an object in a place of the GM’s choice. One or more powerful beings guard the place. While your soul is trapped in this way, your body is incapacitated. A wish spell can’t restore your soul, but the spell reveals the location of the object that holds it. You draw no more cards.

(card descriptions copied from the D&D 5th edition SRD)
Some especially foolish players will draw a large number of cards at once, hoping to get at least one powerful boon to balance out the detrimental cards. As one might expect, this often results in the character's death or inability to continue to draw cards.
The Challenge
Simulate repeated drawing from a 22-card Deck of Many Things, outputting each card drawn, stopping only when one of the following conditions is met:

The character dies (via drawing Skull, or drawing 5 cards after drawing Flames or Rogue, without the benefit of The Fates or Moon active2).
The character is incapable of drawing more cards (via the effects of Donjon, Talons, The Void3, or the character's Intelligence score dropping to 3 or lower via Idiot4).

Rules

The character's alignment, level, XP, and possessions other than the deck do not matter.
The character's Intelligence score starts at 10.
There is no maximum limit to the character's Intelligence or their stockpiled uses of wish.
Uses of The Fates do not stack.
The wish spell has a 1-in-3 chance of causing the character to never be able to use the wish spell again, in addition to its regular effect. If this occurs, the character can no longer use the spell to negate Flames, Rogue, or Skull - the power of The Fates is their only recourse.
The character always makes the following choices:

The Fates and Moon are solely used to get the character out of trouble from Skull, Flames, and Rogue. The character will never use them to reverse the effect of Talons or the wish spell being unable to be cast again, and cannot use them to reverse the effects of Donjon and The Void. The character will immediately use one wish spell to negate the effects of Skull, Flames, or Rogue upon drawing one of them, and it will always succeed. The character will always use The Fates before using wish.
The character always chooses to draw more cards with the effects of Idiot and Jester (appropriately).
The effect of Star is always used to increase Intelligence by 2, to avoid having to stop drawing cards via the effect of Idiot.

The NPC ally summoned by Knight is not powerful enough to save the character from their untimely demise.
Any increases or decreases to Intelligence (via Star or Idiot, respectively) must be reflected in the output (either by noting the change (+2 or -(1d4+1)), or by outputting the current Intelligence score after the effect takes place).
Any changes to the number of wish uses the character has stockpiled must similarly be reflected in the output, including a wish causing the character to not be able to use wish anymore.
All random selections are from uniform discrete distributions.
You may choose any set of 22 distinct outputs to output for the cards drawn - the cards' names do not have to be used.
You may output changes in Intelligence, wish uses, and wish becoming unusable in any consistent, unambiguous manner of your choosing.
The character may use wish or the power of The Fates to avoid death if the appropriate card is drawn as the fifth card after drawing Rogue or Flames. Only if wish is unusable or all of the uses have been used, as well as The Fates is not drawn in time or has already been used, will the character die.
Fool and Jester are discarded after they are drawn. All other cards are immediately returned to the deck, and the deck is then shuffled.
If there are multiple stacks of Rogue and/or Flame active, only one use of The Fates or wish is necessary to dispel all of them.
Drawing multiple cards at once via Jester or Fool does not advance the turn counter on Flames and/or Rogue.

Examples
Each line represents a sequence of draws. Changes to Intelligence and wish uses are shown by the current value in parentheses. A C next to a wish use denotes that wish cannot be used anymore. A F denotes that the power of The Fates was used to avoid death. Additional comments are provided for explanatory purposes, in the form of Python-style comments.
Void # Can't draw with your soul ripped out of your body.
Throne, Euryale, Rogue, Star (12), Donjon # Can't draw while in suspended animation.
Moon (3), Throne, Sun, Flames (2), Fool, Idiot (6), Flames (1 C), The Fates, Skull (F), Skull # Two uses of wish were used on the two Flames draws. The second use rendered the character unable to use wish again. The Fates was used on the first Skull. When the second Skull came up, there was no way for the character to save himself, so he died.
Idiot (5), Star (7), Idiot (3) # Too dumb to draw.
Sun, Star (12), Talons # Talons destroys the deck.
Fates, Throne, Moon (2), Fates, Skull (F), Skull # Fates doesn't stack
Fates, Flames, Euryale, Fates, Skull, Void
Flames, Comet, Euryale, Gem, Knight, Key # 5 draws after Flames, the hero dies
Rogue, Balance, Throne, Gem, Idiot (8), Vizier, Sun # 5 draws plus one extra from Idiot

Reference Implementation
#!/usr/bin/env python3

import random

deck="""Sun
Moon
Star
Throne
Key
Knight
Void
Flames
Skull
Ruin
Euryale
Rogue
Jester
Vizier
Comet
Fates
Gem
Talons
Idiot
Donjon
Balance
Fool""".split()

random.shuffle(deck)

int_stat = 10
wish_uses = 0
wish_expired = False
fates = False
turn_count = None

while True:
    card = deck.pop()
    if card == "Fates":
        if turn_count is None:
            fates = True
            print(card)
        else:
            turn_count = None
            fates = False
            print("{} (F)".format(card))
    elif card == "Moon":
        wish_uses += random.randint(1, 3)
        if turn_count is None:
            print("{} ({})".format(card, wish_uses))
        else:
            turn_count = None
            wish_uses -= 1
            print("{} ({}) ({})".format(card, wish_uses+1, wish_uses))
    elif card in ["Flames", "Rogue"]:
        if turn_count is None:
            turn_count = 5
        if fates:
            fates = False
            turn_count = None
            print("{} (F)".format(card))
        elif wish_uses > 0 and not wish_expired:
            wish_uses -= 1
            turn_count = None
            wish_now_expired = random.choice([False, False, True])
            print("{} ({}{})".format(card, wish_uses, " C" if wish_expired else ""))
            wish_expired = wish_now_expired
        else:
            print("{}".format(card))
    elif card == "Idiot":
        int_stat -= random.randint(2, 5)
        print("{} ({})".format(card, int_stat))
        if turn_count is not None:
          turn_count += 1
        if int_stat <= 3:
            break
    elif card == "Star":
        int_stat += 2
        print("{} ({})".format(card, int_stat))
    elif card == "Skull":
        if fates:
            fates = False
            turn_count = None
            print("{} (F)".format(card))
        elif wish_uses > 0 and not wish_expired:
            wish_uses -= 1
            turn_count = None
            wish_now_expired = random.choice([False, False, True])
            print("{} ({}{})".format(card, wish_uses, " C" if wish_expired else ""))
            wish_expired = wish_now_expired
        else:
            print(card)
            break
    elif card in ["Donjon", "Void", "Talons"]:
        print(card)
        break
    elif card == "Fool":
        print(card)
        if turn_count is not None:
            turn_count += 1
    elif card == "Jester":
        print(card)
        if turn_count is not None:
            turn_count += 2
    else:
        print(card)
    if card not in ["Fool", "Jester"]:
        deck.append(card)
        random.shuffle(deck)
    if turn_count is not None:
        turn_count -= 1
    if turn_count == 0:
        break

[1]: Technically, there are two variants: one with 13 cards, and one with 22 cards. We're only concerned about the full 22-card version here.
[2]: Flame and Rogue don't normally outright kill the character, but the hostile NPC is assumed to have found and killed the foolish character after they have time to draw 5 more cards. The spectre summoned by Skull
 is extremely difficult to fight, and it's assumed that the character doesn't win. Only divine/magical intervention via The Fates or Moon can save the foolish character from their death by these 3 cards.
[3]: We assume the character's friends are smart enough to not try to rescue the character and allow them to draw more cards.
[4]: An Intelligence score of 3 is roughly equivalent to a wild animal, which wouldn't be able to actively make the choice to draw cards.

Sandbox

Might be good to include some more example runs where a) the five turns expire, ideally with some bonus cards drawn in between, b) the fates is drawn twice, with and without making use of it in between.

Your reference implementation doesn't let the wish expire if it's used the moment Moon is drawn. And it also doesn't check there whether they have expired already.

One more thing: the original D&D rules mention additional cards for all of Idiot, Fool and Jester. Your rules first state that the player draws additional card for Idiot and Jester but then clarify the rule counter for Fool and Jester, and your reference implementation seems to draw only additional cards for Fool and Jester. Could you clarify/fix this?

Are we allowed to output wishes, wishes_used and intelligent even when no chances in their value occurred?

@KevinCruijssen As long as you do so unambiguously, yes.

In the first of the new examples, couldn't you still use one of the two wishes to avoid the second Skull?

@MartinEnder I think the second-to-last (Fates, Flames, Euryale, Fates, Skull, Void) ends because of the Void, not because of Fates.

@KevinCruijssen isn't that the third-to-last? I meant the one after that and it's since been fixed.

So I'm assuming this is draw-and-put-back? Or can each card be drawn only once ? Should we reshuffle when the deck runs out? Does 'Discard' mean it gets removed from the deck ie can't be drawn again in the future?

@steenbergh I also read past it at first, but "After each card is drawn, it is returned to the deck, and the deck is shuffled.". Only the Fool and Jester will be removed when drawn, everything else is placed in the deck again and reshuffled every time before a new card is drawn.

JavaScript (ES6), 379 bytes

for(D=[...Array(21)].map((a,b)=>b),d={},i=10,w=e=f=t=0,F=_=>f=t=o=0,W=_=>{w--,t=0,o=w+(e?' C':''),e=1>r(2)},r=a=>0|Math.random()*a,$=1;$;){for(;d[c=r(22)];);o='',c?3>c?(t&&(t+=c),d[c]=1):4>c?f?F():0<w&&!e?W():$=0:7>c?$=0:9>c?(!t&&(t=5),f?F():0<w&&!e&&W()):10>c?(w+=1+r(2),t?(t=0,o=[w,--w]):o=w):11>c?(i-=2+r(3),o=i,$=3<i):12>c&&(i+=2,o=i):t?F():f=1,console.log(c,o),t&&(t--,$=t)}

Ungolfed

let

print = (...x) => console.log(card, ...x),

// Uncomment for more human-friendly output:
// print = (...x) => console.log(`Fates Fool Jester Skull Donjon Void Talons Flames Rogue Moon Idiot Star Sun Throne Key Knight Ruin Euryale Vizier Comet Gem Balance`.split` `[card] + x.map(x => ` (${x})`).join``),

deck = [...Array(21)].map((_,i)=>i),
discard = {},

intelligence = 10,
wishUses = 0,
wishExpired = false,
fates = false,
turns = 0,

useFates = () => {
    fates = false
    turns = 0
    print('F')
},
useWish = () => {
    wishUses--
    turns = 0
    print(wishUses + (wishExpired ? ' C' : ''))
    wishExpired = random(2) < 1
},

random = n => Math.random() * n | 0,

canDraw = true

while(canDraw){
 // card = deck.splice(random(deck.length), 1)[0]
    while(discard[card = random(22)]);

    if(card){
        if(card < 3){
            // 1: Fool
            // 2: Jester
            if(turns){
                turns += card
            }
   print()
   discard[card] = 1
        }else if(card < 4){
            // 3: Skull
            if(fates){
                useFates()
            }else if(wishUses > 0 && !wishExpired){
                useWish()
            }else{
                print()
                canDraw = false
            }
        }else if(card < 7){
            // 4: Donjon
            // 5: Void
            // 6: Talons
            print()
            canDraw = false
        }else if(card < 9){
            // 7: Flames
            // 8: Rogue
            if(!turns){
                turns = 5
            }
            if(fates){
                useFates()
            }else if(wishUses > 0 && !wishExpired){
                useWish()
            }else{
                print()
            }
        }else if(card < 10){
            // 9: Moon
            wishUses += 1 + random(2)
            if(!turns){
                print(wishUses)
            }else{
                turns = 0
                wishUses--
                print(wishUses + 1, wishUses)
            }
        }else if(card < 11){
            // 10: Idiot
            intelligence -= 2 + random(3)
            print(intelligence)
            if(intelligence <= 3){
                canDraw = false
            }
        }else if(card < 12){
            // 11: Star
            intelligence += 2
            print(intelligence)
        }else{
            print()
        }
    }else{
        // 0: Fates
        if(!turns){
            fates = true
            print()
        }else{
            useFates()
        }
    }

    if(turns){
        turns--
        if(!turns){
            canDraw = false
        }
    }
}

Explanation of Output
Cards range from 0-21 as follows:

0: Fates
1: Fool
2: Jester
3: Skull
4: Donjon
5: Void
6: Talons
7: Flames
8: Rogue
9: Moon
10: Idiot
11: Star
12 though 21: Sun, Throne, Key, Knight, Ruin, Euryale, Vizier, Comet, Gem, Balance

A reversal of Skull, Flames, or Rogue via The Fates is denoted with a 0.

JavaScript (ES6), 792 bytes
Previous version using card names, before I found out that any 22 distinct outputs are allowed.

d=`Sun Moon Star Throne Key Knight Void Flames Skull Ruin Euryale Rogue Jester Vizier Comet Fates Gem Talons Idiot Donjon Balance Fool`.split` `,i=10,w=0,W=!1,f=!1,t=null,F=()=>{f=!1,t=null,_('F')},U=()=>{w--,t=null,_(w+(W?' C':'')),W=1>r(2)},_=(...a)=>console.log(c+a.map(b=>` (${b})`).join``),r=a=>0|Math.random()*a,$=!0;for(;$;)c=d.splice(r(d.length),1)[0],'Fates'==c?null==t?(f=!0,_()):F():'Moon'==c?(w+=1+r(2),null==t?_(w):(t=null,w--,_(w+1,w))):'Idiot'==c?(i-=2+r(3),_(i),3>=i&&($=!1)):'Star'==c?(i+=2,_(i)):'Flames'==c||'Rogue'==c?(null==t&&(t=5),f?F():0<w&&!W?U():_()):'Skull'==c?f?F():0<w&&!W?U():(_(),$=!1):'Donjon'==c||'Void'==c||'Talons'==c?(_(),$=!1):'Fool'==c?null!==t&&(t+=1):'Jester'==c?null!==t&&(t+=2):_(),['Fool','Jester'].includes(c)||d.push(c),null!==t&&t--,0===t&&($=!1)

Ungolfed

let

deck = `Sun Moon Star Throne Key Knight Void Flames Skull Ruin Euryale Rogue Jester Vizier Comet Fates Gem Talons Idiot Donjon Balance Fool`.split` `,

intelligence = 10,
wishUses = 0,
wishExpired = false,
fates = false,
turns = null,

useFates = () => {
    fates = false
    turns = null
    print('F')
},
useWish = () => {
    wishUses--
    turns = null
    print(wishUses + (wishExpired ? ' C' : ''))
    wishExpired = random(2) < 1
},

print = (...x) => console.log(card + x.map(x => ` (${x})`).join``),
random = n => Math.random() * n | 0,

canDraw = true

while(canDraw){
    card = deck.splice(random(deck.length), 1)[0]

    switch(card){
    case 'Fates':
        if(turns === null){
            fates = true
            print()
        }else{
            useFates()
        }
        break
    case 'Moon':
        wishUses += 1 + random(2)
        if(turns === null){
            print(wishUses)
        }else{
            turns = null
            wishUses--
            print(wishUses + 1, wishUses)
        }
        break
    case 'Idiot':
        intelligence -= 2 + random(3)
        print(intelligence)
        if(intelligence <= 3){
            canDraw = false
        }
        break
    case 'Star':
        intelligence += 2
        print(intelligence)
        break
   case 'Flames':
   case 'Rogue':
        // Changed Condition
        if(turns === null){
            turns = 5
        }

        if(fates){
            useFates()
        }else if(wishUses > 0 && !wishExpired){
            useWish()
        }else{
            // Added
            print()
        }
        break
    case 'Skull':
        if(fates){
            useFates()
        }else if(wishUses > 0 && !wishExpired){
            useWish()
        }else{
            print()
            canDraw = false
        }
        break
    case 'Donjon':
    case 'Void':
    case 'Talons':
        print()
        canDraw = false
        break
    case 'Fool':
        if(turns !== null){
            turns += 1
        }
        break
    case 'Jester':
        if(turns !== null){
            turns += 2
        }
        break
    default:
        print()
    }

    if(!['Fool', 'Jester'].includes(card)){
        deck.push(card)
    }

    if(turns !== null){
        turns--
    }

    if(turns === 0){
        canDraw = false
    }
}

@Mego honestly, I didn't really get it as well as I should've until seeing this answer, was well done; easy to understand when seeing the full names. If you change it can you keep a version with the full names?

@MagicOctopusUrn Certainly, I'll be sure to preserve the current full-name version in the future.

@Mego it was directed at OP, and was just saying "the version with the actual card names spelled fully made this implementation easy to read. If you shave bytes off, keep this one too, labeled as 'ungolfed'".

@MagicOctopusUrn Updated.

Java 10, 481 480 476 470 453 439 437 436 bytes
v->{var r="";Math M=null;int i=10,d=22,c,F=0,t=0,w=0,W=0,j=2;for(j*=M.random();;){c=d;c*=M.random();r+=" "+c;t=c<1?(r+=t<(F=1)?"":"F"+(F=0))==""?-1:-1:c<2?0*(w+=M.random()*3-(t>0?0:1)):c<4?F>0?-1:t<1?6:t:c<5?F*w*W>(F=0)?-1:1:c>19?t+(t>0*d--*j++?j%2+1:0):t;W=c>1&c<5&w*W>0?(int)(M.random()*3)%2+0*w--:W;i-=c==5?M.random()*3+2:c==6?-2:0;r+=c>1&c<5&F>0?"F"+(F=0):c>0&c<5?"w"+w+"W"+W:c>4&c<7?"i"+i:"";if(--t==0|c==5&i<4|c>6&c<10)return r;}}

Ported the Python3 reference implementation in Java, and then golfed it down.
-46 bytes thanks to @ceilingcat.
Card outputs:

0: Fates
1: Moon
2: Flames
3: Rogue
4: Skull
5: Idiot
6: Star
7/8/9: Donjon/Void/Talons
20/21: Fool/Jester
10-19: everything else (Sun/Throne/Key/Knight/Ruin/Euryale/Vizier/Comet/Gem/Balance)

Output format for wishes left, wishes used, intelligence left, and flag used:
4w1W0
4       // Card drawn
 w1     // New amount of wishes left
   W0   // Whether the wishes used flag is active (1) or inactive (0)

5i6
5       // Card drawn
 i6     // New intelligence

0F0
0       // Card drawn
 F0     // Fates used

Explanation:
Try it here or Try it here with pretty-printed output.
v->{                        // Method with empty unused parameter and String return-type
  var r="";                 //  Result-String, starting empty
  Math M=null;              //  Static Math to save bytes
  int i=10,                 //  Intelligence, starting at 10
      d=22,                 //  Amount of cards in the deck, starting at 22
      c,                    //  Current card drawn
      F=0,                  //  Fates flag, starting at inactive
      t=0,                  //  Turn-counter, starting at 0
      w=0,                  //  Wishes left, starting at 0
      W=0,                  //  Wishes used flag, starting at 0
      j=2;for(j*=M.random() //  Whether Jester/Fool is drawn first of the two, random 0/1
      ;;){                  //  Loop indefinitely:
    c=d;c*=M.random();      //   Draw a random 0-21 card (or less if Fool/Jester is gone)
    r+=" "+c;               //   Append the result with a space and this card
    t=c<1?                  //   If the card was Fates:
      (r+=t<(F=1)           //    Set the Fates-flag to active
                 ?          //    And if the turn-counter is 0:
        ""                  //     Append nothing
      :                     //    Else (the turn-counter is larger than 0):
       "F"+(F=0))           //     Append that Fates was used (and make Fates inactive)
      ==""?-1:-1            //    Then set the turn-counter to -1 (none)
    :c<2?                   //   If the card was Moon instead:
      0*(w+=M.random()*3    //    Increase the wishes by 0-2 randomly
         -(t>0?             //    Then, if the turn-counter is larger than 0
            0               //     Leave the (0-based random) wishes the same
           :                //    Else:
            1))             //     Subtract 1 from the (0-based random) wishes
      -1                    //    Set the turn-counter to -1 (none)
    :c<4?                   //   If the card was Flames or Rogue instead:
      F>0?                  //    If the Fates-flag is active:
       -1                   //     Set the turn-counter to -1 (none)
      :t<1?                 //    Else-if the turn-counter is 0 or -1 (none):
       6                    //     Set the turn-counter to 6
      :                     //    Else:
       t                    //     Leave the turn-counter the same
    :c<5?                   //   If the card was Skull instead:
        F                   //    If the Fates-flag is inactive
        *w                  //    or the amount of wishes is smaller than 1
        *W<1                //    or the wishes used flag is inactive
            +0*(F=0)?       //    (And set the Fates-flag to inactive)
         1                  //     Set the turn-counter to 1
        :                   //    Else:
         -1                 //     Set the turn-counter to -1 (none)
    :c>19?                  //   If the card was Fool or Jester instead:
      t+(t>0*d--            //    Remove the Fool/Jester from the Deck
            *j++            //    And increase `j` (Fool/Jester) by 1
                ?           //    If the turn-counter was not 0 or -1 (none):
          j%2+1             //     Increase either by 1 (Fool) or 2 (Jester)
         :                  //    Else:
          0)                //     Leave the turn-counter the same by increasing with 0
    :                       //   Else:
     t;                     //    Leave the turn-counter unchanged
    W=c>1&c<5               //   If the card drawn was Flames, Rogue or Skull,
      &w                    //   and the amount of wishes is at least 1,
        *W>0?               //   and the wishes used flag is active
       (int)(M.random()*3)%2//    Randomly set the wishes used flag to one of (0,0,1)
       +0*w--               //    And decrease the wishes left by 1
      :                     //   Else:
       W;                   //    Keep the wishes used flag the same
    i-=c==5?                //   If the card drawn was Idiot:
        M.random()*3+2      //    Decrease the intelligence by 2-5 randomly
       :c==6?               //   Else-if the card drawn was Star:
        -2                  //    Increase the intelligence by 2
       :                    //   Else:
        0;                  //    Leave the intelligence the same
    r+=c>1&c<5              //   If the card drawn was Flames, Rogue or Skull,
       &F>0?                //   and Fates is active
        "F"+(F=0)           //    Append that Fates was used (and make Fates inactive)
       :c>0&c<5?            //   Else-if the card drawn was Moon, Flames, Rogue or Skull:
        "w"+w+"W"+W         //    Append the amount of wishes left and wishes used flag
       :c>4&c<7?            //   Else-if the card drawn was Idiot or Star:
        "i"+i               //    Append the amount of intelligence left
       :                    //   Else:
        "";                 //    Append nothing
    if(--t                  //   Decrease the turn-counter by 1
          ==0               //   And if the turn-counter is now 0,
       |c==5                //   or the card drawn was Idiot,
             &i<4           //   and the intelligence dropped below 4,
       |c>6&c<10)           //   or the card drawn was Donjon, Void or Talons:
         return r;}}        //    Return the result of the game

Jester; Fates; Ruin; Euryale; Gem; Ruin; Ruin; Rogue(Fates used) Gem; Balance; Throne; Rogue(wishes left: 0; wishes used: 0); Rogue(wishes left: 0; wishes used: 0); Why did it stop?

@FrownyFrog Thanks! Should be fixed now. If you spot any other mistakes, let me know. :)

Kotlin, 1173 bytes
fun main(args:Array<String>){val d="Sun Moon Star Throne Key Knight Void Flames Skull Ruin Euryale Rogue Jester Vizier Comet Fates Gem Talons Idiot Donjon Balance Fool".split(" ");var c=(Math.random()*22).toInt();var i=10;var u=0;var e=false;var f=false;var t=1;r@while(true){when(c){15->{if(t>=1){f=true;println(c)}else{t = 1;f = false;println("${d[c]} (F)")}}1->{u+=(Math.random()*3).toInt()+1;if(t>=1){println("${d[c]} ($u)")}else{t=1;u-=1;println("${d[c]} (${u + 1}) ($u)")}}in arrayOf(7,11)->{if(t>=1){t=5};if(f){f=false;t=1;println("${d[c]} (F)")}else if(u>0&&!e){u-=1;t=1;val n=(Math.random()*3).toInt();println("${d[c]} ($u$e)");e=n==0}else{println(d[c])}}18->{i-=(Math.random()*4).toInt()+2;println("${d[c]} ($i)");if (t!=0){t+=1};if(i<=3){break@r}}2->{i+=2;println("${d[c]} ($i)")}8->{if(f){f=false;t=1;println("${d[c]} (F)")}else if(u>0&&!e){u-=1;t=1;val n=(Math.random()*3).toInt();println("${d[c]} ($u$e)");e=n==0}else{println(c);break@r}}in arrayOf(6,17,19)->{println(d[c]);break@r}21->{println(d[c]);if(t!=0){t += 1}}12->{println(d[c]);if(t!=0){t+=2}}else->{println(d[c])}};if((c !in arrayOf(12,21))){c=(Math.random()*23).toInt()};if(t!=0){t-=1}else{break}}}

It's runnable, too. - Try it online!
There's probably lots of bugs... let me know in the comments!

Infinite loop printing Fool or Jester.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Take one to make one
Challenge
Given a list of positive integers, find if there exists a permutation where taking up to one bit from each of the integers, a binary number consisting of all 1s can be created.
The number of bits in the resulting binary number is equal to the highest MSB in the list of integers.
Output
Your code must output or return a truthy/falsey value indicating if such a permutation exists.
Examples
Truthy:
With the list [4, 5, 2], and its binary representation [100, 101, 10], we can use the third, first, and second bits, respectively, to create 111:
4  ->  100  ->  100  ->  1
5  ->  101  ->  101  ->    1
2  ->  010  ->  010  ->   1
Result                   111

With the list [3, 3, 3], all of the numbers have both first and second bits set as 1, so we can take our pick with a number to spare:
3  ->  11  ->  11  ->  1
3  ->  11  ->  11  ->   1
3  ->  11  ->  11  ->
Result                 11

Falsey:
With the list [4, 6, 2], none of the numbers have the first bit set as 1, so the binary number cannot be created:
4  ->  100
6  ->  110
2  ->  010

With the list [1, 7, 1], only one of the numbers has the second and third bits set as 1, and the number cannot be created:
1  ->  001
7  ->  111
1  ->  001

Obviously, if the maximum number of set bits exceeds the number of integers, the result number can never be created.
Test cases
Truthy:
[1]
[1, 2]
[3, 3]
[3, 3, 3]
[4, 5, 2]
[1, 1, 1, 1]
[15, 15, 15, 15]
[52, 114, 61, 19, 73, 54, 83, 29]
[231, 92, 39, 210, 187, 101, 78, 39]

Falsey:
[2]
[2, 2]
[4, 6, 2]
[1, 7, 1]
[15, 15, 15]
[1, 15, 3, 1]
[13, 83, 86, 29, 8, 87, 26, 21]
[154, 19, 141, 28, 27, 6, 18, 137]

Rules
Standard loopholes are forbidden. As this is code-golf, shortest entry wins!

There's a theorem that might help with this…

Welcome to PPCG! Nice first challenge!

@Notatree: Well, how nice. I can use the shortest code to find me a wife.

Added to my index of graph problems as bipartite matching.

Jelly, 11 bytes
BUT€ŒpṬz0PẸ

Try it online!
How it works
BUT€ŒpṬz0PẸ  Main link. Argument: A (array)

             Example: A = [4, 5, 2]
B            Binary; convert each n in A to base 2.
                      [[1, 0, 0], [1, 0, 1], [1, 0]]
 U           Upend; reverse all arrays of binary digits.
                      [[0, 0, 1], [1, 0, 1], [0, 1]]
  T€         Truth each; for each binary array, get all indices of 1's.
                      [[3], [1, 3], [2]]
    Œp       Take the Cartesian product of all index arrays.
                      [[3, 1, 2], [3, 3, 2]
      Ṭ      Untruth; map each index array to a binary arrays with 1's at
             at the specified indices.
                      [[1, 1, 1], [0, 1, 1]]
       z0    Zip/transpose the resulting 2D array, filling shorter rows with 0's.
                      [[1, 0], [1, 1], [1, 1]]
         P   Take the columnwise product.
                      [1, 0]
          Ẹ  Any; yield 1 if any of the products is non-zero, 0 otherwise.
                      1

J, 30 bytes
All credit goes to my colleague Marshall.
Unnamed tacit prefix function.
[:+./ .*(1->./@${.|:)^:2@|:@#:

Try it online!
(@ is function composition)
#: antibase-2
|: transpose
(…)^:2 apply the following function twice:
 1- Boolean negate
 >./ the maximum
 @ of the
 $ axis lengths
 {. take (padding with zeros) from
 |: the transposed argument
+./ .* "crazy determinant magic"*
[: don't hook (no-op – serves to compose the previous part with the rest)

* In Marshall's words.

JavaScript (ES6), 104 ... 93 83 bytes
Returns 0 or 1.
f=(a,m=Math.max(...a),s=1)=>s>m|a.some((n,i)=>n&s&&f(b=[...a],m,s*2,b.splice(i,1)))

Test cases

f=(a,m=Math.max(...a),s=1)=>s>m|a.some((n,i)=>n&s&&f(b=[...a],m,s*2,b.splice(i,1)))

console.log('Truthy')
console.log(f([1]))
console.log(f([1, 2]))
console.log(f([3, 3]))
console.log(f([3, 3, 3]))
console.log(f([4, 5, 2]))
console.log(f([1, 1, 1, 1]))
console.log(f([15, 15, 15, 15]))
console.log(f([52, 114, 61, 19, 73, 54, 83, 29]))
console.log(f([231, 92, 39, 210, 187, 101, 78, 39]))

console.log('Falsy')
console.log(f([2]))
console.log(f([2, 2]))
console.log(f([4, 6, 2]))
console.log(f([1, 7, 1]))
console.log(f([15, 15, 15]))
console.log(f([1, 15, 3, 1]))
console.log(f([13, 83, 86, 29, 8, 87, 26, 21]))
console.log(f([154, 19, 141, 28, 27, 6, 18, 137]))

Method
Given the input array A = [a0, a1, ..., aN-1], we look for a permutation [ap[0], ap[1], ..., ap[N-1]] of A and an integer x ≤ N such that:

s = 1 + (ap[0] AND 20) + (ap[1] AND 21) + ... + (ap[x-1] AND 2x-1) = 2x
and s is greater than the greatest element m of A

Formatted and commented
f = (                 // f = recursive function taking:
  a,                  //   - a = array
  m = Math.max(...a), //   - m = greatest element in a
  s = 1               //   - s = current power of 2, starting at 1
) =>                  //
  s > m               // success condition (see above) which is
  |                   // OR'd with the result of this some():
  a.some((n, i) =>    // for each element n at position i in a:
    n & s &&          //   provided that the expected bit is set in n,
    f(                //   do a recursive call with:
      b = [...a],     //     b = copy of a
      m,              //     m unchanged
      s * 2,          //     s = next power of 2
      b.splice(i, 1)  //     the current element removed from b
    )                 //   end of recursive call
  )                   // end of some()

05AB1E, 23 22 20 bytes
-1 byte thanks to Mr.Xcoder
True: 1, False: 0
2вí0ζœεvyƶNè})DgLQ}Z

Try it online!
Explanations:
2вí0ζœεvyƶNè})DgLQ}Z   Full program (implicit input, e.g. [4, 6, 2])
2в                     Convert each to binary ([1,0,0], [1,1,0], [1,0])
  í                    Reverse each ([0,0,1], [0,1,1], [0,1])
   0ζ                  Zip with 0 as a filler ([0,0,0],[0,1,1],[1,1,0])
     œ                 Get all sublists permutations
      ε           }    Apply on each permutation...
       vyƶNè}            For each sublist...
        yƶ                  Multiply each element by its index
          Nè                Get the element at position == sublist index
             )           Wrap the result in a list
              DgLQ       1 if equal to [1,2,...,length of item]
                   Z   Get max item of the list (1 if at least 1 permutations fill the conditions)
                       -- implicit output

Husk, 14 bytes
SöV≡ŀToṁ∂Pmo↔ḋ

Try it online!
Explanation
SöV≡ŀToṁ∂Pmo↔ḋ  Implicit input, say [4,5,2].
          m  ḋ  Convert each to binary
           o↔   and reverse them: x = [[0,0,1],[1,0,1],[0,1]]
         P      Take all permutations of x
      oṁ∂       and enumerate their anti-diagonals in y = [[0],[0,1],[1,0,0],[1,1],[1]..
S    T          Transpose x: [[0,1,0],[0,0,1],[1,1]]
    ŀ           Take the range up to its length: z = [1,2,3]
                Then z is as long as the longest list in x.
 öV             Return the 1-based index of the first element of y
   ≡            that has the same length and same distribution of truthy values as z,
                i.e. is [1,1,1]. If one doesn't exist, return 0.

PHP, 255 243 160 bytes
-12 bytes, took out the sorting
-83 bytes (!) thanks to Titus
<?function f($a,$v=NULL,$b=[]){($v=$v??(1<<log(max($a),2)+1)-1)||die("1");if($p=array_pop($a))while($p-=$i)($b[$i=1<<log($p,2)]|$v<$i)||f($a,$v-$i,[$i=>1]+$b);}

Try it online!
Prints 1 for truthy, nothing for falsey.
Original version ungolfed:
<?php
unset($argv[0]);                                                   // remove filename from arguments
$max = pow(2,floor(log(max($argv),2))+1)-1;                        // get target number (all bits set to 1)
solve($argv,$max,[]);
function solve($array,$value,$bits){
  if(!$value){                                                     // if we've reached our target number (actually subtracted it to zero)
    die("1");                                                      // print truthy
  }
  if(count($array)){                                               // while there are arguments left to check
    $popped = array_pop($array);                                   // get the largest argument
    while($popped > 0 && ($mybit = pow(2,floor(log($popped,2))))){ // while the argument hasn't reached zero, get the highest power of 2 possible
      $popped -= $mybit;                                           // subtract power from argument
      if($value >= $mybit && !$bits[$i]){                          // if this bit can be subtracted from our argument, and we haven't used this bit yet
        $copy = $bits;                                             // create a copy to pass to the function
        $copy[$mybit] = 1;                                         // mark the bit as used in the copy
        solve($array,$value-$mybit,$copy);                         // recurse
      }
    }
  }
}

I haven´t tested it, but theses 158 bytes should do the same: function f($a,$v=NULL,$b=[]){($v=$v??(1<<log(max($a),2)+1)-1)||die("1");if($p=array_pop($a))while($p-=$i)($b[$i=1<<log($p,2)]|$v<$i)||f($a,$v-$i,[$i=>1]+$b);}

@Titus and thus we see how terrible I am at codegolf. And why most questions have a great answer by you in PHP. (and a few other languages).

Terrible for now. That´s a pretty good answer; and golfing skills come with experience.

No need for the lengthy string notation, just use something else that translates to “1” but is not integer. For example a boolean true: die("1") → die(!0).

Wolfram Language (Mathematica), 65 bytes
Max[Tr/@Permutations[n=PadLeft[#~IntegerDigits~2]]]==Tr[1^#&@@n]&

Try it online!
Explanation
#~IntegerDigits~2

We start by converting all inputs to binary lists.
n=PadLeft[...]

Then we pad all those lists with zeros to the left to make the array rectangular. The result is stored in n for later.
Permutations[...]

Yay, brute force, let's get all possible permutations of the input.
Tr/@...

This gets the trace for each permutation, i.e. the sum of the diagonal elements in the permutation. In other words, we add up the MSB from the first number, the next-to-MSB from the second number and so on. If the permutation is valid, all of these will be 1 and there will be as many 1s as the largest input number is wide.
Max[...]

We get the maximum trace, because the trace can never be more than that of a valid permutation.
...==Tr[1^#&@@n]

The right-hand side is just a golfy version of Length @ First @ n, i.e. it gets the width of the rectangular array, and therefore the width of the largest input number. We want to make sure that the trace of some permutation is equal to this.

Lua 5.2, 85 bytes
m=math
x=function(...)print(bit32.bor(...)==2^(m.floor(m.log(m.max(...),2))+1)-1)end

This sets x to be a function that accepts a variable number of inputs (expected to be 32 bit integers), and prints to stdout either "true" or "false".
Usage:
x(13, 83, 86, 29, 8, 87, 26, 21) -- Prints "false"

Hmm, this seems to fail for some of the false test cases? [1,15,3,1] seems to return true instead of false for example. Here is your code the online compiler of TIO. The other two test cases that fail are [1,7,1] and [15,15,15]. All the other test cases output the correct results.

PHP, 121 bytes
function f($a,$s=0){($v=array_pop($a))||(0|$g=log($s+1,2))-$g||die("1");for($b=.5;$v<=$b*=2;)$v&$b&&~$s&$b&&f($a,$s|$b);}

Try it online.
breakdown
function f($a,$s=0)
{
    ($v=array_pop($a))          # pop element from array
    ||                          # if nothing could be popped (empty array)
    (0|$g=log($s+1,2))-$g       # and $s+1 is a power of 2
        ||die("1");                 # then print "1" and exit
    for($b=.5;$v>=$b*=2;)       # loop through the bits:
        $v&$b                       # if bit is set in $v
        &&~$s&$b                    # and not set in $s
            &&f($a,$s|$b);              # then set bit in $s and recurse
}

J, 49 bytes
g=.3 :'*+/*/"1+/"2((#y){.=i.{:$#:y)*"2#:(i.!#y)A.,y'

Do I need to count also the 'g=.'? I'm ready to add it.
A long explicit verb this time. I tried a tacit one for the same algorithm, but it turned out to be even longer and uglier than this. Far away from Adám's solution.
Explanation:
(y is the right argument of the function)
                                             ,y - adds a leading axis to the argument
                                             (if it's scalar becomes an array of length 1)
                                          .A    - finds the permutations according to the left argument
                                   (i.!#y)      - factorial of the length of the argument, for all permutations
                                 #:             - convert each element to binary
                             *"2                - multiply each cell by identity matrix
           (                )                   - group
                   =i.{:$#:y                    - identity matrix with size the length
                                                  of the binary representation of the argument
             (#y){.                             - takes as many rows from the identity matrix
                                                  as the size of the list (pad with 0 if neded)
    */"1+/"2                                    - sums the rows and multiplies the items
                                                  to check if forms an identity matrix
 *+/                                            - add the results from all permutations and
                                                  returns 1 in equal or greater then 1

Try it online!

R, 247 bytes 221 bytes
function(i){a=do.call(rbind,Map(`==`,Map(intToBits,i),1));n=max(unlist(apply(a,1,which)));any(unlist(g(a[,1:n,drop=F],n)))}
g=function(a,p){if(p==1)return(any(a[,1]));Map(function(x){g(a[x,,drop=F],p-1)},which(a[,p])*-1)}

Try it online!
Ungolfed version
f=function(i){                                   #anonymous function when golfed
  a=do.call(rbind,Map(`==`,Map(intToBits,i),1))  #convert integers to binary, then logical
                                                 #bind results together in matrix
  n=max(unlist(apply(a,1,which)))                #determine max number of bits
  any(unlist(g(a[,1:n,drop=F],n)))               #apply recursive function
}

g=function(a,p){
  if(p==1)return(any(a[,1]))                   #check if first bit is available still
  Map(function(x){g(a[x,,drop=F],p-1)},which(a[,p])*-1) #strip row used for current bit
                                                        #and apply the function recursively
}

I realized the no-row check was unnecessary with the drop=F arguments. Also removed some pesky whitespace.

PHP, 152 bytes
<?function b($a,$b,$s){$a[$s]=0;$r=$b-1;foreach($a as$i=>$v)if($v&1<<$b)$r=max(b($a,$b+1,$i),$r);return$r;}$g=$argv;$g[0]=0;echo!(max($g)>>b($g,0,0)+1);

Prints nothing for false, 1 for true.
Ungolfed:
<?

// Search an array for a value having a bit set at the given bit index.
// For each match, search for a next higher bit index excluding the current match.
// This way it "climbs up" bit by a bit, finally returning the highest bit index reached.
function bitSearch($valArr, $bitInd, $skipInd) {
    unset($valArr[$skipInd]);
    $result = $bitInd - 1;
    foreach ($valArr as $ind => $v) {
        if ($v & (1 << $bitInd)) {
            $result = max(bitSearch($valArr, $bitInd + 1, $ind), $result);
        }
    }
    return $result;
}

$argv[0] = 0;
$r = bitSearch($argv, 0, 0);
// Check if the highest bit index reached was highest in the largest value given.
if (max($argv) >> ($r + 1)) {
    echo("False\n");
} else {
    echo("True\n");
}

Python 3, 126 120 bytes
Saved 6 bytes due to Mr. Xcoder
lambda x:g(x,max(map(len,map(bin,x)))-3)
g=lambda x,n:n<0 or any(g(x[:i]+x[i+1:],n-1)for i in range(len(x))if x[i]&2**n)

Try it online!

Could you add an ungolfed version?

[0]+[...] Is pointless isn't it? any(g(x[:i]+x[i+1:],n-1)for i in range(len(x))if x[i]&2**n) should suffice.

@Mr.Xcoder Yeah, I guess I was thinking about the max function when I added it

Jelly, 17 bytes
BUz0×J$€ŒpṢ=JPƲ€Ẹ

Test suite.

Jelly, 17 bytes
BUz0Œ!ŒD€Ẏ
ṀBo1eÇ

A monadic link taking a list of numbers and returning 1 (truthy) or 0 (falsey).
Try it online!
This will time out on TIO for the longest of each of the test cases.
How?
BUz0Œ!ŒD€Ẏ - Link 1, possibilities (plus some shorter ones & duplicates): list of numbers
                                     e.g. [4, 5, 2]
B          - to binary list (vectorises)  [[1,0,0],[1,0,1],[1,0]]
 U         - upend                        [[0,0,1],[1,0,1],[0,1]]
   0       - literal zero                  0
  z        - transpose with filler        [[0,1,0],[0,0,1],[1,1,0]]
    Œ!     - all permutations             [[[0,1,0],[0,0,1],[1,1,0]],[[0,1,0],[1,1,0],[0,0,1]],[[0,0,1],[0,1,0],[1,1,0]],[[0,0,1],[1,1,0],[0,1,0]],[[1,1,0],[0,1,0],[0,0,1]],[[1,1,0],[0,0,1],[0,1,0]]]
      ŒD€  - diagonals of €ach            [[[0,0,0],[1,1],[0],[1],[0,1]],[[0,1,1],[1,0],[0],[0],[1,0]],[[0,1,0],[0,0],[1],[1],[0,1]],[[0,1,0],[0,0],[1],[0],[1,1]],[[1,1,1],[1,0],[0],[0],[0,0]],[[1,0,0],[1,1],[0],[0],[0,1]]]
         Ẏ - tighten                      [[0,0,0],[1,1],[0],[1],[0,1],[0,1,1],[1,0],[0],[0],[1,0],[0,1,0],[0,0],[1],[1],[0,1],[0,1,0],[0,0],[1],[0],[1,1],[1,1,1],[1,0],[0],[0],[0,0],[1,0,0],[1,1],[0],[0],[0,1]]

ṀBo1eÇ - Main link: list of numbers  e.g. [4, 5, 2]
Ṁ      - maximum                           5
 B     - to binary list                   [1,0,1]
   1   - literal one                       1
  o    - or (vectorises)                  [1,1,1]
     Ç - last link as a monad             [[0,0,0],[1,1],[0],[1],[0,1],[0,1,1],[1,0],[0],[0],[1,0],[0,1,0],[0,0],[1],[1],[0,1],[0,1,0],[0,0],[1],[0],[1,1],[1,1,1],[1,0],[0],[0],[0,0],[1,0,0],[1,1],[0],[0],[0,1]]
    e  - exists in?                        1    --------------------------------------------------------------------------------------------------------------^

C , 79 bytes
b,i;main(a){for(;~scanf("%d",&a);i++)b|=a;puts("false\0true"+(b==(1<<i)-1)*6);}

Could you add an explanation? Also, a try it online link would be useful.

Some tips when golfing in C: 1/ in many challenges (this one included), you're allowed to submit a function instead of a full program, 2/ you have to output a truthy/falsey value, this can be anything as long as it's consistent (you can output 0 / 1 instead of "false"/"true"). Lastly, this code doesn't seem to work: [1, 7, 1] should return false, and [52, 114, 61, 19, 73, 54, 83, 29] should return true

You're right, my bad