25
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Related. \$\endgroup\$ Dec 8, 2016 at 21:17
  • 1
    \$\begingroup\$ Will the input always be a 2D array? \$\endgroup\$
    – Dennis
    Dec 8, 2016 at 22:32

20 Answers 20

18
\$\begingroup\$

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!

\$\endgroup\$
6
  • 4
    \$\begingroup\$ Wow, unflatten is a neat and unexpected command. \$\endgroup\$ Dec 8, 2016 at 21:58
  • 4
    \$\begingroup\$ Unflatten might not be the best term since the left argument doesn't have to be flat. The mnemonic is mold. \$\endgroup\$
    – Dennis
    Dec 8, 2016 at 22:21
  • \$\begingroup\$ @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.) \$\endgroup\$
    – user62131
    Dec 8, 2016 at 22:34
  • \$\begingroup\$ I mean that the left argument of can be anything, not just a flat list. For example: tio.run/nexus/jelly#@/9wZ@P///@jow11FIxidRSijXUUTEC0qY6CWWzs/… \$\endgroup\$
    – Dennis
    Dec 8, 2016 at 22:40
  • 1
    \$\begingroup\$ 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… \$\endgroup\$
    – user62131
    Dec 8, 2016 at 22:42
7
\$\begingroup\$

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]]
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I don't know python that well, but couldn't you do shuffle(r=sum(x,[]))? \$\endgroup\$ Dec 8, 2016 at 22:49
  • 1
    \$\begingroup\$ No, shuffle shuffles in place and returns None. \$\endgroup\$
    – Dennis
    Dec 8, 2016 at 22:51
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ "You can assume that your language's built-in random is random." \$\endgroup\$ Dec 8, 2016 at 22:44
  • \$\begingroup\$ @ConorO'Brien "Each integer must have an equally likely chance to appear in each possible location." \$\endgroup\$ Dec 8, 2016 at 23:04
  • \$\begingroup\$ 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. \$\endgroup\$
    – user62131
    Dec 9, 2016 at 2:31
2
\$\begingroup\$

Ruby, 47 bytes

->a{b=a.flatten.shuffle;a.map{|x|x.map{b.pop}}}
\$\endgroup\$
2
\$\begingroup\$

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 :) .

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 28, 2022 at 9:08
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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 !

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

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)
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You could do an in-place replacement. Assignment allowed you to flatten the variable: A⊣(∊A)←(∊A)[?⍨≢∊A←⎕] \$\endgroup\$
    – Adám
    Dec 12, 2016 at 21:43
  • \$\begingroup\$ @Adám: wow, I did not know you could do that. Is there a list of which functions can do this? \$\endgroup\$
    – marinus
    Dec 14, 2016 at 18:20
  • 1
    \$\begingroup\$ Yes. And it works with modified assignment too. \$\endgroup\$
    – Adám
    Dec 14, 2016 at 18:23
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$
1
  • \$\begingroup\$ $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. \$\endgroup\$
    – user59178
    Dec 9, 2016 at 12:32
1
\$\begingroup\$

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 [].

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

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 5 bytes

fÞ℅$•

Try it Online!

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

Octave , 60 bytes

@(a)mat2cell([a{:}](randperm(sum(s=cellfun(@numel,a)))),1,s)
\$\endgroup\$
0
\$\begingroup\$

MATLAB, 84 bytes

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

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

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

q, 36 bytes

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

k, 22 bytes

{(0,+\-1_#:'x)_0N?,/x}
\$\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.