Shuffle a ragged array

Question

A ragged array is an array where each element is an array of unknown number of positive integers.

For example, the following are ragged arrays:

[[1,2,3],[4],[9,10]]               Shape:  3,1,2
[[1],[2],[3]]                      Shape:  1,1,1
[[1,2,3,4,5,6,8]]                  Shape:  7

The following are not ragged arrays:

[1]   Each element will be an array
[]    The array will contain at least 1 element
[[1,2,3],[]]  Each subarray will contain at least 1 integer

You need to input a ragged array, and return a ragged array with the integers shuffled

• The output array must have the same shape as the input array. We define the shape of the array as the length of each subarray.
• Each integer must have an equally likely chance to appear in each possible location.
• You can assume that your language's built-in random is random.

For example, if I passed in: [[4],[1,2,3],[4]], then [[1],[4,4,2],[3]] would be a valid output, but [[4,1,3],[3],[4]] or [[4],[4],[1,2,3]] would not.

Answer 1

Jelly, 3 bytes in Jelly's codepage

FẊṁ

Explanation:

FẊṁ
F    flatten list
 Ẋ   shuffle the output from the previous line
  ṁ  unflatten the list, shaping it like…

Because the program is incomplete (ṁ doesn't have a second argument stated), the default is to use the program input; thus ṁ causes the output to have the same sublist pattern as the input.

Try it online!

Answer 2

PowerShell v2+, 86 bytes

param($n)$a=$n-split'[^\d]'-ne''|sort{random};-join($n-split'\d+'-ne''|%{$_+$a[$i++]})

Works via string manipulation. Input is passed in as a string representing the array, in whatever format works for your language. ;-)

-splits out the input on non-digits, sorts them based on the random script block (which will assign a different random weight for each input to the sort), stores that into $a. We then split the input again, this time on digits, and for each one output the current value (usually brackets and commas) string-concatenated with the corresponding number from $a. That's -joined together back into a string, and output is implicit.

Examples

PS C:\Tools\Scripts\golfing> .\shuffle-a-ragged-array.ps1 "@(@(1,2,3),4)"
@(@(3,2,1),4)

PS C:\Tools\Scripts\golfing> .\shuffle-a-ragged-array.ps1 "@(@(1,2,3),4)"
@(@(1,2,4),3)

PS C:\Tools\Scripts\golfing> .\shuffle-a-ragged-array.ps1 "[[4],[1,2,3],[4]]"
[[4],[2,4,3],[1]]

PS C:\Tools\Scripts\golfing> .\shuffle-a-ragged-array.ps1 "[[10],[1,2,3],[5]]"
[[10],[5,2,1],[3]]

PS C:\Tools\Scripts\golfing> .\shuffle-a-ragged-array.ps1 "[[10],[1,2,3],[5]]"
[[5],[10,2,1],[3]]

Answer 3

Python 2, 89 bytes

from random import*
x=input();r=sum(x,[]);shuffle(r)
print[[r.pop()for _ in t]for t in x]

Try it online!

Answer 4

JavaScript (ES6), 78 75 bytes

x=>x.map(y=>y.map(z=>+s.splice(Math.random()*s.length,1)),s=eval(`[${x}]`))

This is the first time I can remember using .splice() in a code-golf challenge...

You can golf off two bytes by shuffling the array beforehand:

x=>x.map(y=>y.map(z=>s.pop()),s=eval(`[${x}]`).sort(_=>Math.random()-.5))

However, this seems to put the last integer first the majority of the time, so I'm going to assume that the integers aren't uniformly distributed.

Answer 5

Ruby, 47 bytes

->a{b=a.flatten.shuffle;a.map{|x|x.map{b.pop}}}

Answer 6

05AB1E, 17 bytes

˜.r¹vDyg£DˆgF¦}}¯

˜                 Unflatten input
 .r               tmp = shuffle(flattened_input)
   ¹v             For each sub-array
     Dyg£         Take the first length(current_array) elements from tmp
         Dˆ       Append the result to a global array
           gF¦}   Remove the first elements from tmp
               }  End for
                ¯ Display the global array

Try it online!

I'm waiting for the 05AB1E or 2sable solution using some unflattening/molding built-in I don't know yet :) .

Answer 7

Brachylog, 17 bytes

c@~P,?:{l~l}a.cP,

Try it online!

Explanation

We basically create a list of sublists with variable elements that has the same "shape" as the Input, and then state that if we concatenate everything into a single list, it must result in a shuffle of the concatenation of the input into a single list.

c@~P,                 Concatenate the Input into a single list. Shuffle it and call that P.
     ?:{   }a.        The Output is the result of applying this to each element of the input:
        l~l               The Output is a list of same length as the Input.    
             .cP,     P is the concatenation of the sublists of the Output.

Answer 8

Bash, 63, 58 bytes

EDITS:

• Optimized sed expression a bit, -5 bytes

Note:

Bash does not really support multidimensional arrays (they can only be simulated, to some extent), so instead, this program will accept a "serialized" text representation of a rugged array, as depicted in the task description, e.g.: [[1,2,3],[4],[9,10]], and provide output in the same format.

Golfed

printf `sed 's/\w\+/%d/g'<<<$1` `grep -Po '\d+'<<<$1|shuf`

Test

>./shuffle []
[]

>./shuffle [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
[11,12,9,5,3,6,1,15,14,2,13,7,10,8,4]

>./shuffle [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
[9,15,11,10,7,6,1,14,2,3,12,5,4,13,8]

>./shuffle [[1,2,3],[4],[9,10]]
[[10,2,4],[9],[3,1]]

>./shuffle [[1,2,3],[4],[9,10]]
[[3,4,1],[10],[2,9]]

A nice bonus is that you can feed it rugged arrays of an arbitrary depth:

./shuffle [[1,[2,[3,[99,101]]],[4],[9,10]]
[[9,[4,[1,[101,2]]],[10],[3,99]]

and it will still operate correctly.

Try it online !

Answer 9

Perl, 37 bytes

36 bytes of code + -p flag.

@n=/\d+/g;s/\d+/splice@n,rand@n,1/ge

To run it:

perl -pE '@n=/\d+/g;s/\d+/splice@n,rand@n,1/ge' <<< "[[4],[1,2,3],[4]"

Explanations:

@n=/d+/g                # store all the integers in @n
s/\d+/                  # replace each integer with ...
splice@n,rand@n,1/ge    # a element at a random position of @n (which is deleted from @n)

Answer 10

APL, 35 bytes

I'm barely even beating Perl, there has to be something I'm missing.

{Z[?⍨⍴Z]⊂⍨(⍳⍴Z←∊⍵)∊⊃¨{⍵+⊃⌽⍺}\⍳¨⍴¨⍵}

E.g:

      {Z[?⍨⍴Z]⊂⍨(⍳⍴Z←∊⍵)∊⊃¨{⍵+⊃⌽⍺}\⍳¨⍴¨⍵}(1 2 3)(,4)(9 10)
┌──────┬─┬───┐
│10 3 2│1│9 4│
└──────┴─┴───┘

Explanation:

• Find the corresponding indices of the starts of the sub-arrays in a flattened array:
  • ⍳¨⍴¨⍵: For each sub-array, get a list of the indices
  • {⍵+⊃⌽⍺}\: Starting with the first sub-array, add the last value in the array to each value in the next array.
  • ⊃¨: get the first items of the arrays, which are the starting places
  • (⍳⍴Z←∊⍵)∊: store the flattened array in Z. Generate a bit-vector where the ones mark the places where the sub-arrays should start.
• Shuffle the flattened array:
  • ?⍨⍴Z: generate a random permutation of Z.
  • Z[...]: permute Z.
• ⊂⍨: Split up the permutation in sub-arrays according to the bit-vector.

Answer 11

Pyth, 15 bytes

tPc.SsQ.u+NlYQ0

A program that takes input of a list and prints the result.

Test suite

How it works

tPc.SsQ.u+NlYQ0  Program. Input: Q
       .u    Q0  (1) Reduce Q with starting value 0, returning all results:
         +        Add
          N       the current value
           lY     to the length of the next element of Q
     sQ          Flatten Q
   .S            (2) Randomly shuffle
  c              Chop (1) at every location in (2)
tP               Discard the first and last elements
                 Implicitly print

Answer 12

PHP, 105 bytes

$m=array_merge(...$i=$_GET[i]);shuffle($m);foreach($i as$v)$o[]=array_splice($m,0,count($v));print_r($o);

reduced to 105 bytes thanks to user59178.

Original answer:

PHP, 132 bytes

$i=$_GET['i'];$m=call_user_func_array('array_merge',$i);shuffle($m);foreach($i as$v){$o[]=array_splice($m,0,count($v));}print_r($o);

Answer 13

Mathematica, 67 Bytes

ReplacePart[#,Thread[RandomSample@Position[#,_Integer]->Union@@#]]&

Explanation: This shuffles the list of positions of all integers in the 2D ragged array. Union@@ is short for Flatten@

Note: Squiggly brackets {} are used instead of brackets [].

Answer 14

Factor + arrays.shaped, 67 bytes

[ [ flatten randomize ] [ array-replace ] bi [ cut swap ] map nip ]

Try it online!

Explanation

Assumes the input is always a 2D array.

• [ flatten randomize ] [ array-replace ] bi Place the flat, shuffled version of the input and the lengths of its rows on the stack.
• [ cut swap ] map nip Create a ragged array from a flat sequence and a list of lengths. See https://codegolf.stackexchange.com/a/233190/97916.

Answer 15

K (ngn/k), 18 bytes

{(,/x)@<==0N?&#'x}

Try it online!

• &#'x build a list containing n-copies of each top level index, where n is the length of each element of the ragged list (e.g. 0 1 1 1 2)
• 0N? shuffle that list
• <== group the indices, group them again (to essentially flip the keys and values of the dictionary), and sort them ascending (this preserves the original order of the lengths)
• (,/x)@ index into the flattened input and (implicitly) return

Answer 16

Vyxal, 5 bytes

fÞ℅$•

Try it Online!

f     # Flatten
 Þ℅   # Shuffle
   $• # Mold to original shape

Answer 17

Octave , 60 bytes

@(a)mat2cell([a{:}](randperm(sum(s=cellfun(@numel,a)))),1,s)

Answer 18

MATLAB, 84 bytes

function b=g(c);a=[c{:}];a=a(randperm(numel(a)));b=mat2cell(a,1,cellfun('length',c))

Answer 19

Java, 368 bytes

interface Z{int w(int i);default Z m(int n,int s){return i->w(i)+i>=n?s:0;}static int[][]f(int[][]r){int L=0,o=0,x,d,e=0;Z u=i->0,v=i->i;for(int[]a:r){d=a.length;L+=d;u=u.m(L,1);v=v.m(L,-d);}int[]c=new int[L];for(;e<L;)c[e++]=(int)(L*Math.random());for(int[]a:r){for(x=0;x<a.length;){d=c[x+o];e=v.w(d);d=u.w(d);L=a[x];a[x++]=r[d][e];r[d][e]=L;}o+=a.length;}return r;}}

the method static int[][] f( int[][] r ){...} solves the challenge. decided to roll my own functional interface to avoid an import and to add in a default method for ease of use

interface Z{ //define my own functional interface instead of importing

  int w(int i);

  //return a new lambda
  //where w(int i) adds the value s
  //to the result when i is greater than n
  default Z m(int n,int s){
      return i->w(i)+i>=n?s:0;
  }

  static int[][]f(int[][]r){
      int L=0,o=0,x,d,e=0;
      Z u=i->0, //lambda to convert a flattened index to the input's first dimension index
        v=i->i; //lambda to convert a flattened index to the input's second dimension index
      for(int[]a:r){
          d=a.length;
          L+=d; //running total of the lengths
          u=u.m(L,1); //increment the 1st conversion by 1 at every array length
          v=v.m(L,-d); //decrement the 2nd conversion by the array length after that length
      }
      int[]c=new int[L]; //will contain flattened index swapping positions
      for(;e<L;) //randomize the swap positions
          c[e++]=(int)(L*Math.random());
      for(int[]a:r){ //swap the elements from the input
          for(x=0;x<a.length;){
              d=c[x+o]; //flattened swap index
              e=v.w(d); //convert swap index to 2nd dimension index
              d=u.w(d); //convert swap index to 1st dimension index
              L=a[x];
              a[x++]=r[d][e];
              r[d][e]=L;
          }
          o+=a.length; //increment offset for flattened index array
      }
      return r;
  }

}

Answer 20

q, 36 bytes

{(0,sums -1_count each x)_0N?raze x}

k, 22 bytes

{(0,+\-1_#:'x)_0N?,/x}