where a linear will do.

Could you show us that please?

Just don't shuffle the entire array; stop if you have shuffled three elements (taking care you don't shuffle in the leading animal).

my @animals = qw [dog cat bird mouse rat snake horse cow
                  pig lizard lamb zebra lion elephant monkey];

my @scratch = @animals;

foreach my $animal (@animals) {
    for (my $j = @scratch - 1; $j >= @scratch - 3; $j --) {
        my $r = rand ($j + 1);
        @scratch[$j, $r] = @scratch[$r, $j];
        if ($scratch[$j] eq $animal) {
            my $r = rand ($j);
            @scratch[$j, $r] = @scratch[$r, $j];
        }
    }
    say "$animal @scratch[-3..-1]";
}
[download]

As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.

As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.

Yep. Linear, but twice as slow as my code above for the OPs stated requirements:

c:\test>713977-javafan -N=1e6
Took 0.00029 seconds/iteration

c:\test>713977 -N=1e6
Took 0.00015 seconds/iteration
[download]

How much bigger than the requirements does the problem need to get before the additional complexity achieves parity?

And how much bigger still, before the additional complexity of your solution starts to save enough time that the user will actually notice?

Finally, what affect does that re-pick have upon the fairness of the shuffle?

Read more... (2 kB)

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."