# Creating a less random list

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.

• What is "roughly sorted"? – Αλέξανδρος Ζεγγ Jun 11 '18 at 2:57
• Perhaps, given a certain $p\in[0,1]$, we generate a list that has probability $p$ of being sorted? In that case, if you take some $p$ very close to $1$, you'll probably get a list that is almost sorted. I don't know how to generate such a list off the top of my head, but it is certainly an interesting problem! – AccidentalFourierTransform Jun 11 '18 at 3:38
• A possible approach would be to pick a permutation belonging to the group $S_n$ where n is the size of the list and then act that permutation repeatedly on the list. The best permutation to pick is the one with maximal order. Take a look at this article: en.wikipedia.org/wiki/Landau%27s_function – Subho Jun 11 '18 at 6:50
• I don't think @AccidentalFourierTransform's idea strikes at the OP's goal. You could sort a list and then with probability $p$ flip interchange the last two entries and get "a list that has a probability $p$ of being sorted." Not at all what is requested. – David G. Stork Jun 11 '18 at 6:52
• This is might be useful: mathematica.stackexchange.com/questions/129714/… – Subho Jun 11 '18 at 7:01

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}

• Well with p=0.1 there's still possibility that the list is sorted :( But I think this answers most of the question – t-smart Jun 12 '18 at 9:15
• @t-smart If you want to be certain about the deviation from a perfect sort why don't use the rand function instead of rand2 and put any number between 1 and the size of the list as the second argument depending on the amount of scramble you want. Does that not work for you? – Subho Jun 12 '18 at 10:15
• that would work fine,thanks! – t-smart Jun 12 '18 at 12:29

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}