Is there a standard name for the following algorithm? At each step, the code picks an index, remove the object at that index, and remember to never pick that index again. See the following illustration:

removing numbers

Others have suggested the Fisher–Yates shuffle, but it seems like this algorithm is simpler. I found this algorithm useful for many different types of problems. An example use case is, to cycle through 24 hours in a day, by random, without picking the same hour twice.

An index is used to avoid picking the same object twice,

mapping(uint => uint) shufflingIndex;

a counter is used to shrink the list of objects to choose from

uint counter;

and a random number generator is used to select an object.

  • 1
    Sorry but the image isn't at all clear. I have no idea what your question is supposed to be about. The only precise information you've given is a couple of variable declarations, which are about the least important part of the algorithm. – David Richerby Nov 8 at 16:45
  • 2
    I think this is just an implementation of uniform sampling without replacement? But I'm not really sure because as David said it's very hard to tell what is happening. – Stella Biderman Nov 8 at 16:46
  • 3
    Please remove the images and provide concise pseudo code of the algorithm. Since it's super simple that shouldn't be a challenge for you! – Raphael Nov 8 at 18:40

Algorithm P (Shuffling) from Knuth, 1969, similar to the Fisher–Yates shuffle from 1938 though invented independently.

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

The implementation in the question lets each object shuffle itself, adding itself to the list when doing so, whereas the example here from Wikipedia uses a loop.

  • This doesn't seem to be the same as the algorithm sketched in the question: it can pick the same index more than once, but moves elements between indices. – Peter Taylor Nov 9 at 13:58
  • The quoted pseudocode is to produce a random permutation while your algorithm is, as recognized by @StellaBiderman, an implementation of uniform sampling without replacement. The essence of both algorithms are the same. – Apass.Jack Nov 9 at 14:05
  • @PeterTaylor, "it can pick ...", which one is this "it"? – Apass.Jack Nov 9 at 14:07
  • @Apass.Jack, Algorithm P. – Peter Taylor Nov 9 at 16:50

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.