O serii

Będę prowadził serię golfowych wyzwań związanych z przypadkowością. Będzie to w zasadzie 9-dołkowe pole golfowe , ale rozłożone na kilka pytań. Możesz brać udział w każdym wyzwaniu indywidualnie, jakby to było normalne pytanie.

Będę jednak utrzymywać tabelę wyników we wszystkich wyzwaniach. Serial obejmie 9 wyzwań (na razie), jedno publikowane co kilka dni. Każdy użytkownik, który bierze udział we wszystkich 9 wyzwaniach, może wygrać całą serię. Ich ogólny wynik to suma ich najkrótszych zgłoszeń na każde wyzwanie (więc jeśli odpowiesz dwukrotnie na wyzwanie, tylko lepsza odpowiedź jest liczona do wyniku). Jeśli ktokolwiek będzie zajmował najwyższe miejsce w ogólnej tabeli liderów przez 28 dni , przyznam mu nagrodę w wysokości 500 powtórzeń .

Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .

Hole 1: Shuffle an Array

Pierwsze zadanie jest dość proste: biorąc pod uwagę niepustą tablicę liczb całkowitych, losowo ją potasuj. Istnieje jednak kilka zasad:

• Każda możliwa permutacja musi zostać zwrócona z takim samym prawdopodobieństwem (dlatego losowanie powinno mieć jednolity rozkład). Możesz sprawdzić, czy twój algorytm jest jednorodny / bezstronny, implementując go w JavaScript w Will it Shuffle , co wytworzy matrycę tendencyjności - wynik powinien wyglądać tak jednolicie, jak wbudowane Fisher-Yates lub sortować (kolejność losowa) .
• Nie wolno używać żadnej wbudowanej lub innej firmy metody tasowania tablicy lub generowania losowej permutacji (lub wyliczenia wszystkich permutacji). W szczególności jedyną wbudowaną funkcją losową, której możesz użyć, jest uzyskanie pojedynczej liczby losowej na raz . Państwo może założyć, że każdy wbudowaną losowych przebiegów metoda numer w czasie O (1) i jest idealnie równomierne na wymaganym przedziale (w sensie matematycznym - można zignorować szczegóły reprezentacji zmiennoprzecinkowej tutaj). Jeśli twój język pozwala ci uzyskać listę m liczb losowych naraz, możesz skorzystać z tej funkcji, pod warunkiem, że m liczb jest od siebie niezależnych i policzysz je jako O (m).
• Implementacja nie może przekraczać złożoności czasowej O (N) , gdzie N jest rozmiarem tablicy, która ma być tasowana. Na przykład nie można „sortować według liczb losowych”.
• Możesz albo przetasować tablicę na miejscu, albo utworzyć nową tablicę (w takim przypadku stara tablica może zostać zmodyfikowana w dowolny sposób).

Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, argumentu funkcji lub pytania i wygenerować dane wyjściowe za pomocą wartości zwracanej lub drukując do STDOUT (lub najbliższej alternatywy). Jeśli napiszesz funkcję, która przetasowuje tablicę w miejscu, nie musisz jej oczywiście zwracać (pod warunkiem, że Twój język pozwala na dostęp do zmodyfikowanej tablicy po powrocie funkcji).

Dane wejściowe i wyjściowe mogą być w dowolnym dogodnym formacie listy lub ciągu, ale muszą obsługiwać dowolne liczby całkowite z zakresu -2 ³¹ ≤ x <2 ³¹ . W zasadzie, Twój kod powinien działać dla tablic do długości 2 ^{do 31} , choć niekoniecznie muszą zmieścić się w pamięci lub kompletne w rozsądnym czasie. (Po prostu nie chcę widzieć dowolnych limitów wielkości pętli kodu twardego itp.)

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).

Tabela liderów

Poniższy fragment wygeneruje tabelę wyników we wszystkich wyzwaniach serii.

Aby mieć pewność, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).

/* 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&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\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>

Dyalog APL, 25 24 bajtów

Po pierwsze dla rozwiązania składającego się z 25 znaków: 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[⍵]

Po niektórych przekształceniach równoważności na powyższym:

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

możemy pozbyć się zadania i←i zapisać postać:

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

80386 kod maszynowy, 44 24 bajtów

Hexdump kodu:

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

Dzięki FUZxxl, który zasugerował użycie rdrandinstrukcji.

Oto kod źródłowy (może zostać skompilowany przez 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;
    }
}

Kolejna implementacja Fisher-Yates. Większość golfa została osiągnięta poprzez przekazanie parametrów do rejestrów.

Java, 88 101

Podstawowym tasowaniem jest Fisher-Yates. Mam wrażenie, że będzie tu używany dość często, ponieważ jest szybki i łatwy do wdrożenia. Jest tu trochę wkuwania pętli / zadań, ale tak naprawdę nie ma zbyt wiele do golfa; z natury jest krótki.

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

Z pewnymi podziałami linii:

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

To tasuje w miejscu, modyfikując oryginalną tablicę s[]. Program testowy:

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

Python 2, 86 bajtów

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

Jest to funkcja, która przetasowuje tablicę w miejscu bez zwracania jej, wykorzystując prostą implementację tasowania Fisher-Yates . Pobieranie losowych liczb z Pythona jest drogie ...

Dzięki @xnor i @colevk za wskazówki.

J, 45 44 znaków

To było trudne.

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

Oto wyjaśnienie:

1. # y: The tally of y, czyli liczba elementów wy .
2. ?@# y: Liczba losowa równomiernie rozmieszczona w zakresie od 1do(#y)-1 .
3. x { y: Pozycja z y indeksu x.
4. (<<<x) { y: Wszystkie elementy oprócz pozycji o indeksie xw y.
5. x , y: y dołączono do x.
6. x ({ , <^:3@[ { ]) y: Pozycja w indeksie xw y, a następnie wszystkie inne pozycje.
7. (?@# ({ , <^:3@[ { ]) ]) yLosowo z y, a następnie wszystkie inne przedmioty.
8. x {. y: Pierwsze xelementy zaczerpnięte z y.
9. x }. y: Pierwsze xegzemplarze spadł zy .
10. x ({. , }.) y: Pierwsze xelementy wzięte z y, potem pierwsze xegzemplarze spadł zy
11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Pierwsze xelementy wzięte z y, a następnie pierwsze xelementy yprzetworzone jak w numerze 7.
12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: To samo z kroplą wciągniętą, aby uratować jedną postać.
13. u/ y: u wstawiony między pozycje z y.
14. < y: y zapakowane .
15. <"0 y: Każda pozycja w y pudełku .
16. i. y: liczby całkowite od 0do y - 1.
17. i.@# y: liczby całkowite od 0do (#y) - 1.
18. (<"0@i.@# , <) y: Całkowite od 0do (#y) - 1siebie ramkach , a następnie yw jednej obudowie. Jest to konieczne, ponieważ tablice w J są jednolite. Pudełko ukrywa kształt zawartości.
19. x u&v y: jak (v x) u (v y).
20. > y: y otwarty , to znaczy bez pudełka.
21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y fraza z liczby 12 zastosowana do jej nieopakowanych argumentów.
22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ yzdanie z numeru 21 wstawione między pozycje z y.
23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) yzwrot z numeru 22 zastosowany do wyniku zdania z numeru 18 lub jednolita permutacja pozycji z y.

Pyth, 25 bajtów

Sprawdź to tutaj.

Kolejna implementacja Fisher-Yates. Jest zasadniczo taki sam, jak @ Sp3000 rozwiązanie python, tylko w pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Dzięki @Jakube za sztuczkę wymiany

<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

Perl, 68 56 44

Podobnie jak wiele innych rozwiązań, wykorzystuje Fisher-Yates algorytm .

Za pomocą komentarza nutki zapisywanych jest 12 znaków przy użyciu $_zamiast $ii wykonywania operacji na indeksach tablicowych.

44:

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

56:

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

To jest mój pierwszy codegolf.

C, 63 61 60 bajtów

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

Tylko prosta implementacja Fischera-Yatesa, która sortuje podaną tablicę na miejscu. Kompiluje i łączy się doskonale z kompilatorem Visual Studio (vs2013, nie testowałem innych wersji) i kompilatorem Intel. Ładnie wyglądająca sygnatura funkcji tos(int array[], int length) . Jestem pod wrażeniem, że pokonałem Pythona i Ruby.

Zakłada się, że srand()jest wywoływany, a rand () jest poprawnie zaimplementowany, ale uważam, że ta reguła pozwala na to:

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

Ładnie sformatowana wersja:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}

Oktawa, 88 77 bajtów

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

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

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

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

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)) =)

Perl, 44

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

Another perl in 44 characters. Example use:

@x=(1..9);f(@x);print@x

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)

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]

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

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.

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)

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.

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

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

Pyth, 27 bytes

Test it here

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

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

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]

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]

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

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.

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

SQF, 91 bytes

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i

Perl, 41 bytes

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

Try it online!