30
2
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
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.423I don't think the distribution of derangements would be uniform then. – shooqie – 2016-12-23T09:38:44.503