[Question]
  [
# Challenge description
A "derangement" of a sequence is a permutation where no element appears in its original position. For example `ECABD` is a derangement of `ABCDE`, but `CBEDA` is not:
```
ABCDE
 | |   <- B and D are in their orignal positions
CBEDA
```
Given a sequence, generate a random derangement of it.
# Notes
* You may take either a string as an input or an array/list of elements (integers, chars, objects...)
* Instead of returning a new object, you can modify an existing one by swapping its elements
* Each derangement should have an equal probability of being generated
* You may assume that there is more than one element in the sequence and none appear more than once
  
[Answer]
## [CJam](https://sourceforge.net/p/cjam), 14 bytes
```
q:X{mr_X.=:|}g
```
[Try it online!](https://tio.run/nexus/cjam#@19oFVGdWxQfoWdrVVOb/v@/o5OziysA "CJam – TIO Nexus")
Keeps shuffling the input until it's a derangement.
### Explanation
```
q:X   e# Read input and store it in X.
{     e# While the condition at the end of the loop is truthy...
  mr  e#   Shuffle the string.
  _X  e#   Duplicate it and push the input.
  .=  e#   Element-wise equality check.
  :|  e#   Reduce OR over the list, gives something truthy if any character
      e#   remained in its original position.
}g
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 6 bytes
```
Ẋ=³S$¿
```
[Try it online!](http://jelly.tryitonline.net/#code=4bqKPcKzUyTCvw&input=&args=MSwyLDM)
## Explanation
```
Ẋ    ¿    Shuffle the given list while this is nonzero for it:
    $       A two-step process:
 =³           Element-wise equality of it and L (the original list)...
   S          Sum the ones in this binary array.
```
Jonathan Allan saved a byte.
[Answer]
# Python, 85 bytes
Modifies the list passed to it (allowed by meta and in the question). 
```
from random import*
def D(l):
 o=l[:]
 while any(x==y for x,y in zip(o,l)):shuffle(l)
```
[**Try it online here!**](https://repl.it/Esrn/0)
[Answer]
# ES6 (Javascript), ~~71~~, 69 bytes
Input and output are arrays, should work with any element types (strings, numbers e.t.c.), as long as they can be compared with "==".
**Golfed**
```
F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r
```
**Test**
```
F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r
F(['A','B','C','D'])
Array [ "D", "C", "A", "B" ]
F(['A','B','C','D'])
Array [ "D", "A", "B", "C" ]
F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]
F(['A','B','C','D'])
Array [ "D", "C", "B", "A" ]
F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]
```
**Interactive Snippet**
```
F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r
function G() {
    console.log(F(T.value.split``).join``); 
}
```
```
<input id=T value="ABCDEF"><button id=G onclick="G()">GENERATE</button>
```
[Answer]
## [Perl 6](http://perl6.org/), 33 bytes
```
{first (*Zne$_).all,.pick(*)xx *}
```
A lambda that takes a list of integers or characters as input, and returns a new list.
If it must support lists of *arbitrary* values, `ne` would have to be replaced with `!eqv` (+2 bytes).
([Try it online.](https://tio.run/#aWM7Z))
### Explanation:
* `{ }`: Defines a lambda.
* `.pick(*)`: Generates a random shuffle of the input list.
* `.pick(*) xx *`: Creates a lazy infinite sequence of such shuffles.
* `(* Zne $_).all`: A lambda that zips two lists (its argument `*`, and the outer lambda's argument `$_`) with the `ne` (negative string equality) operator, yielding a list of booleans, and then creates an [`all` junction](https://docs.perl6.org/type/Junction) to collapse them to a single boolean state.
* `first PREDICATE, SEQUENCE`: Takes the first element from our infinite sequence of permutations that fulfills the "derangement" test.
[Answer]
# MATL, 7 bytes
This is a translation of my Octave post (and similar to some of the other submissions here). I posted my first MATL post yesterday (CNR crack), so I guess this is not optimal, but it's the best I've got so far.
To be honest, I'm not entirely sure `t` is needed in there, but it's the only way I can get this to work. It's used so that I can compare the user input (retrieved with `G`), with the random permutation. I would think I could compare the two without it, but...?
Anyway, here goes:
```
`Z@tG=a
`          % Loop
 Z@        % Random permutation of input
   t       % Duplicating the stack
    G      % Paste from clipboard G (user input)
     =     % Comparing the random permutation with the input (retrieved from clipboard)
      a    % any(input == random permutation)
           % Implicit end and display
```
[Try it online!](http://matl.tryitonline.net/#code=YFpAdEc9YQ&input=J0FCQ0RFRic)
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), ~~19~~ ~~18~~ ~~15~~ 13 bytes
```
@~.:?z:#da;?&
```
[Try it online!](https://tio.run/nexus/brachylog#@@9Qp2dlX2WlnJJoba/2/3@0oZWRlbGViZWplVns/ygA "Brachylog – TIO Nexus")
### Explanation
```
@~.                Output is a shuffle of the input
  .:?z             Zip the output with the input
      :#da         All couples of integers of the zip must be different
          ;      Or
           ?&      Call recursively this predicate with the same input
```
[Answer]
# [Perl 6](https://perl6.org), 45 bytes
```
{(@^a,{[.pick(*)]}...{none @a Zeqv@$_})[*-1]}
```
```
{(@^a,{[.pick(*)]}...{!sum @a Zeqv@$_})[*-1]}
```
[Try it](https://tio.run/nexus/perl6#Ky1OVSgz00u25uLKrVRQS85PSVWw/V@t4RCXqFMdrVeQmZytoaUZW6unp1edl5@XquCQqBCVWljmoBJfqxmtpWsYW/u/OLFSAazRxlHBScFZwUXB1U4hLb9IIc7QwJoLJKuuDqHBqqINdYx0jHUO7dV51DpVpwaiyS4WoeM/AA "Perl 6 – TIO Nexus")
Input is an Array of anything.
## Expanded:
```
{
  (
    @^a,          # declare parameter, and seed sequence generator
    {             # lambda with implicit parameter ｢$_｣
      [           # store into an array
        .pick(*)  # shuffle ｢$_｣
      ]
    }
    ...           # keep generating the sequence until
    {
      none        # none
      @a          # of the outer blocks input
      Z[eqv]      # is zip equivalent
      @$_         # with the current value being tested
    }
  )[ * - 1 ]      # return the last value
}
```
[Answer]
# [Actually](https://github.com/Mego/Seriously), 13 bytes
```
;;WX╚│♀=ΣWX)X
```
[Try it online!](https://tio.run/nexus/actually#@29tHR7xaOqsR1OaHs1ssD23ODxCM@L/fyVHJ2cXVyUA "Actually – TIO Nexus")
Explanation:
```
;;WX╚│♀=ΣWX)X
;;             make two copies of input
  WX╚│♀=ΣW     while top of stack is truthy:
   X             discard top of stack
    ╚            shuffle array
     │           duplicate entire stack
      ♀=         compare corresponding elements in shuffled and original for equality
        Σ        sum (truthy if any elements are in the same position, else falsey)
          X)X  discard everything but the derangement
```
[Answer]
# Octave, ~~56~~ 55 bytes
```
x=input('');while any(x==(y=x(randperm(nnz(x)))));end,y
```
We have to use `input('')` since this is not a function. Also, since I can choose to have the input as a string we can use the trick that `nnz(x)==numel(x)`.
**Explanation:**
```
x=input('')            % Self-explanatory
while any(x==y)        % Loop until x==y has only 0s (i.e. no elements are equal)
y=x(randperm(nnz(x)))  % Continue to shuffle the indices and assign x(indices) to y
end                    % End loop
y                      % Display y
```
Thanks to Luis for noticing that the input can be a string, thus I could use `nnz` instead of `numel` saving two bytes.
[Answer]
# MATL, 13 bytes
This is a joint effort of @LuisMendo and me. In contrast to many other answers here this one is deterministic in the sense that it does not sample random permutations until it gets a derangement, but it generates all derangements and chooses one randomly.
```
Y@tG-!Af1ZrY)
```
[Try It Online!](https://tio.run/nexus/matl#@x/pUOKuq@iYZhhVFKn5/796YlJyijoA)
### Explanation
```
Y@tG-!Af1ZrY)
Y@             generate all permutatoins
  t            create a duplicate
   G-!A        find the (logical) indices of all valid derangements (where no character of the string is in the same position as the original string)
       f       convert logical to linear indices
        1Zr    choose one of those indices randomly
           Y)  get the derangement (from the ones we generated earlier) at this index
```
[Answer]
# Pyth - ~~10~~ 9 bytes
This keeps on shuffling the input while any of the characters equal the characters at their index in the input.
```
.WsqVHQ.S
```
[Try it online here](http://pyth.herokuapp.com/?code=.WsqVHQ.S&input=%22ABCDE%22&debug=0).
```
.W           Iterate while
 s           Sum, this is works as any() on a boolean list
  qV         Vectorized equality
   H         The lambda variable for the check step
   Q         The input
 .S          Shuffle
  (Z)        Lambda variable, implicit
 (Q)         Start .W with input, implicit
```
[Answer]
# Mathematica, 57 bytes
```
#/.x_:>RandomChoice@Select[Permutations@x,FreeQ[#-x,0]&]&
```
Unnamed function taking a list of whatevers as input and outputting a list. After generating all permutations `#` of the input `x`, we keep only the ones for which the set `#-x` of element-wise differences doesn't contain a `0`; then we make a (uniformly) random choice from that set.
[Answer]
# PHP, 85 bytes
```
for($a=$b=str_split($argv[1]);array_diff_assoc($a,$b)!=$a;)shuffle($b);echo join($b);
```
Copies the string argument to two arrays, shuffles one of them until the difference between them (also comparing indexes of the elements) equals the other one. Run with `-r`.
[Answer]
# R, 59 bytes
```
z=x=1:length(y<-scan(,""));while(any(x==z))z=sample(x);y[z]
```
Reads a list of elements to STDIN, takes the length of the list and starts sampling ranges from 1 to the length, until it finds one that shares no places with the ordered list. Then prints that list.
[Answer]
# [Wonder](https://github.com/wonderlang/wonder), 32 bytes
```
f\@[/>#I zip#=[#0a\shuf#0]?f a?a
```
Usage:
```
f\@[/>#I zip#=[#0a\shuf#0]?f a?a];f[1 2 3 4 5]
```
# Explanation
More readable:
```
f\@[
  some #I zip #= [#0; a\ shuf #0]
    ? f a
    ? a
]
```
Recursive function `f`. Does an element-wise comparison between `f`'s input list and and a shuffled version of the input list. If the comparison yields any equal values, then `f` is called on the shuffled list. Otherwise, we simply return the shuffled list.
[Answer]
# Ruby, 67 bytes
```
def f a
while (a.zip(o=a.shuffle).map{|x,y|x-y}.index 0);end
o
end
```
[Answer]
# Octave,  ~~54~~ 53 bytes
```
@(a)((p=perms(a))(L=!any(p==a,2),:))(randi(sum(L)),:)
```
Generate all permutations of `a` and select randomly a row that doesn't have a common element with `a` .
note: It is accidentally the same as @flawr MATL answer!
[Answer]
## Clojure, ~~94~~ ~~90~~ 79 bytes
```
#(let[s(shuffle %)](if(not(some(fn[[x y]](= x y))(map vector % s)))s(recur %)))
```
-4 bytes by changing the conditional inside the reduction to an `and`, and inlining `done?`.
-11 bytes by converting the reduction to `some`.
WOOT! Beat PHP.
Brute-force method. Shuffles the list while it's invalid. This finishes stupid fast considering it's a brute force method that does nothing to prevent duplicate tries. It found 1000 dearangments of a 1000 element long list in less than a second. 
Ungolfed:
```
(defn dearang [ls]
  (let [s (shuffle ls)
        bad? (some (fn [[x y]] (= x y))
                (map vector ls s))]
    (if (not bad?) s (recur ls))))
```
[Answer]
## Clojure, 56 bytes
```
#(let[s(shuffle %)](if((set(map = % s))true)(recur %)s))
```
Note that a string cannot be shuffled, must be passed through `seq` or `vec`.
Originally I tried `#(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))` but `recur` approach is indeed shorter than `iterate`.
The magic is that `(set(map = % s))` returns either a set of false, set of true or set of true and false. This can be used as a function, if it contains `true` then the answer is `true`, otherwise falsy `nil`. `=` is happy to take two input arguments, no need to wrap it with something.
```
((set [false]) true)
nil
```
Maybe there is even shorter way to check if any of the values is true?
[Answer]
# APL, 11 bytes.
With the string in the right argument:
`⍵[⍋(⍴⍵)?⍴⍵]`
# Explanation
`ρ⍵` gets the length (or shape) of the right argument.
`?` returns a random array of `(⍴⍵)` of these numbers.
`⍋` returns the order of them in order to ensure no duplicates.
`⍵[..]` represents the random assortment of the string using this index.
]