Creating a less random list
Define a function swap
which swaps adjacent elements in a list.
swap[x_List, i_Integer] := ReplacePart[x, {i -> x[[i + 1]], i + 1 -> x[[i]]}]
Then define a function which swaps adjacent elements k
times.
SomewhatSorted[x_List, k_Integer] :=
Fold[swap[#1, #2] &, x, RandomInteger[{1, Length[x] - 1}, k]]
Increase k
to create lists with more differences from the original input list x
. For example,
SomewhatSorted[{a, b, c, d, e, f, g, h}, 0]
{a, b, c, d, e, f, g, h}
SomewhatSorted[{a, b, c, d, e, f, g, h}, 3]
{c, a, b, e, d, f, g, h}
This is based on the idea of Cayley Distance as you will find in https://math.stackexchange.com/questions/1932991/catalan-number-and-cayley-distance-inequality-in-permutation-group and in Permutations: any implementation of the Cayley distance?.
Borrowing the CayleyDistance function of @corey979:
CayleyDistance[patt_, dis_] := PermutationOrder@FindPermutation[patt, dis];
rand[list_, n_] :=
RandomChoice[#[[n]][[2]]] & @({CayleyDistance[Sort@list,First@#], #} & /@
Gather[Permutations[Sort@list], CayleyDistance[Sort@list, #1] ==
CayleyDistance[Sort@list, #2] &])
Note that n is the measure of deviation(Cayley Distance) from the sorted list that can go from 1 to the size of the list.
Hence:
rand[{1, 3, 2, 5, 8, 7, 9}, 3]
{9, 5, 3, 7, 2, 1, 8}
is a random permutation that is at a Cayley Distance of 3 from the perfectly sorted list.
If you want to randomly choose n as well you can very well do:
rand[{1, 3, 2, 5, 8, 7, 9}, RandomInteger[{1,7}]]
{8, 3, 2, 5, 7, 1, 9}
Edit:
Following the comment of @AccidentalFourierTransform one can say that if $p$ is the probability of the list being sorted then assuming that the picking of list follows a binomial distribution $Bin(n-1,1-p)$:
rand2[list_, p_] :=
Module[{n =
1 + RandomVariate[BinomialDistribution[Length@list - 1, 1 - p]]},
RandomChoice[#[[n]][[2]]] & @({CayleyDistance[Sort@list, First@#], #} & /@
Gather[Permutations[Sort@list], CayleyDistance[Sort@list, #1] ==
CayleyDistance[Sort@list, #2] &])]
one can say:
rand2[{1, 3, 2, 5, 8, 7, 9}, 0.1]
{3, 8, 5, 7, 9, 2, 1}
rand2[{1, 3, 2, 5, 8, 7, 9}, 0.5]
{8, 9, 2, 5, 3, 1, 7}
rand2[{1, 3, 2, 5, 8, 7, 9}, 0.8]
{1, 5, 3, 2, 7, 8, 9}
rand2[{1, 3, 2, 5, 8, 7, 9}, 1]
{1, 2, 3, 5, 7, 8, 9}