35
\$\begingroup\$

About the Series

I will be running a little series of code-golf challenges revolving around the theme of randomness. This will basically be a 9-Hole Golf Course, but spread out over several questions. You may participate in any challenge individually as if it was a normal question.

However, I will maintain a leaderboard across all challenges. The series will run over 9 challenges (for now), one posted every few days. Every user who participates in all 9 challenges is eligible for winning the entire series. Their overall score is the sum of their shortest submissions on each challenge (so if you answer a challenge twice, only the better answer one is counted towards the score). If anyone holds the top spot on this overall leaderboard for 28 days I will award them a bounty of 500 rep.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

Hole 1: Shuffle an Array

The first task is pretty simple: given a non-empty array of integers, shuffle it randomly. There are a few rules though:

  • Every possible permutation must be returned with the same probability (so the shuffle should have a uniform distribution). You can check if your algorithm is uniform/unbiased by implementing it in JavaScript on Will it Shuffle, which will produce a matrix of the biases - the result should look as uniform as their built-ins Fisher-Yates or sort (random order).
  • You must not use any built-in or 3rd-party method to shuffle the array or generate a random permutation (or enumerate all permutations). In particular, the only built-in random function you may use is getting a single random number at a time. You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval (in a mathematical sense - you may ignore details of floating-point representation here). If your language lets you obtain a list of m random numbers at once, you may use this facility, provided the m numbers are independent of each other, and you count it as O(m).
  • Your implementation must not exceed a time complexity of O(N), where N is the size of the array to be shuffled. For instance, you cannot "sort by random numbers".
  • You may either shuffle the array in place, or create a new array (in which case the old array may be modified however you like).

You may write a full program or a function and take input via STDIN, command-line argument, function argument or prompt and produce output via return value or by printing to STDOUT (or closest alternative). If you write a function that shuffles the array in place, you don't need to return it of course (provided your language lets you access the modified array after the function returns).

Input and output may be in any convenient list or string format, but must support arbitrary integers in the range -231 ≤ x < 231. In principle, your code should work for arrays up to length 231, although this doesn't necessarily have to fit in your memory or complete within a reasonable amount of time. (I just don't want to see arbitrary size limits to hardcode loops or something.)

This is code golf, so the shortest submission (in bytes) wins.

Leaderboard

The following snippet will generate a leaderboard across all challenges of the series.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)

/* Configuration */

var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}


function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:&lt;(?:s&gt;((?!&gt;).)*&lt;\/s&gt;|((?!&gt;).)+&gt;)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });
  
  
  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }  
  
  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });
  
  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}
body { text-align: left !important}

#leaderboard {
  width: 500px; 
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
11
  • 8
    \$\begingroup\$ I am disappointed that we are not allowed to be "clever" and use library functions other than "get a random number". Do we want to look at yet another 69 implementations of Fisher-Yates shuffling? Please consider removing this rule in future tasks. Also, why a limit on time complexity? Please consider relaxing it to at least O(n^2); I also think someone might find an especially golfed implementation if you allow O(n!). \$\endgroup\$
    – anatolyg
    Feb 3, 2015 at 20:58
  • 7
    \$\begingroup\$ @anatolyg Removing the restrictions amounts to every answer being either sortby(random) (the reason for the time restriction) or simply .shuffle() (the reason for the built-ins restriction), which I think is a lot less clever than having to implement Fisher-Yates or some other approach. \$\endgroup\$ Feb 3, 2015 at 21:03
  • 1
    \$\begingroup\$ If shuffling in place, does a function have to return the array, or is it enough that it is modified? Can I write a function for shuffle(array) instead of newArray=shuffle(array)? \$\endgroup\$
    – Geobits
    Feb 4, 2015 at 2:30
  • 1
    \$\begingroup\$ @Bakuriu Claiming that you can sort in linear time if the numbers are fixed is a bit like claiming you can do anything in O(1) if the input sizes are fixed. Also the relevant restriction is fixed-size arrays, not fixed-size integers - because the array size determines how large you need your random numbers to be. Anyway, the limitation on time complexity are of course for the general algorithm you implement, whereas the limits on input sizes are in place so you don't have to use arbitrary-precision integers if your language doesn't use them out of the box. \$\endgroup\$ Feb 4, 2015 at 9:48
  • 2
    \$\begingroup\$ Why is Adám's solution coming up as 43319 bytes when it's actually 14? \$\endgroup\$
    – boboquack
    May 14, 2017 at 0:10

35 Answers 35

21
\$\begingroup\$

Dyalog APL, 25 24 bytes

First for the 25-character solution: i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕

                      a←⎕ ⍝ evaluated input, assign to "a"
                     ⍴a   ⍝ length
                    ⍳⍴a   ⍝ 1 2 .. length
                   ⌽⍳⍴a   ⍝ length .. 2 1
                 i←       ⍝ assign to "i"
                ?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
   a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
        ←                 ⍝ in Dyalog, assignment returns its right-hand side
  ⊃                       ⍝ first element, i.e. a[⍵]
                          ⍝ the result from {} is an array of all those a[⍵]

After some equivalence transformations on the above:

i {}¨ ?i  ←→  i {}¨∘? i   ⍝ because A f∘g B ←→ A f g B
          ←→  {}¨∘?⍨ i    ⍝ because f⍨ B ←→ B f B

we can get rid of the assignment i← and save a character:

{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕

\$\endgroup\$
8
  • 3
    \$\begingroup\$ ... mind. blown. \$\endgroup\$
    – danwyand
    Feb 4, 2015 at 18:03
  • 1
    \$\begingroup\$ a language I have to read right to left?? wow! \$\endgroup\$
    – Luminous
    Feb 4, 2015 at 19:16
  • 5
    \$\begingroup\$ @Luminous as is often the case with mathematical notation: sin cos ln sqrt x \$\endgroup\$
    – ngn
    Feb 4, 2015 at 19:26
  • 4
    \$\begingroup\$ @ngn when you put it that way that makes my previous comment look laughable. ha. \$\endgroup\$
    – Luminous
    Feb 4, 2015 at 19:39
  • 5
    \$\begingroup\$ @ronalchn There are 8-bit encodings for APL, like this one or this other one; I heard Dyalog uses one of these, as an alternative to Unicode. \$\endgroup\$
    – anatolyg
    Feb 5, 2015 at 8:43
12
\$\begingroup\$

80386 machine code, 44 24 bytes

Hexdump of the code:

60 8b fa 0f c7 f0 33 d2 f7 f1 49 8b 04 8f 87 04
97 89 04 8f 75 ed 61 c3

Thanks to FUZxxl, who suggested using the rdrand instruction.

Here is the source code (can be compiled by Visual Studio):

__declspec(naked) void __fastcall shuffle(unsigned size, int array[])
{
    // fastcall convention:
    // ecx = size
    // edx = array
    _asm
    {
        pushad;             // save registers
        mov edi, edx;       // edi now points to the array

    myloop:
        rdrand eax;         // get a random number
        xor edx, edx;
        div ecx;            // edx = random index in the array

        dec ecx;            // count down
        mov eax, [edi + 4 * ecx];   // swap elements
        xchg eax, [edi + 4 * edx];  // swap elements
        mov [edi + 4 * ecx], eax;   // swap elements
        jnz myloop;

        popad;              // restore registers
        ret;
    }
}

Yet another Fisher-Yates implementation. Most of the golfing was achieved by passing parameters in registers.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You could have also used rdrand for shits and giggles. \$\endgroup\$
    – FUZxxl
    Feb 4, 2015 at 13:31
  • \$\begingroup\$ @FUZxxl I totally forgot about it! Too bad it removes the most interesting part about my answer... \$\endgroup\$
    – anatolyg
    Feb 4, 2015 at 13:37
9
\$\begingroup\$

Java, 88 101

A basic Fisher-Yates shuffle does the trick. I get the feeling it'll be used pretty commonly here, since it's quick and easy to implement. There's some loop/assignment cramming here, but there's honestly not too much to golf; it's just short by nature.

void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}

With some line breaks:

void t(int[]s){
    for(int i=s.length,t,x;
        i>0;
        t=s[x*=Math.random()],
        s[x]=s[i],
        s[i]=t
    )
        x=i--;
}

This shuffles in place, modifying the original array s[]. Test program:

public class Shuffle {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        new Shuffle().t(a);
        for(int b:a)
            System.out.print(b+" ");
    }
    void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}
}
\$\endgroup\$
21
  • 1
    \$\begingroup\$ No, the challenge states that you can assume that it "is perfectly uniform over the requested range". The requested range of Math.random() has a size which is a power of two, so this doesn't meet spec. \$\endgroup\$ Feb 3, 2015 at 15:52
  • 1
    \$\begingroup\$ @PeterTaylor Jan's and Geobits' interpretations are indeed how I intended the rule - that you don't have to worry about the actual cycle-length of your PRNG. \$\endgroup\$ Feb 3, 2015 at 16:02
  • 1
    \$\begingroup\$ @MartinBüttner the cycle length is not the issue here - that is covered by your rule. The coarseness of floats is. \$\endgroup\$ Feb 3, 2015 at 16:05
  • 3
    \$\begingroup\$ @TheBestOne It's one byte shorter than the only currently-posted python solution ;) \$\endgroup\$
    – Geobits
    Feb 3, 2015 at 18:00
  • 1
    \$\begingroup\$ Not any more! :D \$\endgroup\$
    – Sp3000
    Feb 4, 2015 at 0:03
8
\$\begingroup\$

Python 2, 86 bytes

from random import*
def S(L):i=len(L);exec"i-=1;j=randint(0,i);L[i],L[j]=L[j],L[i];"*i

This is a function which shuffles the array in place without returning it, using a straightforward implementation of the Fisher-Yates shuffle. Getting random numbers from Python is expensive...

Thanks to @xnor and @colevk for tips.

\$\endgroup\$
4
  • \$\begingroup\$ That range expression looks pretty cumbersome. Surely it's shorter to count down manually as while i:i-=1;...? \$\endgroup\$
    – xnor
    Feb 3, 2015 at 17:14
  • \$\begingroup\$ @xnor Yeah it is - thanks for that. I keep forgetting that while tends to be shorter than for for this sort of thing... \$\endgroup\$
    – Sp3000
    Feb 3, 2015 at 21:54
  • 1
    \$\begingroup\$ Awww... now my Java answer isn't beating this. I was quite happy for a very short while :( \$\endgroup\$
    – Geobits
    Feb 3, 2015 at 23:56
  • \$\begingroup\$ You can save another 2 bytes by making i=len(L) and putting the decrement at the beginning of the while loop. \$\endgroup\$
    – colevk
    Feb 4, 2015 at 2:45
8
\$\begingroup\$

J, 45 44 characters

This was a tricky one.

<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

Here is an explanation:

  1. # y: The tally of y, that is, the number of elements in y.
  2. ?@# y: A random number uniformly distributed over the range from 1 to (#y)-1.
  3. x { y: The item from y at index x.
  4. (<<<x) { y: All items except the item at index x in y.
  5. x , y: y appended to x.
  6. x ({ , <^:3@[ { ]) y: The item at index x in y, then all the other items.
  7. (?@# ({ , <^:3@[ { ]) ]) y A random it from y, then all the other items.
  8. x {. y: The first x items taken from y.
  9. x }. y: The first x items dropped from y.
  10. x ({. , }.) y: The first x items taken from y, then the first x items dropped from y
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: The first x items taken from y, then the first x items from y processed as in number 7.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: The same thing with the drop pulled in to save one character.
  13. u/ y: u inserted between the items of y.
  14. < y: y boxed.
  15. <"0 y: Each item of y boxed.
  16. i. y: integers from 0 to y - 1.
  17. i.@# y: integers from 0 to (#y) - 1.
  18. (<"0@i.@# , <) y: Integers from 0 to (#y) - 1 each boxed and then y in a single box. This is needed because arrays in J are uniform. A box hides the shape of its content.
  19. x u&v y: like (v x) u (v y).
  20. > y: y opened, that is, without its box.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y the phrase from number 12 applied to its unboxed arguments.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y the phrase from number 21 inserted between items of y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) y the phrase from number 22 applied to the the result of the phrase from number 18, or, a uniform permutation of the items of y.
\$\endgroup\$
11
  • 1
    \$\begingroup\$ I just can't distinguish all the parentheses. And that triple boxing <@<@<@[ is also a mystery... Waiting for explanation. :) \$\endgroup\$
    – randomra
    Feb 3, 2015 at 16:08
  • 2
    \$\begingroup\$ Once this gets explained, I might be much more likely to upvote this answer ;-) \$\endgroup\$ Feb 3, 2015 at 16:12
  • \$\begingroup\$ @randomra Here you go. \$\endgroup\$
    – FUZxxl
    Feb 3, 2015 at 16:25
  • \$\begingroup\$ @JanDvorak Is the explanation satisfying? \$\endgroup\$
    – FUZxxl
    Feb 3, 2015 at 16:30
  • \$\begingroup\$ Great explanation! I didn't know about all the boxed use of from ({). And I really like the &>/ trick to manipulate a list. I'm sure I could have used it a couple times before. \$\endgroup\$
    – randomra
    Feb 3, 2015 at 16:49
5
\$\begingroup\$

Pyth, 25 bytes

Test it here.

Yet another Fisher-Yates implementation. Is essentially the same as @Sp3000 python solution, just in pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Thanks to @Jakube for the swapping trick

<implicit>    Q=input()
FNrlQ1        For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
 KON          K = random int 0-N
 J@QN         J=Q[N]
 <space>      Suppress print
 XXQN@QKKJ    Swap K and J
)             End for
Q             Print Q
\$\endgroup\$
2
  • \$\begingroup\$ You can save two bytes by combining those two list assignments: ` XXQN@QKKJ` instead of ` XQN@QK XQKJ`. \$\endgroup\$
    – Jakube
    Apr 7, 2015 at 21:24
  • \$\begingroup\$ @Jakube thanks for the tip. I knew there must have been a way to swap values in a list, and this is really smart. You should add it to the tips list. \$\endgroup\$
    – Maltysen
    Apr 7, 2015 at 21:35
4
\$\begingroup\$

Perl, 68 56 44

Like many other solutions, this uses the Fisher-Yates algorithm.

Using nutki's comment, 12 characters are saved by using $_ instead of $i and performing the operations in the array indices.

44:

sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}

56:

sub f{$i=@_;$j=int(rand$i),@_[$i,$j]=@_[$j,$i]while$i--}

This is my first codegolf.

\$\endgroup\$
1
  • \$\begingroup\$ Not a bad start, I did not know that you can use @_[...] as rvalue like that. Can be golfed further into sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}. \$\endgroup\$
    – nutki
    Feb 6, 2015 at 11:32
3
\$\begingroup\$

C, 63 61 60 bytes

i,t;s(a,m)int*a;{for(;m;a[m]=t)t=a[i=rand()%m--],a[i]=a[m];}

Just a straight implementation of Fischer-Yates that sorts the given array in place. Compiles and links perfectly fine with the visual studio compiler (vs2013, haven't tested the other versions) and the Intel Compiler. Nice looking function signature is s(int array[], int length). I'm legitimately impressed I beat Python and Ruby.

This does assume srand() is called and rand() is implemented properly, but I believe this rule allows for that:

You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval

Nicely formatted version:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
\$\endgroup\$
8
  • \$\begingroup\$ I think it suffices to make the function header s(a,m)*a{, but I'm not sure and don't want to test either. You might want to do a xor-swap, like in a[i]^=a[m]^=a[i]^=a[m]. This also avoids the need to declare t. \$\endgroup\$
    – FUZxxl
    Feb 3, 2015 at 22:03
  • \$\begingroup\$ @FUZxxl I believe an xor swap causes problems if i==m. \$\endgroup\$
    – Geobits
    Feb 3, 2015 at 22:38
  • \$\begingroup\$ @Geobits indeed. I missed that possibility. \$\endgroup\$
    – FUZxxl
    Feb 3, 2015 at 22:40
  • \$\begingroup\$ I was just trying to figure out why that wasn't working... should have remembered that. Also I do need s(a,m)int*a for visual studio and the intel compiler. Don't have gcc or clang installed to test, but I assume they will also complain. \$\endgroup\$ Feb 3, 2015 at 22:43
  • \$\begingroup\$ This is pretty impressively golfed. After trying a lot of modifications that didn't save anything, I did manage to see a way to save 2 characters. If you change the swap order so that the first swap statement becomes t=a[i], you can then move the i=rand()%m-- statement inside as the array index. \$\endgroup\$
    – Runer112
    Feb 4, 2015 at 18:17
3
\$\begingroup\$

Octave, 88 77 bytes

function s=r(s)for(i=length(s):-1:1)t=s(x=randi(i));s(x)=s(i);s(i)=t;end;end

Yet another Fisher-Yates implementation... Should be fairly straightforward if I add the usual line returns and spacing:

function s=r(s)
  for(i=length(s):-1:1) # Counting down from i to 1
    t=s(x=randi(i));    # randi is builtin number generator for an int from 0 to i
    s(x)=s(i);
    s(i)=t;
  end
end

The "end" keywords really kill the golf score here, unfortunately. Hey, I can use "end" instead of "endfor" and "endfunction"!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Just FYI, the "bytes" isn't really required by the code, it just makes sure there is a headline, which contains a comma (to separate the language) and at least one number after the comma, and then just chooses the last number that isn't crossed out. Having "bytes" in there is still nice though. ;) \$\endgroup\$ Feb 6, 2015 at 19:11
  • 1
    \$\begingroup\$ You could save 1 byte by using numel instead of lenght. As a bonus your program would also work with 2-D arrays aka matrices ;) \$\endgroup\$ Aug 17, 2016 at 13:46
2
\$\begingroup\$

Java 8, 77

(x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};

It's a lambda taking int[] and returning void. My first attempt seemed not very interesting, so I decided to have it exit by throwing an exception.

Test program:

interface shuff {
    void shuff(int[] x);
}
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        shuff s = (x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};
        int[] x = {3, 9, 2, 93, 32, 39, 4, 5, 5, 5, 6, 0};
        try {
            s.shuff(x);
        } catch(ArrayIndexOutOfBoundsException _) {}
        for(int a:x) System.out.println(a);
    }
}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Isn't it cheating to use a lambda to get around having to write a function signature, when you have to supply a delegate in order to use the lambda anywhere? Also... can't you drop the parentheses around Math.random()? \$\endgroup\$
    – Rawling
    Feb 4, 2015 at 14:37
  • 1
    \$\begingroup\$ @Rawling You could vote in this meta question. Currently, there are 9 votes in favor of lambdas, and 0 against. Yes, the parentheses can be removed. \$\endgroup\$
    – feersum
    Feb 4, 2015 at 19:52
  • \$\begingroup\$ Huh, if there's a meta post and a so-far-consensus then fire away. (And enjoy the two-lower golf score on me :p) \$\endgroup\$
    – Rawling
    Feb 4, 2015 at 22:15
  • 3
    \$\begingroup\$ I think, it's unfair for function to stop by exception in a normal case, is it? \$\endgroup\$
    – Qwertiy
    Feb 4, 2015 at 23:34
  • 1
    \$\begingroup\$ @Qwertiy To each his own... You think it's unfair, I think it's great. \$\endgroup\$
    – feersum
    Feb 4, 2015 at 23:36
2
\$\begingroup\$

Golflua, 37

How to run Golflua?

~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$

The input is provided as a table in the variable X. The table is shuffled in place.

Example usage:

> X={0,-45,8,11,2}
> ~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$
> w(T.u(X))
-45 0 8 11 2
\$\endgroup\$
2
\$\begingroup\$

R, 79 bytes

f=function(x){n=length(x);for(i in 1:n){j=sample(i:n,1);x[c(i,j)]=x[c(j,i)]};x}

This is a straightforward implementation of the Fisher-Yates shuffle. The R function sample draws a simple random sample of a given size from a given vector with equal probability. Here we're drawing a random sample of size 1 at each iteration from the integers i, ..., n. As stated in the question, this can be assumed to be O(1), so in all this implementation should be O(N).

\$\endgroup\$
2
\$\begingroup\$

Matlab, 67

Also implementing Fisher-Yates.

a=input('');n=numel(a);for i=1:n;k=randi(i);a([i,k])=a([k,i]);end;a

I thought it was too bad I could not use Matlab's randperm function. But after some fiddling around, I thought I may look at the source of randperm to see how it is done, and I was astonished to see that there was just one line: [~,p] = sort(rand(1,n)) =)

\$\endgroup\$
2
\$\begingroup\$

Perl, 44

sub f{($_[$x],$_)=($_,$_[$x=rand++$i])for@_}

Another perl in 44 characters. Example use:

@x=(1..9);f(@x);print@x
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 82 90 83 93 bytes

Note: This variation the Fisher-Yates shuffle is actually Martin Büttner's solution, with some code paring by alephalpha. s is the input array. Nothing fancy-smancy, but sometimes the simple things are the most elusive.

f@s_:=(a=s;m=Length@a;Do[t=a[[r=RandomInteger@{1,m-1}]];a[[r]]=a[[m]]; a[[m]]=t,{n,1,m-1}];a)
\$\endgroup\$
1
  • \$\begingroup\$ You can use Do here. It's shorter than While. \$\endgroup\$
    – alephalpha
    Feb 7, 2015 at 10:36
2
\$\begingroup\$

Ruby, 57 bytes

->a{a.size.times{|i|j=rand(i+1);a[i],a[j]=a[j],a[i]};p a}

Input (as lambda function):

f.([1,2,3,4,5])

Output:

[2, 1, 4, 3, 5]
\$\endgroup\$
2
\$\begingroup\$

TI-BASIC, 46 bytes

For(X,dim(L1),2,-1:randInt(1,X→Y:L1(X→Z:L1(Y→L1(X:Z→L1(Y:L1

1   111   2  1111112       1111112 111112 1112 111112 1112

Source for byte count

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You're missing the End. \$\endgroup\$
    – lirtosiast
    Sep 30, 2015 at 7:05
2
\$\begingroup\$

K, 31 chars

f:{{l[i:x,1?x]:l@|i}'|!#l::x;l}

Not quite as short as the one I put up before (which got disqualified)...oh well.

It's a basic Fisher-Yates shuffle. This was built with lots of help from the Kona mailing list.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 66

This function shuffles the array in place. It also returns a byproduct array that is NOT the shuffled output and must not be considered.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)
\$\endgroup\$
2
\$\begingroup\$

MATL, 16 bytes

XH`HnYr&)XHxvHHn

Try it online!

Fisher-Yates in MATL. Almost a third of this program is devoted to the letter H, which corresponds to the clipboard function in MATL.

Basically, H stores the unused items from the input, while the stack keeps track of the shuffled list.

\$\endgroup\$
2
\$\begingroup\$

Japt, 12

rÈiMqZÄ Y}[]

Try it!

-10 (about half ;) thanks to @Shaggy!

I have been wanting to try out a golfing language, and the Japt interpreter had good documentation and a way to try things out in the browser.

Below is the strategy I took:

  • Reduce input seeding with an empty array
  • At each step, find a random slot to insert the current element
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Japt, good to have you with us. I think this works for 9 bytes, using the same method. If the RNG isn't satisfactory, though, then try this instead. \$\endgroup\$
    – Shaggy
    Jan 20, 2019 at 17:58
  • \$\begingroup\$ @Shaggy - Thanks for the tips! :) I ended up using a slightly modified version of your 2nd solution. Since the 3rd parameter of the reduce function is an index, we already know the length. \$\endgroup\$
    – dana
    Jan 20, 2019 at 18:34
1
\$\begingroup\$

Javascript ES6, 69

a=>{m=a.length;while(m)[a[m],a[i]]=[a[i=~~(Math.random()*m--)],a[m]]}

It's Fisher–Yates.

PS: Can be tested in Firefox

\$\endgroup\$
1
  • \$\begingroup\$ @MartinBüttner, removed it :) \$\endgroup\$
    – Qwertiy
    Feb 4, 2015 at 23:30
1
\$\begingroup\$

Pyth, 27 bytes

Test it here

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

This is an implementation of the incremental Fisher-Yates shuffle, mentioned second here.

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

Haskell, 170

import System.Random
import Data.Array.IO
s a=do(_,n)<-getBounds a;sequence$map(\i->do j<-randomRIO(i,n);p<-a%i;q<-a%j;writeArray a j p;return q)[1..n]where(%)=readArray

Another Fisher-Yates solution inspired by the algorithm at https://wiki.haskell.org/Random_shuffle.

s is a function which has signature: IOArray Int a -> IO [a]

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

CJam - 30

q~_,,W%{_I=I)mr:J2$=@I@tJ@t}fI

Try it at http://cjam.aditsu.net/

Example input: [10 20 30 40 50]
Example output: 3020401050 (add a p at the end of the code for pretty printing)

If the code is allowed to take the input from the stack (like a function), then the first 2 characters can be removed, reducing the size to 28.

Explanation:

The code is longer than I hoped, due to the lack of a "swap" operator for arrays
(to be implemented later :p)

q~            read and evaluate the input (let's call the array "A")
_,,           make an array [0 1 2 ... N-1] where N is the size of A
W%            reverse the array, obtaining [N-1 ... 2 1 0]
{…}fI         for I in this array
    _I=       push A[I]
    I)mr:J    push a random number from 0 to I (inclusive) and store it in J
              stack: A, A[I], J
    2$=       get A[J]
    @I@t      set A[I] = A[J]
              stack: former A[I], A
    J@t       set A[J] = former A[I]
\$\endgroup\$
4
  • \$\begingroup\$ As mentioned in the comments, I'm afraid this is invalid. At the very least _ is O(N) (inside an O(N) loop). Unfortunately, I don't see a way to work around that in CJam. \$\endgroup\$ Feb 5, 2015 at 17:58
  • \$\begingroup\$ Lists are handled like immutable objects, so duplication is just implemented as duplicating the reference. It's actually the t that kills it, as it can't mutate the list and now must create a copy. \$\endgroup\$
    – Runer112
    Feb 5, 2015 at 18:18
  • \$\begingroup\$ @MartinBüttner I was about to post the same thing as Runer112; yes there might be a problem with t, I'd like to improve it in future versions.. \$\endgroup\$ Feb 5, 2015 at 18:20
  • \$\begingroup\$ So this code follows the spirit of the question, but not the "letter", due to internal language implementation issues. \$\endgroup\$ Feb 5, 2015 at 18:22
1
\$\begingroup\$

JavaScript (ES 6), 61

S=a=>(a.map((c,i)=>(a[i]=a[j=Math.random()*++i|0],a[j]=c)),a)

You can test it here by just adding a line that says shuffle = S (Firefox only).

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

STATA, 161

di _r(s)
set ob wordcount($s)
token $s
g a=0
foreach x in $s{
gl j=floor(runiform()*_n)+1
replace a=`$j' if word($s,_n)=`x'
replace a=`x' if word($s,_n)=`$j'
}
l

Expects input as space separated numbers. I can remove the headers and observation numbers from the output if you would like, but otherwise this is shorter.

\$\endgroup\$
2
  • \$\begingroup\$ What's _n in this? \$\endgroup\$ Feb 3, 2015 at 16:30
  • \$\begingroup\$ _n is the number of the current observation. \$\endgroup\$
    – bmarks
    Feb 3, 2015 at 16:35
1
\$\begingroup\$

Java, 93 bytes

a->{for(int b=0,c,d=0,e=a.length;b<e;c=a[b],a[b]=a[d],a[d]=c,b++,d=b)d+=Math.random()*(e-b);}

Example usage: http://ideone.com/RqSMnZ

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

SQF, 91 bytes

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is biased (see "swap (i <-> random)" on Will It Shuffle), but you can turn it into Fisher-Yates (which is unbiased) by replacing %x with %i. \$\endgroup\$ Feb 4, 2015 at 9:53
1
\$\begingroup\$

Perl, 41 bytes

sub f{push@b,splice@_,rand@_,1while@_;@b}

Try it online!

\$\endgroup\$

Your Answer

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

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