7
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ What is "roughly sorted"? $\endgroup$ – Αλέξανδρος Ζεγγ Jun 11 '18 at 2:57
  • $\begingroup$ 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! $\endgroup$ – AccidentalFourierTransform Jun 11 '18 at 3:38
  • $\begingroup$ 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 $\endgroup$ – Subho Jun 11 '18 at 6:50
  • $\begingroup$ 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. $\endgroup$ – David G. Stork Jun 11 '18 at 6:52
  • $\begingroup$ This is might be useful: mathematica.stackexchange.com/questions/129714/… $\endgroup$ – Subho Jun 11 '18 at 7:01
6
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Well with p=0.1 there's still possibility that the list is sorted :( But I think this answers most of the question $\endgroup$ – t-smart Jun 12 '18 at 9:15
  • $\begingroup$ @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? $\endgroup$ – Subho Jun 12 '18 at 10:15
  • $\begingroup$ that would work fine,thanks! $\endgroup$ – t-smart Jun 12 '18 at 12:29
6
$\begingroup$

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}

$\endgroup$

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.