text:
Random Golf of the Day #1: Shuffle an Array
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&]*(?:<(?: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 = '
'+ place++ +'.	'+user.name+'	';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += ''+answer.size+'	';
      else
        row += '	';
    }
    row += '	';
    if (user.completedAll)
      row += ''+user.score+'	';
    else
      row += ''+user.score+'	';
    row += '
';
    $("#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;
}

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

    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.

	User
        #1
        #2
        #3
        #4
        #5
        #6
        #7
        #8
        	Total

{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

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

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

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

Nitpicking: your claim that you cannot sort by random numbers, plus the restriction of fixed size integers are incompatible. You can sort in linear time if the size of the elements is fixed, what you cannot do is sorting by comparisons only.

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

@Geobits The former is fine. I admit, the spec is currently a bit contradictory in that - will fix.

For FUZxxl's J solution and aditsu's CJam solution (and maybe others?), while the algorithms used could have linear runtime, the implementations have quadratic runtime. Due to the languages used, for each digit shuffled, memory operations that take linear time with respect to the size of the input are performed. So unfortunately, I believe that these solutions (and probably any in those languages) do not meet the current requirements.

Can the function take its argument as a global?

@kirbyfan64sos No, that would essentially just be a snippet and not a function.

Why is Adám's solution coming up as 43319 bytes when it's actually 14?

@boboquack Because of how stupidly answers are scanned for scores. I edited the answer to fix it.

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←⎕

... mind. blown.

a language I have to read right to left?? wow!

@Luminous as is often the case with mathematical notation: sin cos ln sqrt x

@ngn when you put it that way that makes my previous comment look laughable. ha.

I object. According to https://mothereff.in/byte-counter, this solution is 51 bytes! Therefore, I suggest that some of the other solutions are shorter.

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

@ngn it's often the case in many languages. f(g(h(x)))

@Luminous You read APL left to right but it's evaluated right to left.

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.

You could have also used rdrand for shits and giggles.

@FUZxxl I totally forgot about it! Too bad it removes the most interesting part about my answer...

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

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.

@Peter I'm not sure I agree. The docs say the range is [0.0 - 1.0]. Whether that can be represented perfectly by a FP number doesn't matter if I can assume it's perfectly uniform over that range.

@PeterTaylor "approximately" only means "up to the issues inherent to PRNGs in general". The range here is [0.0..1.0], otherwise this would have been accessing out of the bounds.

@PeterTaylor unless you read the rule as "you may assume the PRNG generates floats with probability perfectly proportional to their density, but you may not assume that floats are an accurate representation of the real line", which would be unfair to languages that use floating point randomness as their source of perfectly random indexes.

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

@MartinBüttner the cycle length is not the issue here - that is covered by your rule. The coarseness of floats is.

@JanDvorak, actually it doesn't generate floats with probability proportional to their density, or you'd be much more likely to get a number less than 0.5 than a number greater than 0.5. But it's selecting (approximately) uniformly from a finite set of doubles, not an uncountable set of reals.

@PeterTaylor by "proportional to their density" I meant inverse proportionality. As in, 0.6 has its ULP twice as big as 0.3, so it should be twice as likely to occur.

Getting this distribution out of a perfect bit source might be an interesting challenge, actually.

Wow... Almost as short as a python solution.

@TheBestOne It's one byte shorter than the only currently-posted python solution ;)

Not any more! :D

@Sp3000 Your turn ;)

Annoyingly, a C# clone of this requires 5 more characters. (You need a new Random() and it's cheaper to assign Next(i) to x and shuffle the increments around than to call NextDouble().)

Can't you replace s[i]=t)x=i--; with s[x=--i]=t); to reduce 1 byte?

@IsmaelMiguel Not really. x=i-- needs to be executed first in the loop or else it's undefined for the first iteration.

But you have int i=s.length right inside the for loop.

@IsmaelMiguel No, I mean x is undefined. You can try it if you want, but simply moving it breaks the program.

For some reason I find that extremely weird. I have no way to test it now (maybe ideone, but I'm not very familiar with Java). Nor knowledge. But I still find it weird since you have s[x*=Math.random()] and that runs fine.

@IsmaelMiguel x=i-- is run before x*=Math.random() due to the loop structure. If I move it, then it comes after and x is undefined the first time it tries to multiply.

Now I get it. Still find it weird, but I get it. Thanks a lot for the explanation. Dang, I had my hopes high!

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.

That range expression looks pretty cumbersome. Surely it's shorter to count down manually as while i:i-=1;...?

@xnor Yeah it is - thanks for that. I keep forgetting that while tends to be shorter than for for this sort of thing...

Awww... now my Java answer isn't beating this. I was quite happy for a very short while :(

You can save another 2 bytes by making i=len(L) and putting the decrement at the beginning of the while loop.

J, 45 44 characters
This was a tricky one.
<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

Here is an explanation:

# y: The tally of y, that is, the number of elements in y.
?@# y: A random number uniformly distributed over the range from 1 to (#y)-1.
x { y: The item from y at index x.
(<<<x) { y: All items except the item at index x in y.
x , y: y appended to x.
x ({ , <^:3@[ { ]) y: The item at index x in y, then all the other items.
(?@# ({ , <^:3@[ { ]) ]) y A random it from y, then all the other items.
x {. y: The first x items taken from y.
x }. y: The first x items dropped from y.
x ({. , }.) y: The first x items taken from y, then the first x items dropped from y
x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: The first x items taken from y, then the first x items from y processed as in number 7.
x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: The same thing with the drop pulled in to save one character.
u/ y: u inserted  between the items of y.
< y: y boxed.
<"0 y: Each item of y boxed.
i. y: integers from 0 to y - 1.
i.@# y: integers from 0 to (#y) - 1.
(<"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.
x u&v y: like (v x) u (v y).
> y: y opened, that is, without its box.
x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y the phrase from number 12 applied to its unboxed arguments.
({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y the phrase from number 21 inserted  between items of y.
({. , ?@#@}. ({ , <^: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.

I just can't distinguish all the parentheses. And that triple boxing <@<@<@[ is also a mystery... Waiting for explanation. :)

Once this gets explained, I might be much more likely to upvote this answer ;-)

@randomra Here you go.

@JanDvorak Is the explanation satisfying?

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.

Is this really O(n)? If the lists are arrays and not linked lists some of these operations take O(n^2) total time (O(n) used n times) like step 4 and 10. (I could easily be wrong just asking.)

@randomra That's my fear, too. J has optimized code for many common things though, so it might be O(n), it might also be O(n²). I'm not really sure.

@FUZxxl I believe the fear is correct. I made a comment to the main post stating that your solution and aditsu's CJam solution both unfortunately get knocked down to O(n²) due to list operations that actually take O(n), which I confirmed with timed tests. Waiting for OP to comment on the matter.

@Runer112 You did actually time this? In that case, I'm afraid this is indeed invalid.

@MartinBüttner Yes, I timed it. I expressed this concern earlier as a comment to the original post, which also mentions aditsu's CJam solution as having a similar problem (which I also timed).

@Runer112 Yes, I left a comment regarding this on aditsu's answer. Thanks for pointing it out.

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

You can save two bytes by combining those two list assignments:  XXQN@QKKJ instead of  XQN@QK XQKJ.

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

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.

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..@_}.

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

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

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

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

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.

@FUZxxl I believe an xor swap causes problems if i==m.

@Geobits indeed. I missed that possibility.

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.

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.

I copied into VS2013 and turned off warnings...still there are 12 errors. No variable declarations and variables before '{' etc.

its probably compiling it as c++ code, which is stricter than c. compile it from a VS developer command prompt using cl. also be sure the file is .c, not .cpp

You can remove 1 byte by transforming for(;m;a,b,c); into for(;m;c)a,b;

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]

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

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()?

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

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)

I think, it's unfair for function to stop by exception in a normal case, is it?

@Qwertiy To each his own... You think it's unfair, I think it's great.

Does the x need to be wrapped in parentheses?

Instead of shuff interface, you can use predefined java.util.function.Consumer<int[]> functional interface.

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

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)

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

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)

You can use Do here. It's shorter than While.

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

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

You're missing the End.

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.

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

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.

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

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.

What's _n in this?

_n is the number of the current observation.

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]

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.

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.

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

So this code follows the spirit of the question, but not the "letter", due to internal language implementation issues.

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

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.

Pyth, 27 bytes
Test it here
FkQJOhlYaY?@YtJJkIJ XYtJk;Y

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

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

@MartinBüttner, removed it :)

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]

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

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

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

Try it online!

Jolf, 46 bytes
Invalid, since language postdates question. Is otherwise a perfectly valid answer. Try it ici!
v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K

Explanation
v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K
                                              implicit: K = input array
v'n                                           set n to
   lK                                           the length of K
     W«n)                                     while(--n){
         v'H                                    set H to
            C     t                               the integer part of
             *mr                                  Math.random() times
                hn                                  n+1
                   v'S                          set S to
                      .Kn                         the nth member of K
                         $K[n]=K[H];K[H]=S$     eval as javascript (perform swap)
                                           }  }
                                            K K
                                              implicit: print K

This runs in O(n) time, I believe, as n is strictly decreasing.
I used this as the basis for the code

Julia 0.6, 56 bytes
!a=for i=length(a):-1:1;j=rand(1:i);a[[i,j]]=a[[j,i]]end

Try it online!
Fisher-Yates.
a[[i,j]]=a[[j,i]] is slightly shorter than a[i],a[j]=a[j],a[i].
rand(1:i) samples from the range 1:i.

SmileBASIC, 56 bytes
Fisher-Yates algorithm of course.
DEF S A
FOR I=1-LEN(A)TO-1SWAP A[-I],A[RND(1-I)]NEXT
END

Downwards FOR loops are expensive (STEP -1), so instead you can just negate the start/end values, which only adds 1 extra character. This is the code if FOR implicitly went backwards when the end value is lower than the start:
DEF S A
FOR I=LEN(A)-1TO 1SWAP A[I],A[RND(I+1)]NEXT '1 character less
END

PowerShell, 39 27 bytes
-4 bytes thanks to @mazzy
$args-split','|sort{random}

Accepts input as commandline arguments, and outputs as an array.

Welcome! You can use random only. https://codegolf.stackexchange.com/a/778/80745

VBA/Basic, 96
Someday I will find a good challenge for vba or basic, but not today
Fisher-Yates
Sub s(o(), n)
For i = 0 To n
r = Int(Rnd() * (n + 1))
x = o(r)
o(r) = o(i)
o(i) = x
Next
End Sub

This is biased. It's what Will it Shuffle calls "swap (i <-> random)". You can turn it into actual Fisher-Yates by replacing n + 1 with i +  though.

ty, but damm then I need to add 'step -1'

Sorry, I don't know what you mean.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Array combinatoric comparison
Introduction
You may remember sudoku, where there can only be one of each number in each row, column and block of nine.
The general idea is that if the array contains but one element, you can submit that as a deterministic solution. If there are already filtered arrays (by rows, columns and 3×3 blocks) the remainder can still be deterministic.
Where

a=[1,2];
b=[1,3];
c=[2,3];
d=[1,2,3,4]

d should be reduced to [4] as it apparently cannot be anything else.
Challenge
Provide a sniplet that compares n arrays.
For every X, if only X numbers appear at least once in a set of X arrays, then all those X numbers should be removed from each array not in the set.
The elements are integer numbers ranging [1, n].
Winning criterion
Lowest character count.
"I'm too young to die" version
9 arrays at most, 9 elements at most.
Test Cases

[1,2]; [2,3]; [1,3]; [1,2,3,4]
  [1,2,3]; [2,3,4]; [1,5,6]; [2,3]; [1,4]; [1,2,3,4,6]
Test outputs
[1,2]; [2,3]; [1,3]; [4]
  [1,2,3]; [2,3,4]; [5]; [2,3]; [1,4]; [6]

"the numerosity of elements of 1 to n arrays' union equals to the numerosity of arrays". Does this mean that there are n arrays in the input, and their union is exactly [1,2,...,n]? Also, I don't really understand the challenge. What should the output be in your example?

The output should be in the above case [1,2]; [1,3]; [2,3] and [4].
The numerosity of arrays is not necessarily the same as the numerosity of their union's elements, the array reduction is a more general operation.

What is this about ""I'm too young to die" version"? The formatting suggests that it's part of the winning criterion, but that makes no sense. I think you probably want cascading deductions, but the question doesn't mention them: it should (either to say that they're required or that they aren't).

It would also be helpful to state whether the elements of the arrays are always integers, and if so whether they always fall within a given range. That could allow some answers to save bytes.

The "I'm too young to die" version is for lazy bums who don't want to test what they've written. Larger set combinatorics are a nasty thing. Anyways, the tests (sorry for the edit) fall within the bottleneck of 9 elements, 9 sets.

If the intention is to have two winners then I'm afraid that's not possible. This site's software only allows one accepted answer.

I can't make sense of what the task is here. Could someone who does please explain?

@feersum The 1 in b should be removed according to your interpretation.

Pyth: 37 29 28 bytes
um?d|-lHl{sHsmg{kdH-dsHGtyQQ

Input is a list of lists like [[1,2], [2,3], [1,3], [1,2,3,4]]. Try it online: Pyth Compiler/Executor
Explanation:
um?d|-lHl{sHsmg{kdH-dsHGtyQQ
u                          Q  G = input array
u                       tyQQ  For each H in powerset(input):
 m                     G        G = [            ...        for d in G]
  ?d               -dsH             [d if ... else d-sum(H) for d in G]
     -lHl{sH                        len(H)-len(set(sum(H)))!=0
    |                                     or
            smg{kdH                 sum(d is subset of k for k in H)>0

I love this. Clear, concise.

C# - 231 characters
static int[][] P(int[][]a){var m=a.GetUpperBound(0)+1;var j=0;for(var i=0;i<m;i++){var u=new List<int>();for(j=0;j<=i;j++)u=u.Union(a[j]).ToList();if(u.Count()==m)for(j=0;j<m;j++)if(i!=j)a[i]=a[i].Except(a[j]).ToArray();}return a;}

Ungolfed and harness
using System.Collections.Generic;
using System.Linq;

namespace ArrayCombCompar
{
    class Program
    {
        static void Main(string[] args)
        {
            var testArray1 = new int[][] {
                new int[] {1,2},
                new int[] {2,3},
                new int[] {1,3},
                new int[] {1,2,3,4}
            };
            var testArray2 = new int[][] {
                new int[] {1,2,3},
                new int[] {2,3,4},
                new int[] {1,5,6},
                new int[] {2,3},
                new int[] {1,4},
                new int[] {1,2,3,4,6}
            };
            var result1 = P(testArray1);
            var result2 = P(testArray2);
        } // Put breakpoint here to see results

        static int[][] P(int[][]a)
        {
            var m = a.GetUpperBound(0) + 1;
            var j = 0;
            for (var i = 0; i < m; i++)
            {
                var u = new List<int>();
                for (j = 0; j <= i; j++)
                    u = u.Union(a[j]).ToList();
                if (u.Count() == m)
                    for (j = 0; j < m; j++)
                        if (i != j) a[i] = a[i].Except(a[j]).ToArray();
            }
            return a;
        }

     }
}

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Compute the inverse XOR
Let f be the function that maps a bitfield ({0 1}) of size n+1 to bitfield of size n by applying XOR to the ith and i+1th bit and writing the result in the new bitfield.
Example: f("0101") = "111"
Informal calculation:
0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1

Let f_inverse be the inverse function of f. Since the inverse is not unique, f_inverse returns one valid solution.
Input: bitfield as string (i.e. "0101111101011") and a given natural number k
Output: bitfield as string, so that the string contains the result if f_inverse is applied k times to the input bitfield. (i.e. f_inverse(f_inverse(f_inverse(input))) )
Winning criteria: fewest Characters
Bonus:
-25 Characters if f_inverse is not applied recursively/iteratively, instead the output string is directly calculated
Testscript:
a = "011001"
k = 3

def f(a):
    k = len(a)
    r = ""
    for i in xrange(k-1):
        r += str(int(a[i]) ^ int(a[i+1]))
    return r

def iterate_f(a, k):
    print "Input ", a
    for i in xrange(k):
        a = f(a)
        print "Step " + str(i+1), a

iterate_f(a, k)

You can paste it for example here and then try it.

Can you give some test cases to verify.

Could you please stop calling them {0-1}-Bitfields? Also I don't understand the definition of f, where does i come from? What is the second argument of XOR? how do we get 111 from 0101?

What is a better name? i denotes the index

Just a "bitfield" would do. What is the /value/ of i? "0 XOR 1" = 1 "1 XOR 0" = 1 "0 XOR 1" = 1 doesn't explain anything: I know how XOR works, but what exactly are we XORing and where are we storing the result?

It maps a binary string to a binary string by shifting one copy right, performing bitwise XOR, and discarding the leading bit.

I think he means: f([a,b,c,d]) = [a^b, b^c, c^d]. And he wants the inverse of that function, i.e f'([x,y,z]) = [a,b,c,d] such that a^b=x, b^c=y, c^d=z.

Related

Do you want us to give the result of every step or just the final result? Also, do we need a complete program or is it enough to just provide a function that can be called with the two input values?

@DavidYoung I think the challenge explicitly asks only for the final result. As for your second question there are accepted defaults (see the bullet-points after "If 1. and 7. are not specified..."). So yes, you may define a function instead of writing a full program.

Pyth, 33 30 - 25 = 5 bytes
Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ

Run it by input from stdin like (online interpreter: https://pyth.herokuapp.com/):
111
3

and the result will be written to stdout.
This is a direct translation of:
Python 2, 127 118 79 - 25 = 54 bytes
def i(s,k):
 l=int(s,8);t=len(s)+k
 while k<1<<t:l^=l/8;k+=1
 print'%0*o'%(t,l)

Call it like i("111", 3), and the result will be written to stdout.
Note that we expect k not being too large, since for code-golfing purpose the inner loop will run for O(2k) times.

I think we usually call this operation "xorshift" or something. If we express the input as big-endian integers, then the function f is simply:

f(x) = x ⊕ (x ≫ 1)

If we apply f twice we will get:

f2(x) = x ⊕ (x ≫ 2)

However applying 3 times will have a different pattern:

f3(x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)

Applying 4 times get back to the basic form:

f4(x) = x ⊕ (x ≫ 4)

And so on:

f2k(x) = x ⊕ (x ≫ 2k)

Note that if we choose a big-enough 2k, then (x ≫ 2k) = 0, meaning f2k(x) = x, and the inverse is trivially the identity function!
So the strategy for finding f-k(x) without calling f-1(x) at all is:

Find K such that:

K ≥ k
K > log2 x
K is a power of 2

Express f-k(x) = f-K + (K-k)(x) = f-K(fK-k(x)) = fK-k(x)
Thus, the result is f called K-k times
25 chars profit :p

Update 1: Used octal representation instead of binary so that we could use % formatting to save lots of bytes.
Update 2: Exploit the periodic structure of f. Retired the iterative version since the non-iterative one is shorter even without the -25 bytes bonus.
Update 3: Reduced 3 bytes from Pyth, thanks isaacg!

As described in the tips: http://codegolf.stackexchange.com/a/45280/20080 you can replace the for loop and assignments with a reduce, like this: Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ

CJam, 15 14 bytes
l~{0\{1$^}/]}*

Takes input like
"111" 3

Test it here.
Explanation
l~{0\{1$^}/]}*
l~             "Read and evaluate input.";
  {         }* "Repeat k times.";
   0\          "Push a 0 and swap it with the string/array.";
     {   }/    "For each element in the string/array.";
      1$       "Copy the previous element.";
        ^      "XOR.";
           ]   "Wrap everything in a string/array again.";

The result is automatically printed at the end of the program.
I say "string/array", because I start out with a string (which is just an array of characters), but I keep taking XORs between them and between numbers as well. Character Character ^ gives an integer (based on the XOR of the code points), Character Integer ^ and Integer Character ^ give a character (based on the XOR of the number with the code point - interpreted as a code point). And Integer Integer ^ of course just gives an integer.
So the types are flying all over the place, but luckily, whenever I have an integer it's either 0 or 1 and whenever I have a character it's either '0 and '1 and result is always the desired one (in either type). Since strings are just arrays of characters, mixing characters with numbers is not a problem at all. And at the end, when everything is printed, characters get no special delimiters, so the output is not affected by which bit is represented as a number or a character.

Your excellent explanation of the character / number type behavior in CJam let me shave a byte off my solution, reaching 25 − 25 = 0 bytes.  Thanks, and +1!

That type behavior is horrifying (+1).

J,  17 chars
Always using 0 as the leading digit.
   (~:/\@]^:[,~[$0:)

   3 (~:/\@]^:[,~[$0:) 1 1 1
0 0 0 1 0 0

Starting from top row's 128 1's state (left) and a random state (right), showing the last 128 digits through the first 129 iteration.
   viewmat (~:/\)^:(<129) 128$1               viewmat (~:/\)^:(<129) ?128$2

APL 11
((0,≠\)⍣⎕)⎕

Explanation:
≠\  compare increasing number of elements (1 1 1 ->1 0 1)
0,    add a starting zero
()⍣⎕  repeat the function in parenthesis ⎕ times, ⎕ is the second argument
()⎕   apply all to ⎕, that is first argument

Try on tryapl.org

Couldn't run it on tryapl (how you give the inputs?) but ≠\  wouldn't work instead of 2|+\ ?

the ⎕'s are the inputs, if you use the same expression I wrote, the program should ask you for the numbers you want, first the binary vector, then a second time for the number of iterations. I used a and b in the link to tryapl, so it's executed without askin things. Also thanks for the ≠!!

If I copy ((0,≠\)⍣⎕)⎕ I get invalid token. Tryapl can't handle inputs?

Hmmmm... you're right, it's happening the same to me. I'm using Dyalog APL and then tryapl just to post here, so I never noticed, sorry about that.

CJam, 25 − 25 = 0 bytes
q~1,*_@{[\{1$^}/_](;)\}/;

This is just a straight CJam port of the GolfScript answer below, since, after reading Martin Büttner's answer, I realized that I could save one byte due to CJam's handling of integer and character types.  (Basically, CJam doesn't need the 1& used to force ASCII characters into bits in the GolfScript code, but does require a prepended q to read the input.)  I would usually consider such a trivial port a cheap trick, but achieving a zero score made it IMO worthwhile.
In any case, this program works exactly like the original GolfScript program below, so please refer to its description and usage instructions.  As usual, you can test the CJam version using this online interpreter.

GolfScript, 26 − 25 = 1 byte
~1,*.@{[1&\{1$^}/.](;)\}/;

This solution iterates over the input string only once, so I believe it qualifies for the −25 byte bonus.  It works by internally maintaining a k-element array that stores the current bit of each of the k pre-iterates.
Input should be given via stdin, in the format "1111111" 3, i.e. as a quoted string of 0 and 1 characters, followed by the number k.  Output will be to stdout, as a bitstring without quotes.
Test this code online. (If the program times out, try re-running it; the Web GolfScript server is notorious for random timeouts.)

Here's an expanded version of this program, with comments:
~             # eval the input, leaving a string and the number k on the stack

1,*           # turn the number k into an array of k zeros ("the state array")
.             # make a copy of the array; it will be left on the stack, making up the
              # first k bits of the output (which are always zeros)

@             # move the input string to the top of the stack, to be iterated over
{
  [           # place a start-of-array marker on the stack, for later use
  1&          # zero out all but the lowest bit of this input byte
  \           # move the state array to the top of the stack, to be iterated over

  { 1$^ } /   # iterate over each element of the state array, XORing each
              # element with the previous value on the stack, and leave
              # the results on the stack

  .           # duplicate the last value on the stack (which is the output bit we want)
  ]           # collect all values put on the stack since the last [ into an array
  (;          # remove the first element of the array (the input bit)
  )           # pop the last element (the duplicated output bit) off the array
  \           # move the popped bit below the new state array on the stack
}
/             # iterate the preceding code block over the bytes in the input string

;             # discard the state array, leaving just the output bits on the stack

Basically, like most of the iterative solutions, this code can be understood as applying the recurrence

bi,j := bi,(j−1) ⊕ b(i−1),(j−1),
where b0,j is the j-th input bit (for j ≥ 1), bk,j is the j-th output bit, and bi,0 = 0 by assumption.  The difference is that, whereas the iterative solutions, in effect, compute the recurrence "row by row" (i.e. first b1,j for all j, then b2,j, etc.), this solution instead computes it "column by column" (or, more accurately, "diagonal by diagonal"), first computing bi,i for 1 ≤ i ≤ k, then bi,i+1, then bi,i+2, etc.
One (theoretical) advantage of this approach is that, in principle, this method can process an arbitrarily long input string using only O(k) storage.  Of course, the GolfScript interpreter automatically reads all the input into memory before running the program anyway, mostly negating this advantage.

Python, 94 78
Will be executed at least once and thus gives the same result for n=0 and n=1
def f(x,n):
 c='0'
 for i in x:c+='10'[i==c[-1]]
 return f(c,n-1)if n>1 else c

Old version which converts the string to a numeric array and "integrates" modulo 2
from numpy import*
g=lambda x,n:g(''.join(map(str,cumsum(map(int,'0'+x))%2)),n-1)if n>0 else x

Python 2, 68
g=lambda l,n,s=0:n and g(`s`+(l and g(l[1:],1,s^(l>='1'))),n-1)or l

A totally recusive solution. It's easier to understand if broken into two functions
f=lambda l,s=0:`s`+(l and f(l[1:],s^(l>='1')))
g=lambda l,n:n and g(f(l),n-1)or l

where f computes successive differences and g composes f with itself n times.
The function f compute the cumulative XOR-sums of l, which is the inverse operation to successive XOR-differences. Since input is given as a string, we need to extract int(l[0]), but do so shorter with the string comparison l>='1'.

Python 2, 69
An iterative solution using an exec loop turned out 1 char longer.
l,n=input()
exec"r=l;l='0'\nfor x in r:l+='10'[l[-1]==x]\n"*n
print l

Maybe there's a shorter way to deal with the string. If we could have input/outputs be lists of numbers, it would save 5 chars
l,n=input()
exec"r=l;l=[0]\nfor x in r:l+=[l[-1]^x]\n"*n
print l

C# - 178 161 115 characters
static string I(string a, int k){var s = "0";foreach(var c in a)s+=c==s[s.Length-1]?'0':'1';return k<2?s:I(s,--k);}

Ungolfed with harness
using System;
using System.Text;

namespace InverseXOR
{
    class Program
    {
        static string I(string a, int k)
        {
            var s = "0";
            foreach (var c in a)
                s += c == s[s.Length - 1] ? '0' : '1';
            return k < 2 ? s : I(s, --k);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(I(args[0], Convert.ToInt32(args[1])));
        }
    }
}

Perl 5, 34
#!perl -p
s/ .*//;eval's/^|./$%^=$&/eg;'x$&

Parameters given on the standard input separated by a space.
$ perl a.pl  <<<"1101 20"
101111011011011011010110

Javascript ES6, 47 chars
f=(s,k)=>k?f(0+s.replace(s=/./g,x=>s^=x),--k):s

By the way, there is no side effects :)

You need to accept a k parameter for the number of iterations.  (The -25 bonus is for computing the result of the iterations without actually performing the iterations.)

I should've read specification carefully (facepalm)

CJam, 20 bytes
q~{:~0\{1$!_!?}/]s}*

Input is like "111" 3
Try it online here

"011001" is the result from your code for your input but its not correct if you check

@user3613886 Sorry, copied older version. Fixed now


text:
String Equivalence: Counting Substrings
Background
Two strings s and t are called k-Abelian equivalent (shortened to k-equivalent in the following) for a positive integer k if the following conditions hold:

The length-k-1 prefixes of s and t are equal.
The length-k-1 suffixes of s and t are equal.
The strings s and t have the same multisets of length-k contiguous substrings.
In other words, every string of length k occurs an equal number of times in s and t.
Overlapping occurrences are counted as distinct.

Note that k-equivalent strings are always k-1-equivalent if k > 1, and the third condition implies that s and t have the same length.
It is also known, and possibly useful, that the three conditions above are equivalent to the following one:

Every non-empty string of length k or k-1 occurs an equal number of times in s and t.

An Example
For example, consider the strings s = "abbaaabb" and t = "aabbaabb".
Because the strings have the same number of each character, 4 of a and 4 of b, they are 1-equivalent.
Consider then 2-equivalence.
Their first and last characters are the same (both strings begin with a and end with b), so the first two conditions are satisfied.
The length-2 substrings of s are aa (occurs twice), ab (twice), ba (once), and bb (twice), and those of t are exactly the same.
This means that the strings are 2-equivalent.
However, since their second letters are different, the strings are not 3-equivalent.
Input
Two alphanumeric strings s and t of the same length n > 0.
Output
The largest integer k between 1 and n (inclusive) such that s and t are k-equivalent.
If no such k exists, the output is 0.
In the above example, the correct output would be 2.
Rules
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Crashing on malformed input is perfectly fine.
Test Cases
"abc" "def" -> 0
"abbaabbb" "aabbbaab" -> 0
"abbaaabb" "aabbbaab" -> 2
"abbaaabb" "aabbaabb" -> 2
"aaabbaabb" "aabbaaabb" -> 3
"aaabbaabb" "aaabbaabb" -> 9
"abbabaabbaababbabaababbaabbabaab" "abbabaabbaababbaabbabaababbabaab" -> 9
"yzxyxx" "yxyzxx" -> 2
"xxxxxyxxxx" "xxxxyxxxxx" -> 5

Why is the solution for the third case "abbaaabb" "aabbbaab" = 1? The prefixes a, a and the suffixes b, b are the same, and the substrings aa, ab, bb  appear each twice, and the substring ba appears once in each string.

@Jakube prefix of N length

@Optimizer It says: "The length-k-1 prefixes of s and t are equal."

@Jakube Oh right

@Jakube Good find. There may be something wrong with my reference implementation, or it may be my mistake. I'll change it to a 2 for now, and investigate this later.

@Zgarb The are also some other mistakes: the correct solutions should be: 0,0,2,2,3,9,9,2,5.

@Zgarb Corrected it myself.

Pyth: 26 22 bytes
lfq_TTCmmSm<>dbhkldldQ

Input are two strings like "abc","def". Try it online: Pyth Compiler/Executor
Explanation:
Quite some complicated code. But I'll start easy.
First we want to create all substrings of length k of the string d.
Sm<>dbhkld
 m      ld      apply a function ... to all elements b
                in the list [0, 1, 2, ..., len(d)-1]
   >db              take the string d starting from the position b
  <   hk            but only hk = k + 1 characters
S               Sort the resulting list.

For the string "acbde" and k = 3 this results in ['abc', 'bde', 'cbd', 'de', 'e']. Notice, that 'de' and 'e' are part of this list. This will be quite important in a bit.
I want the substrings for each k, one map again.
mSm<>dbhkldld
m          ld   apply a function (create all substrings of lenght k) to
                all elements k in the list [0, 1, 2, ..., len(d)-1]

For the string "acbd" this results in [['a', 'b', 'c', 'd'], ['ac', 'bd', 'cb', 'd'], ['acb', 'bd', 'cbd', 'd'], ['acbd', 'bd', 'cbd', 'd']].
I want this for both strings, another map.
mmSm<>dbhkldldQ
m             Q   apply the function (see above) for all d in input()

[[['a', 'b', 'c'], ['ab', 'bc', 'c'], ['abc', 'bc', 'c']], [['d', 'e', 'f'], ['de', 'ef', 'f'], ['def', 'ef', 'f']]] for the input "abc","def", and after a
zip C, this looks [(['a', 'b', 'c'], ['d', 'e', 'f']), (['ab', 'bc', 'c'], ['de', 'ef', 'f']), (['abc', 'bc', 'c'], ['def', 'ef', 'f'])].
Now comes the exciting part: We are of course only interest in the ks, where the substrings of both words are the same.
lfq_TTCmmSm<>dbhkldldQ
 f                         I filter the list for elements T, where
  q_TT                         reversed(T) == T
                           (basically T[0] == T[1])
l                          print the lenght of the resulting list.
                           (= the number of times, where the substrings of length k
                              of string 1 are equal to the substrings of
                              length k of string 2)

Since we also have the suffixes of length < k in Ts, this also checks, if the suffixes are equal.
The only thing, which I don't check is, if the prefixes are equal. But as it turns out, this isn't necessary. Lemma 2.3 (4<=>5) of the linked paper says: If the substrings of length k are the same, than pref_{k-1}(string 1) = pref_{k-1}(string 2) is equivalent to suff_{k-1}(string 1) = suff_{k-1}(string 2). Since the suffixes are equal, the prefixes are also equal.

the 'ab' in g"abbab"3 is from the last two characters, not the prefix. So no, you are not correctly following the spec as you do not check for k-1 length prefix at all

@Optimizer Lemma 2.3 in the linked paper does the job. I'll add some more explanation.

Are you saying that checking for k-1 length prefix is not at all required ?

@Optimizer Exactly

@Zgarb Thanks for accepting my answer. Too sad, this question didn't get more recognition. I found this was one of the best challenges in a while, and am quite proud of my solution.

CJam, 51 49 47 41 34 bytes
WqN/:Q0=,,{Qf{_,,\f>\)f<$}~=},+W=)

Just to get something started. This can surely be golfed a lot. Looking at a different algorithm too.
Input goes as the two strings without quotes on separate lines.
Example:
aaabbaabb
aabbaaabb

Output:
3

Try it online here


text:
Random Golf of the Day #2: Numbers from a Normal Distribution
About the Series
First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.
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 2: Numbers from a Normal Distribution
I can't believe this hasn't been done yet! You're to generate random numbers, drawing from a normal distribution. Some rules (the majority of them are probably automatically covered by most submission, but some of them are in place to ensure consistency of results between vastly different languages):

You should take two non-negative integers as input: a seed S and the amount N of numbers to return. The output should be a list of N floating point numbers, drawn from a normal distribution with mean 0 and variance 1. Whenever your submission is given the same seed S it should produce the same number. In particular, if it is called once with (S, N1) and once with (S, N2), the first min(N1, N2) entries of the two outputs should be identical. In addition, at least 216 different values of S should produce different sequences.
You may use any built-in random number generator that is documented to draw numbers from an (approximately) uniform distribution, provided you can pass S on to it and it supports at least 216 different seeds. If you do, the RNG should be able to return at least 220 different values for any given number you request from it.
If your available uniform RNG has a smaller range, is not seedable, or supports too few seeds, you must either first build a uniform RNG with a sufficiently large range on top of the built-in one or you must implement your own suitable RNG using the seed. This page may be helpful for that.
If you don't implement an established algorithm for generating normal distributions, please include a proof of correctness. In either case, the algorithm you choose must yield a theoretically exact normal distribution (barring limitations of the underlying PRNG or limited-precision data types).
Your implementation should use and return either floating-point numbers (at least 32 bits wide) or fixed-point numbers (at least 24 bits wide) and all arithmetic operations should make use of the full width of the chosen type.
You must not use any built-in functions directly related to normal distribution or Gaussian integrals, like the Error function or its inverse.

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).
S and N will be non-negative integers, each less than 220. Output may be in any convenient, unambiguous list or string format.
This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.
Leaderboard
The first post of the series generates a leaderboard.
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.)

Wait, are we allowed to use non-integer-range RNG's?

P.S. 2 existing answers seem to use [0, 1) floating point RNG's, is this allowed?

@mniip Yes, floating-point RNG's are allowed, provided they are uniform, seedable and able to return the required number of distinct floats.

R, 68 bytes
function(S,N){set.seed(S);sqrt(-2*log(runif(N)))*cos(2*pi*runif(N))}

This uses the runif() function, which generates random deviates from a uniform distribution. The seed for the random number generation is specified using set.seed(), which by default uses the Mersenne-Twister algorithm with a period of 2^19937-1.
The result is an R vector of length N containing the computed standard normal deviates.
This uses the Box-Muller method: For two independent uniform random variables U and V,

If that's valid syntax in R, you can leave out the f= (the function doesn't necessarily need to be named, if unnamed functions are a thing in your language).

@MartinBüttner: I appreciate the suggestion but to my knowledge R wouldn't know what to do with an unnamed function.

I always get an error message Error: unexpected '}' in "f=fu... besides, are you sure you get the same first numbers if you call f(0,1) and f(0,2)?

Dyalog APL, 33 bytes
{(.5*⍨¯2×⍟?0)×1○○2×?0}¨⍳⎕⊣⎕rl←1+⎕
Box-Muller:
⎕         ⍝ evaluated input
⎕rl←1+⎕   ⍝ set APL's random seed to 1+⎕ (S)
          ⍝   add 1 because ⎕rl←0 has special meaning: sets the seed randomly
{ }¨⍳N    ⍝ do the thing in braces N times
?0        ⍝ random number 0≤x<1
1○○2×A    ⍝ sin(2πA)
.5*⍨¯2×⍟B ⍝ sqrt(-2lnB)

I'm pretty sure this can't beaten by any other language.

This doesn't meet this rule:  "In particular, if it is called once with (S, N1) and once with (S, N2), the first min(N1, N2) entries of the two outputs should be identical."

@marinus Thanks, fixed.  I also changed ⎕rl to be S+1 because ⎕rl←0 has special meaning.

You probably don't actually need the +1, all it says is that you need to support at least 2^16 different values. So working correctly in the range [1..2^16] should be OK.

S=0 would make the computation not repeatable, which violates the rule you quoted above.

Dyalog APL, 42 34
{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}

This is a function that takes S as its left argument and N as its right argument.
     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}10
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616
     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}20
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616 0.642585109 ¯0.2450019151 ¯0.415034463 0.03481768503 ¯0.4621212815 ¯0.760925979
      0.2592913013 1.884867889 ¯0.9621252731 0.3062560446

It's an implementation of the Box-Muller transform, using Dyalog APL's built-in random operator ?, which by default is a Mersenne twister that returns 64-bit values, which should be enough.
Explanation:

⎕RL←⍺: set the random seed to ⍺.
?⍵2⍴0: generate ⍵ pairs of random numbers between 0 and 1.
{...}/: apply the following function to each pair:

(.5*⍨¯2×⍟⍺)×1○⍵×○2: calculate the Z0 value (sqrt(-2 ln ⍺)×cos(2π⍵)).

In v14.0 ?0 returns a floating point number between 0 and 1.

Java, 164 161 bytes
class B extends java.util.Random{B(int s,int n){super(s);for(;n-->0;System.out.println(Math.sqrt(-2*Math.log(nextDouble()))*Math.cos(2*Math.PI*nextDouble())));}}

This takes in input via function and output via stdout. It uses the Box-Muller method.

s=0;s++<n; -> ;n-->0; ?

@Geobits Looks like a lambda :D

Perl, 67
sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}

Box-Muller as in other entries. f takes parameters in order S, N.
Use:
$ perl -le 'sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}print for f(5,3)'
-1.59212831801942
0.432167710756345
-0.533673305924252

Commodore 64 Basic, 76 70 63 bytes
1INPUTS,N:S=R/(-S):F┌I=1TON:?S●(-2*LOG(R/(1)))*S╮(2*π*R/(1)):N─

Since the PETSCII character set contains some symbols not present in Unicode, I've made substitutions: / = SHIFT+N, ┌ = SHIFT+O, ● = SHIFT+Q, ╮ = SHIFT+I, ─ = SHIFT+E
This implements the standard Box-Muller transform to generate the numbers; I picked the sin(x) half of the transform because Commodore 64 Basic has a two-character shortcut for sin(), but not for cos().
Although the manual states otherwise, the value of the argument to RND does matter: if a negative number is passed, the random number generator is not merely re-seeded, it is re-seeded with that number.  This makes seeding much simpler: instead of needing to POKE five memory locations, I merely need to make a do-nothing call to RND, which reduces the code from two lines/121 bytes to 1 line/76 bytes.
Edit: Golfed six bytes off by realizing I could combine the two INPUT statements, and that the space after TO was optional.
Edit: Golfed another seven off: Commodore Basic does, in fact, have Pi as a built-in constant, and it's even typeable on a modern keyboard (SHIFT+PgDn, in case you were wondering).

80386 machine code, 72 bytes
Hexdump of the code:
60 8b 7c 24 24 33 ed 8d 75 fb 8d 46 79 f7 e2 f7
f6 8b da b3 7f 0f cb d1 eb 89 1f d9 07 d9 e8 de
e9 33 ee 75 e5 d9 ed d9 c9 d9 f1 dc c0 d9 e0 d9
fa d9 c9 d9 eb de c9 dc c0 d9 ff de c9 d9 1f 83
c7 04 e2 c6 61 c2 04 00

Here is the source code (can be compiled by Visual Studio):
__declspec(naked) void __fastcall doit(int count, unsigned seed, float* output)
{
    _asm {
                                // ecx = count
                                // edx = seed
        // save registers
        pushad;
        mov edi, [esp + 0x24];  // edi = pointer to output
        xor ebp, ebp;           // ebp = 0
        lea esi, [ebp - 5];     // esi = 4294967291 (a prime number)

    myloop:
        // Calculate the next random number
        lea eax, [esi + 121];   // eax = 116
        mul edx;
        div esi;
        mov ebx, edx;

        // Convert it to a float in the range 1...2
        mov bl, 0x7f;
        bswap ebx;
        shr ebx, 1;

        // Convert to range 0...1 and push onto the FPU stack
        mov [edi], ebx;
        fld dword ptr [edi];
        fld1;
        fsubp st(1), st;

        // Make 2 such random numbers
        xor ebp, esi;
        jnz myloop;

        // Calculate sqrt(-2*ln(x))
        fldln2;
        fxch;
        fyl2x;
        fadd st, st(0);
        fchs;
        fsqrt;

        // Calculate cos(2*pi*y)
        fxch st(1);
        fldpi;
        fmul;
        fadd st, st(0);
        fcos;

        // Calculate and write output
        fmulp st(1), st;
        fstp dword ptr [edi];
        add edi, 4;

        // Repeat
        loop myloop

        // Return
        popad;
        ret 4;
    }
}

Here I use a a Lehmer random number generator. It uses the following algorithm:
x(k+1) = 116 * x(k) mod 4294967291

Here 4294967291 is a big (2^32-5) prime number, and 116 is a small (less than 128; see below) number that is its primitive root. I chose a primitive root that has
a more-or-less random distribution of zeros and ones in binary representation (01110100). This RNG has the maximum possible period of 4294967290, if the seed is nonzero.

The relatively small numbers I used here (116 and 4294967291, which can be represented also as -5) let me take advantage of the lea instruction encoding:
8d 46 79     lea eax, [esi+121]

It is assembled to 3 bytes if the numbers can fit into 1 byte.

The multiplication and division use edx and eax as their working registers, which is why I made seed the second parameter to the function (fastcall calling convention uses edx to pass the second parameter). In addition, the first parameter is passed in ecx, which is a good place to hold a counter: a loop can be organized in 1 instruction!
e2 c6        loop myloop

To convert an integer into a floating-point number, I exploited the representation of single-precision floating-point numbers: if I set the high 9 bits (exponent) to the bit pattern 001111111, and leave the 23 low bits random, I'll get a random number in the range 1...2. I took the idea from here. To set the high 9 bits, I used some bit-fiddling on ebx:
mov ebx, edx;    xxxxxxxx|yyyyyyyy|zzzzzzzz|aaaaaaaa
mov bl, 0x7f;    xxxxxxxx|yyyyyyyy|zzzzzzzz|01111111
bswap ebx;       01111111|zzzzzzzz|yyyyyyyy|xxxxxxxx
shr ebx, 1;      00111111|1zzzzzzz|zyyyyyyy|yxxxxxxx

To generate two random numbers, I used a nested loop of 2 iterations. I organized it with xor:
xor ebp, esi;    first time, the result is -5
jnz myloop;      second time, the result is 0 - exit loop

The floating-point code implements the Box-Muller transform.

Pyth, 32 bytes
No Python being used now in super-quotes because of the new functions Pyth has now. Yet another Box-Mueller.
 .xvzVQ*@_y.lOZ2.71 2.ty*3.14OZ1

That space in the beginning is important.
.xvz             Seed RNG with evaluated input
VQ               For N in second input
*                Multiplication
 @       2       Square root
   _y            Times negative 2
    .l )         Natural log
     OZ          Of random float (RNG with zero give [0, 1) float)
 .t       1      Cosine from list of trig functions
  y              Double
   *             Multiplication
    .nZ          Pi from constants list
    OZ           Random Float

The seeding doesn't seem to work in the online interpreter, but it works fine in the local version. The online interpreter seems to be fixed, so here's a permalink: permalink

This uses a feature of Pyth (.nZ) that wasn't implemented, when the question was asked. (It was actually implemented today.) Therefore this answer should not be part of the competition (http://meta.codegolf.stackexchange.com/questions/4867/can-i-ever-answer-with-a-language-invented-after-the-challenge-was-posted).

K, I'll got back to the 32 char solution

Yeah, that would be better. You can still show off you new solution in a seperate section of you answer. But the code your competing should be the one working with the old Pyth.

Btw, I don't think that the 32 solution should be valid either. Since it uses the random seed initialized, which was only added about 5 days ago.

Haskell, 118  144
import System.Random;h z=let(u,r)=random z in(cos$2*pi*fst(random r)::Float)*sqrt(-2*log u):h r;g=(.(h.mkStdGen)).take

Example usage:
*Main> g 3 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927]
*Main> g 6 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927,1.1229043,-0.10026576,0.4279402]
*Main> g 6 0xE09B1088DF461F7D
[2.5723906,-0.5177805,-1.3535261,0.7400385,3.5619608e-3,-8.246434e-2]

The return type of random is constrained to Float, which makes random generate a uniform float in [0, 1). From then on it's a simlpe box-muller formula with some pointless magic for list generation.

Octave, 91 96 88 bytes
function r=n(s,n)rand("seed",s);x=rand(2,n);r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));end

Or, with whitespace:
function r=n(s,n)
  rand("seed",s);
  x=rand(2,n);
  r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));
end

Set the seed up front, and use the Box-Mueller method.
NB: Octave allows for generation of arrays of random numbers, and can use standard operations on these arrays which produce array outputs. The .* operator is element-by-element multiplication of two arrays to produce the result.

I think this does not meet the conditions, if you call n(0,1) and n(0,2) you get different first numbers, do you?

Crap, you are correct. I've fixed it but it cost me 5 bytes...

Golflua, 63 70
Golflua info and instructions.
\g(n,s)`_ENV,b=M,{}rs(s)~@i=1,n b[i]=q(l(r()^-2))*c(r()*pi)$~b$

Returns a table containing the values. In the example I'm using ~T.u( ), which is the same as return table.unpack( ) in lua.
> ~T.u(g(3,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981
> ~T.u(g(5,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981 -0.70654636393063 -0.65662878785425
> ~T.u(g(5,7654321))
0.3867923683064 -0.31758512485963 -0.58059120409317 1.2079459300077 1.1500121921242

A lot of chars were saved by setting the function's environment to M (aka math).

Java, 193 bytes
While this doesn't beat the current Java leader, I decided to post anyway to show a different method of calculation. It's a golfed version of OpenJDK's nextGaussian().
class N extends java.util.Random{N(int s,int n){super(s);for(float a,v;n-->0;System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))for(a=0;a>=1|a==0;a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;}}

With line breaks:
class N extends java.util.Random{
    N(int s,int n){
        super(s);
        for(float a,v;
            n-->0;
            System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))
                for(a=0;
                    a>=1|a==0;
                    a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;
    }
}

+1 for using Marsaglia (or rather for not using the straight-forward Box-Muller) ;)

Can this not be a lambda? Something like: (s,n)->{java.util.Random r=new java.util.Random(s);for(float a,v;n-->0;System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))for(a=0;a>=1|a==0;a=v*v+(v=2*r.nextFloat()-1)*v)v=2*r.nextFloat()-1;}

@Quincunx I could, for one byte. But I don't like hiding my function declarations in uncounted code, whatever the current consensus on meta about it. It's worth the one byte to me ;)

SAS, 108
I already posted an answer in R that's shorter than this, but there are very few SAS answers on PPCG, so why not add another?
%macro f(s,n);data;do i=1 to &n;x=sqrt(-2*log(ranuni(&s)))*cos(8*atan2(1,1)*ranuni(&s));put x;end;run;%mend;

With some white space:
%macro f(s, n);
    data;
        do i = 1 to &n;
            x = sqrt(-2 * log(ranuni(&s))) * cos(8 * atan2(1, 1) * ranuni(&s));
            put x;
        end;
    run;
%mend;

This defines a macro which can be called like %f(5, 3). The macro executes a data step which loops through the integers 1 to N, and at each iteration it computes a random normal deviate using Box-Muller and prints it to the log using the put statement.
SAS has no built-in for pi, so the best we can do is approximate it with arctangent.
The ranuni() function (which is deprecated but requires a couple fewer characters than the newer function) returns a random number from a uniform distribution. The SAS documentation doesn't give a whole lot of detail on the RNG implementation other than it has a period of 2^31-2.
In SAS macros, macro variables are referenced with a preceding & and resolve to their values at run time.
As you've probably witnessed, SAS is rarely an actual contender in a code-golf contest.

T-SQL, 155 bytes
CREATE PROC R(@S BIGINT,@N INT)AS
DECLARE @ INT=0,@K INT=8388607WHILE @<@N
BEGIN
SELECT SQRT(-2*LOG(RAND(@S*@%@K)))*COS(2*PI()*RAND(@S*9*@%@K))SET @+=1
END

Use with EXEC R S,N because there is no STD_IN in T-SQL
where S and N are the seed and N respectively. S will produce "random" (RAND(seed) is a really bad random number implementation) sequences when S>2^16 (possibly before that, but I won't guarantee it). Uses Box-Muller like most solutions so far. 8388607 is 2^23-1, which should hopefully generate 2^20 different values.

Powershell, 164 bytes
Param($s,$n)$q=2147483647
$a=GET-RANDOM -SETSEED $s
FOR(;$n---gt0;){$a=GET-RANDOM
$b=GET-RANDOM
[math]::SQRT(-2*[math]::LOG($a/$q))*[math]::COS(2*[math]::PI*$b/$q)}

Same as most answers with Box-Muller. Not very experienced with Powershell, so any help golfing would be appreciated.

Matlab, 77
The first input should be n, the second one s.
a=input('');
rand('seed',a(2));
for i=1:a;
    (-2*log(rand))^.5*cos(2*pi*rand)
end

Ruby, 72 bytes
->n,s{include Math;srand s;n.times{p sqrt(-2*log(rand))*sin(2*rand*PI)}}

Input (as lambda function):
f.(6, 12353405)

Output:
-1.1565142460805273
0.9352802655317097
1.3566720571574993
-0.9683973210257978
0.9851210877202192
0.14709635752306677

PS: I would like to know if this can be golfed further. I'm just a beginner.

@MartinBüttner I think I've been using too much C these days. Totally forgot about.

STATA, 85 bytes
di _r(s)_r(n)
set se $s
set ob $n
g a=sqrt(-2*ln(runiform()))*cos(2*runiform()*_pi)
l

Takes input via standard in (first number is S, then N). Sets the seed to S. Sets the number of observations to N. Makes a variable and sets its value to the Box Muller transform value (thanks to @Alex for showing it). Then lists all of the observations in a table with column header a and observation numbers next to them. If these are not okay, let me know, and I can remove headers and/or observation numbers.

R, 89 Bytes
I know R has been done before but I wanted to show a different approach than the Box-Muller that everyone else used. My solution uses the Central Limit Theorem .
f=function(S,N){set.seed(S);a=1000;for(i in(1:N)){print(sqrt(12/a)*(sum(runif(a))-a/2))}}

I'm afraid, the central limit theorem doesn't satisfy "the algorithm you choose must yield a theoretically exact normal distribution". No matter how many uniform variables you add up, as long as the sum is finite, the normal distribution will always be approximate. (While the central limit theorem is a nice idea, I had to rule it out precisely because it's not clear which value should be used for a in your code such that the result is "fair".)

It was worth a shot ;)

Perl, 150 108 107 bytes
This uses the Marsaglia Polar Method. Called with f(S, N).
Moved the assignment of $a into the calculation of $c.
107:
sub f{srand$_[0];map{do{$c=($a=-1+2*rand)**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

Removed spare number storage and the definition of $b.
108:
sub f{srand$_[0];map{do{$a=-1+2*rand,$c=$a**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

150:
sub f{srand$_[0];map{$h?$h=!print$s:do{do{$a=-1+2*rand,$b=-1+2*rand,$c=$a*$a+$b*$b}until$c<1;$d=sqrt(-2*log($c)/$c);$s=$b*$d;$h=print$a*$d;}}1..$_[1]}

TI-Basic, 74 bytes
Prompt S,N:S→rand:For(X,1,N:0→A:0→V:0→W:While A≥1 or A=0:2rand-1→V:2rand-1→W:V²+W²→A:End:Disp VW√(Aֿ¹-2log(A:End

1      1111111   11   1111111111111111111     1111   111111   1111111   11111111111111  11    111111111   111

The ¹ is actually the inverse operator.

Swift, 144 142
Nothing clever, just seeing how Swift works.
import Foundation;func r(s:UInt32,n:Int){srand(s);for i in 0..<n{println(sqrt(-2*log(Double(rand())/0xffffffff))*sin(2*Double(rand())*M_PI))}}

I was hoping I could use (0...n).map{} but it the compiler doesn't seem to recognise map{} unless you use a parameter.

of course...? it's forEach if you don't want a return value, and I'm pretty sure the _ in is compulsory

what's the /0xffffffff for btw

Haskell, 97 bytes
import System.Random
h(a:b:c)=sqrt(-2*log a::Float)*cos(2*pi*b):h c
f a=take a.h.randoms.mkStdGen

Try it online!
Just your basic Box-Muller transformation, on an infinite list of random numbers.

Python 3, 118 bytes
from random import*
from math import*
def f(s,n):seed(s);return[sqrt(-2*log(random()))*cos(tau*random())for _ in[0]*n]

Try it online!

SmileBASIC, 81 bytes
Well, now that I've answered the first question, I have to do all the rest...
Generating random numbers is cheap, but seeding the RNG uses the longest builtin function in the language, RANDOMIZE.
DEF N S,N
RANDOMIZE.,S
FOR I=1TO N?SQR(-2*LOG(RNDF()))*COS(PI()*2*RNDF())NEXT
END

Maybe there's some way to optimize the formula. I don't see how it's required to use two RNG calls.

It is required to have two independent samples for the Box-Muller transformation

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/