16
\$\begingroup\$

Thanks to rak1507 for the suggestion

"Random" in this challenge always refers to "uniformly random" - of all possible choices, each has an equal chance of being chosen. Uniform shuffling means that every possible permutation of the array has an equal chance of being chosen.

Given an array consisting of positive digits (123456789), select a randomly chosen, non-empty subsequence from the array, shuffle the elements and reinsert them back into the array in the former indices, outputting the result

For example, take L = [5, 1, 2, 7, 4]. We choose a random non-empty subsequence, e.g. [5, 2, 4]. These are at indices 1, 3, 5 (1-indexed). Next, we shuffle [5, 2, 4] to give e.g. [2, 5, 4]. We now reinsert these into the list, with 2 at index 1, 5 at index 3 and 4 at index 5 to give [2, 1, 5, 7, 4].

You may also take the input as an integer or a string, and output it as such, or you may mix and match types.

This is , so the shortest code in bytes wins

\$\endgroup\$
16
  • 5
    \$\begingroup\$ subsequence implies contiguous, you might want to specify that it's all subsets \$\endgroup\$
    – emanresu A
    Dec 29, 2021 at 0:55
  • 2
    \$\begingroup\$ @U12-Forward No, the subsequence can be of any length between 1 and the length of the input. "a random non-empty subsequence" refers to choosing from all non-empty subsequences of the input \$\endgroup\$ Dec 29, 2021 at 0:59
  • 2
    \$\begingroup\$ I think you need to specify more exactly what "elect a randomly chosen, non-empty subsequence from the array" means, because there are multiple reasonable ways to do this with different distributions. Does it have to be equivalent to computing the input's powerset (without the empty list) and choosing one of those sets randomly? \$\endgroup\$
    – pxeger
    Dec 29, 2021 at 2:24
  • 1
    \$\begingroup\$ @emanresuA I believe that you are thinking of "substring", see this math post. \$\endgroup\$ Dec 29, 2021 at 3:20
  • 4
    \$\begingroup\$ To my understanding, output for [1, 2, 3] should be \$\frac{2}{3}\$ [1, 2, 3]; \$\frac{2}{21}\$ [2, 1, 3]; \$\frac{2}{21}\$ [1, 3, 2]; \$\frac{2}{21}\$ [3, 2, 1]; \$\frac{1}{42}\$ [3, 1, 2]; \$\frac{1}{42}\$ [2, 3, 1]. If I was calculated correctly... I would suggest answers show destribution of input [1, 2, 3] and confirm it meats the requirement of distribution. \$\endgroup\$
    – tsh
    Dec 29, 2021 at 5:24

17 Answers 17

6
\$\begingroup\$

Jelly, 11 bytes

JŒPḊX,Ẋ$yJị

Try It Online!

JŒPḊX,Ẋ$yJị  Main Link
J            Get the list of indices [1, 2, ..., n]
 ŒP          Powerset - all possible subsets
   Ḋ         Remove the empty one
    X        Select a random one
     ,Ẋ$     Pair that with a random permutation of itself
        yJ   Translate the original indices according to that mapping
          ị  Index back into the original list
\$\endgroup\$
5
\$\begingroup\$

J, 37 40 39 35 bytes

({~#?#)@:{~`]`[}1 I.@#:@+0{1?_1+2^#

Try it online!

+3 after reading hyperneutrino's answer and realizing I had to remove the empty subset

-4 after reading loopy walt's answer and realizing I could make my random choice before converting to binary

Consider 5 1 2 7:

  • 1 ...+0{1?_1+2^# If n is input length, picks a random number between 1 and 2^n.

  • I.@#:@ converts it to binary, and then converts that mask to indices. That is, the first 2 steps amount to choosing a random element from the 2nd column:

    ┌───────┬───────┐
    │0 0 0 1│3      │
    │0 0 1 0│2      │
    │0 0 1 1│2 3    │
    │0 1 0 0│1      │
    │0 1 0 1│1 3    │
    │0 1 1 0│1 2    │
    │0 1 1 1│1 2 3  │
    │1 0 0 0│0      |
    │1 0 0 1│0 3    │
    │1 0 1 0│0 2    │
    │1 0 1 1│0 2 3  │
    │1 1 0 0│0 1    │
    │1 1 0 1│0 1 3  │
    │1 1 1 0│0 1 2  │
    │1 1 1 1│0 1 2 3│
    └───────┴───────┘
    
  • ({~#?#)@:{~`]`[} Now "amend" the original input at those indices with the current values at those indices, shuffled.

\$\endgroup\$
4
\$\begingroup\$

Perl 5 List::Util, 47 bytes

sub{@_[@s]=@_[shuffle@s=grep.5<rand,0..$#_];@_}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

R, 82 79 77 bytes

Or R>=4.1, 70 bytes by replacing the word function with a \.

Edit: fix for 1-length input thanks to @Dominic van Essen.

function(v,k=seq(!v),`[`=sample)`[<-`(v,m<-k[k[1,,choose(max(k),k)]],sort(m))

Try it online!

Different approach to Dominic's R answer (test harness stolen from him).

Samples length of the subsequence to shuffle from a distribution given by a truncated row of Pascal's triangle. Then samples this many indices in random order and substitutes the corresponding values for the sorted counterparts.

function(v,             # function taking v as input
k=seq(!v),              # sequence along v (1:length(v))
s=sample){              # rename for golfing purposes
n<-                     # how long the subsequence
 s(k,1,                 # sample from k one number
 prob=choose(max(k),k)) # distribution given by row of Pascal's triangle
                        # without the first 1 (corresponding to empty subsequence)
m<-s(k,n)               # sample n items from k 
v[m]=                   # in v: at indices given by m
 v[sort(m)]             # place values from indices at sorted m
v}                      # return v
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Really nice! I love it. But you may need to add a ! in the seq to cope with input with length 1... \$\endgroup\$ Dec 29, 2021 at 21:13
  • \$\begingroup\$ Isn't R's sample biased in some way? I know it was fixed but that version may not be on TIO... @dominicvanessen \$\endgroup\$
    – Giuseppe
    Dec 29, 2021 at 21:47
  • \$\begingroup\$ @Giuseppe - I don't know, but isn't this checked when we calculate the sampling distribution (as pajonk & I have both done)? We seem to get tsh's expected distribution, so I'm assuming it's Ok... \$\endgroup\$ Dec 29, 2021 at 21:58
  • \$\begingroup\$ @DominicvanEssen thanks, I tested it at some point but apparently it was just luck then (as with challenges involving randomness may happen). Fortunately, a balancing golf has been found. \$\endgroup\$
    – pajonk
    Dec 30, 2021 at 7:21
  • \$\begingroup\$ @Giuseppe despite the test mentioned by Dominic, I think that we may assume for the purposes of the challenges that PRGs are actually random. \$\endgroup\$
    – pajonk
    Dec 30, 2021 at 7:24
3
\$\begingroup\$

Vyxal, 13 bytes

ẏÞS℅~İṖ℅Z(n÷Ȧ

Try it Online!

Explained

ẏÞS℅~İṖ℅Z(n÷Ȧ
ẏ             # Push the input and the range [0, len(input))
 ÞS℅          # Choose a random sublist of indices
    ~İ        # And index into the input at those places, without popping anything
      Ṗ℅      # Choose a random permutation of the indexed items
        Z     # and zip that with the chosen indices - this creates a list of [[original index, new item]...]
         (    # for each pair:
          n÷Ȧ # input[original index] = new item
\$\endgroup\$
2
  • \$\begingroup\$ Why the : ??? \$\endgroup\$
    – emanresu A
    Dec 29, 2021 at 1:05
  • \$\begingroup\$ @emanresuA because I wasn't sure if it worked without it \$\endgroup\$
    – lyxal
    Dec 29, 2021 at 1:05
3
\$\begingroup\$

Wolfram Language (Mathematica), 72 bytes

SubsetMap[c@*Permutations,#,c@Rest@Subsets[i=0;++i&/@#]]&
c=RandomChoice

Try it online!

SubsetMap[               ,#,                           ]    replace at indices:
                                   Subsets[i=0;++i&/@#]      of subsequences
                            c@Rest@                           (random nonempty)
          c@*Permutations                                   with a random permutation       
\$\endgroup\$
3
\$\begingroup\$

Python, 140 bytes

from random import*
def f(a):
 n=len(a);s=randint(1,2**n-1);t=[j for j in range(n)if s&2**j]
 while t:u=choice(t);T,*t=t;a[T],a[u]=a[u],a[T]

Attempt This Online!

Changes the input list in-place (no return value). It first draws a random integer from [1,2^n-1]) where n is the length of input list a. Its binary representation is used as a mask to uniformly select from the allowed subsets (all but the empty one). This subset is then randomly shuffled by applying a series of swaps. The swap is always the lowest active with a randomly chosen active position. I say "active" because after the swap the low element is retired from the active set and no longer eligible for swaps. It is left as an easy exercise for the reader to verify that this draws uniformly from all permutations of the subset.

The test code makes the histogram suggested by @tsh (more or less; I lump together permutations with the same structure) in a comment and the distribution looks ok.

\$\endgroup\$
0
3
\$\begingroup\$

Charcoal, 36 35 bytes

≔⌕A⮌⍘⊕‽⊖X²Lθ²1ηFLθ⊞υ⎇№ηι‽⁻ηυιIEυ§θι

Try it online! Link is to verbose version of code. Explanation:

≔⌕A⮌⍘⊕‽⊖X²Lθ²1η

Choose a random number from 1 to 2 to the power of the length of the input (exclusive). Convert it to base 2, and get the exponents of the powers of 2 that sum to that number.

FLθ⊞υ⎇№ηι‽⁻ηυι

Create a random permutation of those exponents, while keeping the unused exponents in their original position.

IEυ§θι

Apply that permutation to the original input.

\$\endgroup\$
3
\$\begingroup\$

R, 91 85 84 82 bytes

Edit: -1 byte thanks to pajonk, then -2 bytes thanks to Giuseppe

function(v,l=sum(v|T),`?`=sample,m=(l:0)[!(2:2^l-2?1)%/%2^(0:l)%%2]){v[m]=v[?m];v}

Try it online!

TIO link includes (reciprocal) distribution of shuffle_subsequence(1:3) to check conformity to tsh's calculations.

\$\endgroup\$
3
  • \$\begingroup\$ Rename sample to ? (or +) for -1 byte. \$\endgroup\$
    – pajonk
    Dec 29, 2021 at 15:16
  • \$\begingroup\$ 82 bytes \$\endgroup\$
    – Giuseppe
    Dec 29, 2021 at 17:57
  • \$\begingroup\$ @Giuseppe - thanks: don't know why I didn't see that... it seems so obvious (after you point it out, of course... doh)... \$\endgroup\$ Dec 29, 2021 at 19:51
3
\$\begingroup\$

BQN, 60 53 bytes

Edit: -7 bytes thanks to mlochbaum, and also thanks to ovs and mlochbaum for bug-spotting

•rand.Deal{(𝔽∘≠⊸⊏⌾(((2⋆⊒˜𝕩)(2|·⌊÷)˜1+⊑𝔽1-˜2⋆≠𝕩)⊸/)𝕩)}

Try it at BQN online REPL

Ungolfed, commented (try it here):

Deal ← •rand.Deal    # random permutation of 0..𝕩-1
Rand ← ⊑Deal         # random number from 0..𝕩-1
Shuf ← ⊢⊏˜·Deal≠     # random shuffle of list 𝕩
num ← 1+Rand 1-˜2⋆≠ vec        # pick a random number from 1..2^len(vec)-1
bits ← {(2⋆⊒˜vec)(2|·⌊÷)˜𝕩}num # convert it into bits
ans ← (Shuf⌾(bits⊸/)vec)       # shuffle vec at positions given by bits
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The 2-˜ should be 1-˜ instead to allow the full sequence (all 1's) as a subsequence. See the difference for 0‿1 here \$\endgroup\$
    – ovs
    Dec 29, 2021 at 22:33
  • \$\begingroup\$ @ovs - Ah, yes, thanks! Zero-based indexing always catches me out... \$\endgroup\$ Dec 29, 2021 at 22:46
2
\$\begingroup\$

APL+WIN, 31 bytes

Prompts for vector of digits. Will also work with a string of characters.

v[i]←v[i[(⍴i)?⍴i←(?⍴v)?⍴v←⎕]]⋄v

Index origin = 1. Randomly selects the length of the subset from 1 to length. Randomly selects indices corresponding to the length of subset. Randomly shuffles values at those indices.

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is not using a uniform distribution over all subsequences, as there are not equally many subsequences of each given length. For example for the input 1 2, your code will select the subsequence 1 2 with probability \$1 \over 2\$ and the two subsequences 1 and 2 with probability \$1 \over 4\$ each. \$\endgroup\$
    – ovs
    Dec 29, 2021 at 22:40
2
\$\begingroup\$

APL (Dyalog Unicode), 36 29 27 bytes

Requires index origin 0.

{⍵[?⍨≢⍵]}@{k∘←?{2}¨⍵}⍣{∨/k}

Try it online!

If we would allow the empty subsequence as a random choice, k∘← and ⍣{∨/k} could be removed.

How?

{k∘←?{2}¨⍵} Get a random subsequence and store it's binary mask in k
{2}¨⍵ A 2 for each value in . This could be 2⍨¨⍵ in version 18 and above.
? For each, draw a random integer in [0, 2) / 0 or 1.
k∘← Store that vector in a global variable named k and return it.

{⍵[?⍨≢⍵]}@ Shuffle the selected that subsequence
{ ... }@ Replace the subsequence indicated by 1's in the boolean mask with the return value of the function on the left.
≢⍵ n = Length of the subsequence
?⍨ Choose n random integers in the interval [0, n) (Permutation of [0,1,2,...,n-1]).
⍵[ ... ] Index into the subsequence with the permutation.

⍣{∨/k} ... until k contains at least a single 1.

\$\endgroup\$
1
\$\begingroup\$

BQN, 19 bytes

{𝕩⊏˜•rand.Deal≠𝕩}⍟≢

Explanation:-

{𝕩⊏˜•rand.Deal≠𝕩} shuffles array randomly

⍟≢ shuffles it again if (by chance) the shuffled array is equal to the original array

\$\endgroup\$
1
  • 5
    \$\begingroup\$ The original array should be a possible output, surely? Otherwise the permutatino of 'original order' for the shuffled elements didn't hava an equal chance of being chosen,,. \$\endgroup\$ Dec 29, 2021 at 9:42
1
\$\begingroup\$

JavaScript (ES6), 170 bytes

x=>(s=n=>n?(w=(x,i,k)=>[x[i],x[k]]=[x[k],x[i]])(y,--n,o()*n|0)&&s(n):y)((r=_=>(y=[...x.keys()].filter(_=>(o=Math.random)()<.5))+y?y:r())().length).map((k,i)=>w(x,i,k))&&x
\$\endgroup\$
1
\$\begingroup\$

Python3, 142 bytes:

from random import*
r=range
def f(s):g=sample(r(l:=len(s)),randint(1,l));j=g[:];shuffle(j);return[s[j.pop(0)]if i in g else s[i]for i in r(l)]

Try it online!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ The subsequence selected is not uniform across the domain of subsequences (for example given a list of length 10 you will choose the full length 10 sequence one time in ten but it should be chosen one time in 1023). \$\endgroup\$ Dec 29, 2021 at 17:22
1
\$\begingroup\$

C++ (gcc), 197 \$\cdots\$ 175 174 bytes

#import<regex>
using V=std::vector<int>;int f(V&v){V i=v,r=v;int y=0,n,j;for(int&a:i)a=y++;std::random_shuffle(&i[0],&*end(i));for(j=n=rand()%y+1;j;)r[i[--j]]=v[i[j%n]];v=r;}

Try it online!

Added 2 bytes to fix an error.
Saved 3 5 bytes thanks to ceilingcat!!!

Inputs a vector of integers.
Randomly shuffles a random subgroup of the elements in place.

\$\endgroup\$
0
0
\$\begingroup\$

Japt, 2 bytes

Simply shuffles the array randomly and has the possibility to output the original array, which would seem to satisfy the requirements to me.

ö¬

Try it

But, if not, then ...

Japt, 15 bytes

... This version interleaves the array with a random permutation of itself, chooses an element at random from each pair, and continues to do so until the result equals the input when both are sorted.

@ÍeXÍ}a@íUö¬ mö

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.