performance - Unique random number algorithm -

-

i algorithm/function that, given number n, generates random numbers 0 n - 1 in constant time. after nth call, function may pleases. also, important algorithm generates numbers when requested rather using shuffling, because may (and in average case do) not need full list of numbers. best approach take?

(optional read) thought of having hash set of numbers, , pulling numbers out 1 @ time, require inserting elements (which not need) hash set first... not work... argh

thanks in advance.

modify fisher–yates shuffle replacing array map stores elements have been moved. in python:

import random class shuffle:     def __init__(self, n):         self.d = {}         self.n = n     def generate(self):         = random.randrange(self.n)         self.n -= 1         di = self.d[i] if in self.d else  # idiomatically, self.d.get(i, i)         dn = self.d[self.n] if self.n in self.d else self.n         self.d[i] = dn         self.d[self.n] = di         return di

the space usage , amortized expected running time o(1) words per element generated. log factors, optimal.


Comments

Post a Comment

Popular posts from this blog

java - How to Configure JAXRS and Spring With Annotations -

-
i working on little spring web service project. here example route: package com.example.api; import javax.ws.rs.get; import javax.ws.rs.path; import javax.ws.rs.produces; import javax.ws.rs.pathparam; import javax.ws.rs.ext.provider; import javax.ws.rs.core.mediatype; @provider public class webserviceroutes { @get @path("/hello") public string health() { return "hello"; } } then in spring configuration class: package com.example.api; import org.springframework.context.annotation.bean; import org.springframework.context.annotation.configuration; @configuration public class springcontextconfiguration { @bean( destroymethod = "shutdown" ) public springbus cxf() { return new springbus(); } @bean public webserviceroutes webserviceroutes() { return new webserviceroutes(); } } and in web.xml: <?xml version="1.0" encoding="utf-8"?> <web-app version=...
Read more

visual studio - TFS will not accept changes I've made to a Java project -

-
i using tfs's team explorer manage visual studio projects. recently, i've created new java project (not in visual studio) manually added tfs using source control control explorer in visual studio. after added java project tfs, made changes , bug fixes. then, went visual studio , opened source control explorer check in changes, tfs thinks no changes made. it seems needed check out project before making changes. guess erroneously expected tfs track automatically, okay. so, using source control explorer in tfs, checked out project, , tried check in pending changes. when tried check in, got following message: all of changes either unmodified files or locks. changes have been undone server. is there way convince server indeed project has changed? how can check in changes have made? thank help.
Read more

php - Create image in codeigniter on the fly -

-
i want create image in codeigniter in simple php using gd functions. have tried following method in controller function image(){ $my_img = imagecreate( 200, 80 ); $background = imagecolorallocate( $my_img, 0, 0, 255 ); $text_colour = imagecolorallocate( $my_img, 255, 255, 0 ); $line_colour = imagecolorallocate( $my_img, 128, 255, 0 ); imagestring( $my_img, 4, 30, 25, "thesitewizard.com", $text_colour ); imagesetthickness ( $my_img, 5 ); imageline( $my_img, 30, 45, 165, 45, $line_colour ); //$this->output->set_content_type('image/png'); header( "content-type: image/png" ); imagepng( $my_img ); imagecolordeallocate( $line_color ); imagecolordeallocate( $text_color ); imagecolordeallocate( $background ); imagedestroy( $my_img ); } if write code in simple php can see in url http://www.domain.com/image.php if run in codeignite...
Read more