<p>Here is an algorithm:
Choose a number from the sequence with probabilities proportional to their values, remove it and push_front it to the output sequence. Repeat the steps.</p>

<p>With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.</p>

<p>The algorithm can be implemented in time O(NlogN)</p>

CC BY-SA 3.0
2013-05-02T19:37:41.527Z
Indeed! I started out thinking along similar lines (analoguously to insertion sort or the like), but somehow convinced myself that the probabilities couldn't be untangled.
Magnus Lie Hetland
CC BY-SA 3.0
2013-05-02T08:58:22.003Z
2013-05-02T08:58:22.003Z
Really_Need_A_Name
<p>You could use the <a href="http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm" rel="nofollow">Metropolis-Hastings algorithm</a> (or perhaps <a href="http://en.wikipedia.org/wiki/Gibbs_sampling" rel="nofollow">Gibbs sampling</a>) to sample your sequence, as long as you can calculate the desired probability for the entire sequence (or a function that is <em>proportional</em> to the probability). As I understand you, you wish to let the probability of $a$ coming before $b$ be set to the odds $a\mathop{:}b$. If all such decisions were independent, you could simply multiply the probabilities (derived from the odds) over all the pairs—but of course they're not. This might be a good enough approximation of what you're after, though, depending on what the application is.</p>

<p>Anyway, once you have your probability function $f(s)$ (defined over the entire sequence $s$), an application of the Metropolis algorithm (a special case of Metropolis-Hastings) would be something like this:</p>

<ol>
<li>Start with an arbitrary ordering $s$.</li>
<li>Generate a different ordering, $s'$, for example by randomly swapping two elements.</li>
<li>Compute the acceptance ratio $\alpha = f(s')/f(s)$.</li>
<li>If $\alpha \geq 1$, accept $s'$, that is, use it instead of $s$ for the next iteration. Go to 2.</li>
<li>Otherwise, accept $s'$ with a probability $\alpha$. Go to 2.</li>
</ol>

<p>And then you let this run for “a while”—exactly how long would depend on the length of your sequence (though the number of iterations should be on the order of the autocorrelation of the Markov process; you can probably find more details on this in a good book on Monte Carlo methods).</p>

CC BY-SA 3.0
2013-04-30T19:53:51.110Z
2013-04-30T20:04:16.390Z
2013-04-30T20:04:16.390Z
Magnus Lie Hetland
<p>I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a sequence than a smaller element is proportional to the ratio of these elements' values.</p>

<p>For instance if we have a sorted sequence of elements: <code>1, 2, 3</code>, then I'd like this algorithm to generate a permutation of this sequence in such a way that the probability of finding element <code>3</code> earlier in a sequence than the element <code>1</code> is 3 times smaller than the other way around. This property should hold for all pairs of the elements.</p>

<p>Is this possible?  If so, can you suggest an algorithm for this?</p>

<randomness><sorting><permutations>
Sort with random deviations
Max
# Sort with random deviations

(Asked by: username_0 on 2013-04-29)

I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a sequence than a smaller element is proportional to the ratio of these elements' values.

For instance if we have a sorted sequence of elements: `1, 2, 3`, then I'd like this algorithm to generate a permutation of this sequence in such a way that the probability of finding element `3` earlier in a sequence than the element `1` is 3 times smaller than the other way around. This property should hold for all pairs of the elements.

Is this possible? If so, can you suggest an algorithm for this?

**Tags:** randomness, sorting, permutations

---

## 2 answers

### Answer by username_1 on 2013-05-02. Score: 4 | Accepted answer

Here is an algorithm:
Choose a number from the sequence with probabilities proportional to their values, remove it and push\_front it to the output sequence. Repeat the steps.

With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.

The algorithm can be implemented in time O(NlogN)

> **Comments:**
> **username_2**: Indeed! I started out thinking along similar lines (analoguously to insertion sort or the like), but somehow convinced myself that the probabilities couldn't be untangled.  

---

### Answer by username_2 on 2013-04-30. Score: 3

You could use the [Metropolis-Hastings algorithm](http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm) (or perhaps [Gibbs sampling](http://en.wikipedia.org/wiki/Gibbs_sampling)) to sample your sequence, as long as you can calculate the desired probability for the entire sequence (or a function that is *proportional* to the probability). As I understand you, you wish to let the probability of $a$ coming before $b$ be set to the odds $a\mathop{:}b$. If all such decisions were independent, you could simply multiply the probabilities (derived from the odds) over all the pairs—but of course they're not. This might be a good enough approximation of what you're after, though, depending on what the application is.

Anyway, once you have your probability function $f(s)$ (defined over the entire sequence $s$), an application of the Metropolis algorithm (a special case of Metropolis-Hastings) would be something like this:

1. Start with an arbitrary ordering $s$.
2. Generate a different ordering, $s'$, for example by randomly swapping two elements.
3. Compute the acceptance ratio $\alpha = f(s')/f(s)$.
4. If $\alpha \geq 1$, accept $s'$, that is, use it instead of $s$ for the next iteration. Go to 2.
5. Otherwise, accept $s'$ with a probability $\alpha$. Go to 2.

And then you let this run for “a while”—exactly how long would depend on the length of your sequence (though the number of iterations should be on the order of the autocorrelation of the Markov process; you can probably find more details on this in a good book on Monte Carlo methods).


---

