Creating a less random list

Question

I'm trying to create an list like {1,3,2,5,8,7,9}, or {2,1,5,6,4,7,9}, that the elements in each list is sorted in a rough order, but not exactly sorted. The Random functions does not really work in this scenario. So how can I create this kind of list? UPDATE I suppose I should make it more clear. So there is a variable p that defines how "sorted" the list is, with p==1 being a totally sorted list and p==0 being an unsorted list, p==-1 means an inversely sorted list. So my goal was to generate lists with a p value in a range.

Answer 1

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}

Answer 2

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}