# Shuffle a ragged array

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.

• Related. Commented Dec 8, 2016 at 21:17
• Will the input always be a 2D array? Commented Dec 8, 2016 at 22:32

# 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!

• Wow, unflatten is a neat and unexpected command. Commented Dec 8, 2016 at 21:58
• Unflatten might not be the best term since the left argument doesn't have to be flat. The mnemonic is mold. Commented Dec 8, 2016 at 22:21
• @Dennis: Does that mean that it wouldn't work correctly for this challenge on an input ragged array that contained lists as elements, rather than integers (because it'll flatten the inside lists first)? That's a little disappointing, you'd expect it to work regardless of the type that the ragged array had. (Update: I checked, it seems that both F and ṁ work for multiple layers of flattening, not just one.)
– user62131
Commented Dec 8, 2016 at 22:34
• I mean that the left argument of ṁ can be anything, not just a flat list. For example: tio.run/nexus/jelly#@/9wZ@P///@jow11FIxidRSijXUUTEC0qY6CWWzs/… Commented Dec 8, 2016 at 22:40
• Oh, I'd call that an unflatten operation; the left argument is being treated as a flat list (just it happens to contain lists as elements, but those elements are being interpreted as opaque). Actually, I suspect we agree on what unflattening is but disagree on what flattening is…
– user62131
Commented Dec 8, 2016 at 22:42

## 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]]  # 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! • I don't know python that well, but couldn't you do shuffle(r=sum(x,[]))? Commented Dec 8, 2016 at 22:49 • No, shuffle shuffles in place and returns None. Commented Dec 8, 2016 at 22:51 # 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. • "You can assume that your language's built-in random is random." Commented Dec 8, 2016 at 22:44 • @ConorO'Brien "Each integer must have an equally likely chance to appear in each possible location." Commented Dec 8, 2016 at 23:04 • sort doesn't work properly when given an inconsistent comparison key. Even if the language's random is random, its sort will malfunction in this situation, and that's what's creating the bias you're seeing. As such, I think the second solution is incorrect. – user62131 Commented Dec 9, 2016 at 2:31 # Ruby, 47 bytes ->a{b=a.flatten.shuffle;a.map{|x|x.map{b.pop}}}  # 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 :) . • 7 bytes: ˜.rI€g£ - try it online (with 10 random outputs). It's likely £ didn't act like that yet with a list argument when you posted your answer, although it does work in the latest legacy version. Commented Nov 28, 2022 at 9:08 # 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.  # 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 ! ## 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)  # 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. • You could do an in-place replacement. Assignment allowed you to flatten the variable: A⊣(∊A)←(∊A)[?⍨≢∊A←⎕] – Adám Commented Dec 12, 2016 at 21:43 • @Adám: wow, I did not know you could do that. Is there a list of which functions can do this? Commented Dec 14, 2016 at 18:20 • Yes. And it works with modified assignment too. – Adám Commented Dec 14, 2016 at 18:23 # 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  # 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);

• $m=array_merge(...$i=$_GET[i]); is 25 bytes shorter than $i=$_GET['i'];$m=call_user_func_array('array_merge',$i); and does the same thing. In addition you can drop the {} after the foreach to save 2 more bytes. Commented Dec 9, 2016 at 12:32 ## 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 []. # 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. # 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 # Vyxal, 5 bytes fÞ℅$•


Try it Online!

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


# Octave , 60 bytes

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


# MATLAB, 84 bytes

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


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

}


# q, 36 bytes

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


# k, 22 bytes

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