Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You are looking for a <a href="http://en.wikipedia.org/wiki/Derangement" rel="noreferrer">derangement</a> of your entries.</p> <p>First of all, your algorithm works in the sense that it outputs a random derangement, ie a permutation with no fixed point. However it has a enormous flaw (which you might not mind, but is worth keeping in mind): <strong>some derangements cannot be obtained with your algorithm</strong>. In other words, it gives probability zero to some possible derangements, so the resulting distribution is definitely not uniformly random.</p> <p>One possible solution, as suggested in the comments, would be to use a rejection algorithm:</p> <ul> <li>pick a permutation uniformly at random</li> <li>if it hax no fixed points, return it</li> <li>otherwise retry</li> </ul> <p>Asymptotically, the probability of obtaining a derangement is close to <code>1/e</code> = 0.3679 (as seen in the wikipedia article). Which means that to obtain a derangement you will need to generate an average of <code>e</code> = 2.718 permutations, which is quite costly.</p> <p>A better way to do that would be to reject <em>at each step</em> of the algorithm. In pseudocode, something like this (assuming the original array contains <code>i</code> at position <code>i</code>, ie <code>a[i]==i</code>):</p> <pre><code>for (i = 1 to n-1) { do { j = rand(i, n) // random integer from i to n inclusive } while a[j] != i // rejection part swap a[i] a[j] } </code></pre> <p>The main difference from your algorithm is that we allow <code>j</code> to be equal to <code>i</code>, but only if it does not produce a fixed point. It is slightly longer to execute (due to the rejection part), and demands that you be able to check if an entry is at its original place or not, but it has the advantage that it can produce every possible derangement (uniformly, for that matter).</p> <p>I am guessing non-rejection algorithms should exist, but I would believe them to be less straight-forward.</p> <p><strong>Edit:</strong></p> <p>My algorithm is actually bad: you still have a chance of ending with the last point unshuffled, and the distribution is not random at all, see the marginal distributions of a simulation: <img src="https://i.stack.imgur.com/yblIU.png" alt="marginal distributions"></p> <p>An algorithm that produces uniformly distributed derangements can be found <a href="http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf" rel="noreferrer">here</a>, with some context on the problem, thorough explanations and analysis.</p> <p><strong>Second Edit:</strong></p> <p>Actually your algorithm is known as <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo.27s_algorithm" rel="noreferrer">Sattolo's algorithm</a>, and is known to produce all cycles with equal probability. So any derangement which is not a cycle but a product of several disjoint cycles cannot be obtained with the algorithm. For example, with four elements, the permutation that exchanges 1 and 2, and 3 and 4 is a derangement but not a cycle.</p> <p>If you don't mind obtaining only cycles, then Sattolo's algorithm is the way to go, it's actually much faster than any uniform derangement algorithm, since no rejection is needed.</p>
    singulars
    1. This table or related slice is empty.
    1. POShuffle list, ensuring that no item remains in same position
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USFelixCQ
    1. USFelixCQ
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAre you sure there are some derangements that the OP's algorithm can't generate? I don't see why. I don't know what language that is (Java?), but `Math.random()` looks like a commonly-seen function that returns uniformly distributed floats in the range [0, 1). Given that, each step through the loop should swap `data[i]` with one of the values after it, chosen without bias. This should produce an unbiased derangement, no? What does your graphical simulation say?
      singulars
      1. PO
      1. USTom Zych
    2. COThank you! I just love the word "derangement"; certainly one of the best. mathematical. terms. ever. The fact that I can't generate all the derangements doesn't make any difference to my application, though a nagging voice in my head says, "but you should do it **correctly**."
      singulars
      1. PO
      1. USjdeisenberg
    3. CO@Tom: See my latest edit to see why some derangements cannot be obtained. The simulation shows, at position `i,j`, the probability of entry originally at index `i` to end up at index `j`. The first line is fairly uniform, meaning that the first entry has equal chance of ending anywhere besides the first position. But the last line shows that the last entry has a very high chance of ending at the penultimate position, and a slight chance of remaining in place.
      singulars
      1. PO
      1. USFelixCQ
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload