Shuffle a subsequence

Question

_{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 code-golf, so the shortest code in bytes wins

Answer 1

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

Answer 2

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.

Answer 3

Perl 5 List::Util, 47 bytes

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

Try it online!

Answer 4

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

Answer 5

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

Answer 6

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       

Answer 7

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.

Answer 8

Charcoal, 36 35 bytes

≔⌕Ａ⮌⍘⊕‽⊖Ｘ²Ｌθ²1ηＦＬθ⊞υ⎇№ηι‽⁻ηυιＩＥυ§θι

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

≔⌕Ａ⮌⍘⊕‽⊖Ｘ²Ｌθ²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.

ＦＬθ⊞υ⎇№ηι‽⁻ηυι

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

ＩＥυ§θι

Apply that permutation to the original input.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

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!

Answer 16

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.

Answer 17

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