30
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Related? \$\endgroup\$ – Addison Crump Dec 19 '16 at 0:47
  • 3
    \$\begingroup\$ @VoteToClose: haha, totally busted \$\endgroup\$ – shooqie Dec 19 '16 at 4:58
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Farhan Anam Dec 19 '16 at 16:55
  • \$\begingroup\$ Is there any guarantee that the elements will be unique, or can they contain duplicates? \$\endgroup\$ – Carcigenicate Dec 20 '16 at 0:44
  • 1
    \$\begingroup\$ @Carcigenicate: it's right there in the description; you may assume there are no duplicates \$\endgroup\$ – shooqie Dec 20 '16 at 11:34

21 Answers 21

12
\$\begingroup\$

CJam, 14 bytes

q:X{mr_X.=:|}g

Try it online!

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I wish OP had specified that solutions would have to guarantee they always finish. \$\endgroup\$ – John Dvorak Dec 18 '16 at 13:36
  • 4
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Dec 18 '16 at 13:54
  • \$\begingroup\$ 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). \$\endgroup\$ – Nobody Dec 18 '16 at 14:28
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Dec 18 '16 at 14:42
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – maservant Dec 19 '16 at 16:03
9
\$\begingroup\$

Jelly, 6 bytes

Ẋ=³S$¿

Try it online!

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ So you got your Winter Bash hat ahead of time? :-) \$\endgroup\$ – Luis Mendo Dec 18 '16 at 16:59
  • 2
    \$\begingroup\$ Time to draw a nice new picture, Ẋ=³S$¿ saves a byte. \$\endgroup\$ – Jonathan Allan Dec 18 '16 at 17:55
  • 2
    \$\begingroup\$ Huh, I never knew that about $. Thanks! \$\endgroup\$ – Lynn Dec 18 '16 at 17:58
  • \$\begingroup\$ It's 6 chars, but more than 6 bytes. Ẋ=³S$¿ byte lengths are: 312112. So 10 bytes in total. \$\endgroup\$ – mxfh Mar 16 '17 at 0:10
6
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ If 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! \$\endgroup\$ – mathmandan Dec 18 '16 at 23:09
  • \$\begingroup\$ @mathmandan good idea, but then I'd need to print it back out again if it's a full program, which costs more bytes. \$\endgroup\$ – FlipTack Dec 19 '16 at 7:34
  • 1
    \$\begingroup\$ OK, 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.) :) \$\endgroup\$ – mathmandan Dec 19 '16 at 12:10
5
\$\begingroup\$

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>

\$\endgroup\$
5
\$\begingroup\$

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

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 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.
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 19 18 15 13 bytes

@~.:?z:#da;?&

Try it online!

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
\$\endgroup\$
3
\$\begingroup\$

Perl 6, 45 bytes

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

Try it

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
}
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Any improvements? Do I really need t there or can I get rid of it? It was fun trying to golf in MATL... :) \$\endgroup\$ – Stewie Griffin Dec 18 '16 at 13:52
  • \$\begingroup\$ :-) 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 \$\endgroup\$ – Luis Mendo Dec 18 '16 at 14:16
3
\$\begingroup\$

Actually, 13 bytes

;;WX╚│♀=ΣWX)X

Try it online!

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Note to self: Read the entire question next time :) Thanks! \$\endgroup\$ – Stewie Griffin Dec 18 '16 at 13:16
  • 1
    \$\begingroup\$ That happens to me all the time :-) \$\endgroup\$ – Luis Mendo Dec 18 '16 at 13:50
2
\$\begingroup\$

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!

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
\$\endgroup\$
2
\$\begingroup\$

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.

.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
\$\endgroup\$
  • \$\begingroup\$ Can you please add an explanation. I wanted to write a pyth answer. I don't know much about it. \$\endgroup\$ – Gurupad Mamadapur Dec 18 '16 at 17:07
  • \$\begingroup\$ @GurupadMamadapur sure, would be happy too. \$\endgroup\$ – Maltysen Dec 18 '16 at 17:08
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Maltysen Dec 18 '16 at 17:12
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ nice! Slightly longer #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]& obviously quicker in practice for long strings \$\endgroup\$ – martin Dec 18 '16 at 21:28
  • \$\begingroup\$ Wait, you're telling me there is no built-in for derangements in Mathematica? :o \$\endgroup\$ – shooqie Dec 18 '16 at 22:04
  • \$\begingroup\$ I was half expecting a built-in myself :) \$\endgroup\$ – Greg Martin Dec 19 '16 at 8:45
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 67 bytes

def f a
while (a.zip(o=a.shuffle).map{|x,y|x-y}.index 0);end
o
end
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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))))
\$\endgroup\$
0
\$\begingroup\$

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?

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ETHproductions Dec 22 '16 at 16:00
  • \$\begingroup\$ I think it should fit the requirements now. It takes in the right argument, or . \$\endgroup\$ – Jacob Utley Dec 22 '16 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.