4 ms·
Related: given a permutation of numbers 0..999, find out the position of a given number (e.g. number 5). It may seem that on average, you need 500 iterations. I
by resource0x 8y ago
Related: given a permutation of numbers 0..999, find out the position of a given number (e.g. number 5). It may seem that on average, you need 500 iterations. In fact, you need much less:
let index = 5;
while (element[index] != 5) index = element[index];
- pavel_lishin 8y ago> In fact, you need much less How many iterations does that take on average? And why?
- resource0x 8y agosee https://math.stackexchange.com/questions/1409862/average-length-of-a-cycle-in-a-n-permutation https://math.stackexchange.com/questions/1409862/average-len... Which gives you 1000/7.48, not 1000/2
- saagarjha 8y agoThis seems to tend to 500 when I run this experimentally.
- resource0x 8y agoIndeed. Never tested it before, took the article in stackexchange for granted.
- deleted 8y ago[deleted]