Generate a random derangement



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:

 | |   <- B and D are in their orignal positions

Given a sequence, generate a random derangement of it.


  • 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


Posted 2016-12-18T09:44:03.627

Reputation: 5 032

4Related? – Addison Crump – 2016-12-19T00:47:29.837

3@VoteToClose: haha, totally busted – shooqie – 2016-12-19T04:58:13.757

I don't know much about all this but is this in any way related to the fixed point theorem... according to which things will always end up in their own position or something like that...? I'll wager I'm wrong but someone please correct me :) – Farhan Anam – 2016-12-19T16:55:34.747

Is there any guarantee that the elements will be unique, or can they contain duplicates? – Carcigenicate – 2016-12-20T00:44:27.797

1@Carcigenicate: it's right there in the description; you may assume there are no duplicates – shooqie – 2016-12-20T11:34:50.120

@shooqie Whoops, sorry. Missed the last point. – Carcigenicate – 2016-12-20T13:20:57.020

If I take a random amount of chars (1 - (len()-1)) from the beginning of the string and set them to the end, does it count? Ie. ABCDE -> CDEAB – James Brown – 2016-12-23T09:24:37.423

I don't think the distribution of derangements would be uniform then. – shooqie – 2016-12-23T09:38:44.503



CJam, 14 bytes


Try it online!

Keeps shuffling the input until it's a derangement.


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.

Martin Ender

Posted 2016-12-18T09:44:03.627

Reputation: 184 808

1I wish OP had specified that solutions would have to guarantee they always finish. – John Dvorak – 2016-12-18T13:36:05.097

4@JanDvorak Well, the probability that this doesn't finish is 0. But you're right that requiring a deterministic running time would have made the challenge more interesting. – Martin Ender – 2016-12-18T13:54:11.903

Is the probability actually 0? The shuffle operation won't be perfect, how does it actually work? I think this probably is a good approximation of what the OP asked for, but I doubt the probabilities of each derangement are the same (probably it depends on some seed value of the PRNG which is likely used by the shuffle operation). – Nobody – 2016-12-18T14:28:42.880

3@Nobody I doubt you can get perfectly uniform results from a PRNG using any algorithm whatsoever. However, assuming that the shuffle itself is uniform (which the Java docs sort of guarantee with "All permutations occur with approximately equal likelihood."), a rejection-based solution will also yield uniform derangements, because each derangement is one permutation, and each permutation has the same probability. – Martin Ender – 2016-12-18T14:42:34.477

1@Nobody Math nerd here. A condition that either succeeds or fails is called a Bernoulli trial in statistics. This implies that the probability of the needing k trials to first success is (1 - p)^(k - 1) * p, where p is the probability of a successful derangement. It's easy to see that as k grows larger, the probability of needing k trials becomes vanishingly small. Therefore, we say the algorithm halts with probability 1 ("almost surely"), yet it is not impossible that it never halts. – maservant – 2016-12-19T16:03:44.677


Jelly, 6 bytes


Try it online!


Ẋ    ¿    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.


Posted 2016-12-18T09:44:03.627

Reputation: 55 648

5So you got your Winter Bash hat ahead of time? :-) – Luis Mendo – 2016-12-18T16:59:53.173

2Time to draw a nice new picture, Ẋ=³S$¿ saves a byte. – Jonathan Allan – 2016-12-18T17:55:49.040

2Huh, I never knew that about $. Thanks! – Lynn – 2016-12-18T17:58:16.210

It's 6 chars, but more than 6 bytes. Ẋ=³S$¿ byte lengths are: 312112. So 10 bytes in total. – mxfh – 2017-03-16T00:10:28.027


Python, 85 bytes

Modifies the list passed to it (allowed by meta and in the question).

from random import*
def D(l):
 while any(x==y for x,y in zip(o,l)):shuffle(l)

Try it online here!


Posted 2016-12-18T09:44:03.627

Reputation: 13 242

1If you specify Python 2, I think you could replace def D(l): with l=input() and then save the indentation spaces in the following lines (so you have a program instead of a function). Did not downvote, though! – mathmandan – 2016-12-18T23:09:00.750

@mathmandan good idea, but then I'd need to print it back out again if it's a full program, which costs more bytes. – FlipTack – 2016-12-19T07:34:35.570

1OK, if you say so. I guess to me the spec seemed to be saying that you didn't have to print out or return the result--that taking a list [from user input] and shuffling it would be sufficient. But it's reasonable to read "existing" as "existing prior to running any of your code", in which case I agree with you. (Maybe there's a well-established consensus on this.) :) – mathmandan – 2016-12-19T12:10:39.100


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 "==".





Array [ "D", "C", "A", "B" ]

Array [ "D", "A", "B", "C" ]

Array [ "C", "D", "B", "A" ]

Array [ "D", "C", "B", "A" ]

Array [ "C", "D", "B", "A" ]

Interactive Snippet


function G() {
<input id=T value="ABCDEF"><button id=G onclick="G()">GENERATE</button>


Posted 2016-12-18T09:44:03.627

Reputation: 7 884


Perl 6, 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.)


  • { }: 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 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.


Posted 2016-12-18T09:44:03.627

Reputation: 4 352


Brachylog, 19 18 15 13 bytes


Try it online!


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


Posted 2016-12-18T09:44:03.627

Reputation: 32 976


Perl 6, 45 bytes

{(@^a,{[.pick(*)]}...{none @a Zeqv@$_})[*-1]}
{(@^a,{[.pick(*)]}...{!sum @a Zeqv@$_})[*-1]}

Try it

Input is an Array of anything.



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

Brad Gilbert b2gills

Posted 2016-12-18T09:44:03.627

Reputation: 12 713


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:


`          % 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!

Stewie Griffin

Posted 2016-12-18T09:44:03.627

Reputation: 43 471

Any improvements? Do I really need t there or can I get rid of it? It was fun trying to golf in MATL... :) – Stewie Griffin – 2016-12-18T13:52:18.103

:-) I don't see how to get rid of that t (or equivalently another G) You need to leave something on the stack for the next iteration or as final result – Luis Mendo – 2016-12-18T14:16:26.380


Actually, 13 bytes


Try it online!


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


Posted 2016-12-18T09:44:03.627

Reputation: 32 998


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


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.

Stewie Griffin

Posted 2016-12-18T09:44:03.627

Reputation: 43 471

Note to self: Read the entire question next time :) Thanks! – Stewie Griffin – 2016-12-18T13:16:54.437

1That happens to me all the time :-) – Luis Mendo – 2016-12-18T13:50:52.033


Pyth - 10 9 bytes

This keeps on shuffling the input while any of the characters equal the characters at their index in the input.


Try it online here.

.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


Posted 2016-12-18T09:44:03.627

Reputation: 25 023

Can you please add an explanation. I wanted to write a pyth answer. I don't know much about it. – Gurupad Mamadapur – 2016-12-18T17:07:14.283

@GurupadMamadapur sure, would be happy too. – Maltysen – 2016-12-18T17:08:48.940


@GurupadMamadapur added. We have a tutorial. Its pretty out of date, but will teach you the basics. If you need any help with anything related to pyth, feel free to ping me in chat.

– Maltysen – 2016-12-18T17:12:37.577


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.


Try It Online!


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


Posted 2016-12-18T09:44:03.627

Reputation: 40 560


Mathematica, 57 bytes


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.

Greg Martin

Posted 2016-12-18T09:44:03.627

Reputation: 13 940

1nice! Slightly longer #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]& obviously quicker in practice for long strings – martin – 2016-12-18T21:28:45.997

Wait, you're telling me there is no built-in for derangements in Mathematica? :o – shooqie – 2016-12-18T22:04:13.050

I was half expecting a built-in myself :) – Greg Martin – 2016-12-19T08:45:02.303


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.


Posted 2016-12-18T09:44:03.627

Reputation: 13 814


Wonder, 32 bytes

f\@[/>#I zip#=[#0a\shuf#0]?f a?a


f\@[/>#I zip#=[#0a\shuf#0]?f a?a];f[1 2 3 4 5]


More readable:

  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.

Mama Fun Roll

Posted 2016-12-18T09:44:03.627

Reputation: 7 234


R, 59 bytes


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.


Posted 2016-12-18T09:44:03.627

Reputation: 2 898


Octave, 54 53 bytes


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!


Posted 2016-12-18T09:44:03.627

Reputation: 5 435


Ruby, 67 bytes

def f a
while ({|x,y|x-y}.index 0);end


Posted 2016-12-18T09:44:03.627

Reputation: 311


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.


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.


(defn dearang [ls]
  (let [s (shuffle ls)
        bad? (some (fn [[x y]] (= x y))
                (map vector ls s))]
    (if (not bad?) s (recur ls))))


Posted 2016-12-18T09:44:03.627

Reputation: 3 295


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)

Maybe there is even shorter way to check if any of the values is true?


Posted 2016-12-18T09:44:03.627

Reputation: 2 361


APL, 11 bytes.

With the string in the right argument:



ρ⍵ 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.

Jacob Utley

Posted 2016-12-18T09:44:03.627

Reputation: 121

Welcome to PPCG! We require all entries to be valid functions or full programs, so your answer needs to take input through a function argument or input method. – ETHproductions – 2016-12-22T16:00:05.170

I think it should fit the requirements now. It takes in the right argument, or . – Jacob Utley – 2016-12-22T16:18:57.003