algorithm - Choosing k out of n -


i want choose k elements uniformly @ random out of possible n without choosing same number twice. there 2 trivial approaches this.

  1. make list of n possibilities. shuffle them (you don't need shuffle n numbers k of them performing first k steps of fisher yates). choose first k. approach takes o(k) time (assuming allocating array of size n takes o(1) time) , o(n) space. problem if k small relative n.
  2. store set of seen elements. choose number @ random [0, n-1]. while element in set choose new number. approach takes o(k) space. run-time little more complicated analyze. if k = theta(n) run-time o(k*lg(k))=o(n*lg(n)) because coupon collector's problem. if k small relative n takes more o(k) because of probability (albeit low) of choosing same number twice. better above solution in terms of space worse in terms of run-time.

my question:

is there o(k) time, o(k) space algorithm k , n?

with o(1) hash table, partial fisher-yates method can made run in o(k) time , space. trick store changed elements of array in hash table.

here's simple example in java:

public static int[] getrandomselection (int k, int n, random rng) {     if (k > n) throw new illegalargumentexception(         "cannot choose " + k + " elements out of " + n + "."     );      hashmap<integer, integer> hash = new hashmap<integer, integer>(2*k);     int[] output = new int[k];      (int = 0; < k; i++) {         int j = + rng.nextint(n - i);         output[i] = (hash.containskey(j) ? hash.remove(j) : j);         if (j > i) hash.put(j, (hash.containskey(i) ? hash.remove(i) : i));     }     return output; }

this code allocates hashmap of 2×k buckets store modified elements (which should enough ensure hash table never rehashed), , runs partial fisher-yates shuffle on it.

here's quick test on ideone; picks 2 elements out of 3 30,000 times, , counts number of times each pair of elements gets chosen. unbiased shuffle, each ordered pair should appear approximately 5,000 (±100 or so) times, except impossible cases both elements equal.


Comments

Post a Comment

Popular posts from this blog

python - Installing PyDev in eclipse is failed -

unable read repository @ http://pydev.sf.net/updates/content.xml. sun.security.validator.validatorexception: pkix path building failed: sun.security.provider.certpath.suncertpathbuilderexception: unable find valid certification path requested target i installing pydev in eclipse using python, doesn't install successfully. gives above error. happened? how solve error? i had error when trying install on laptop behind corporate firewall. couldn't tell setup of firewall, not sure of root cause. i got passed error installing pydev eclipse when out behind firewall. another way got around have eclipse on non-firewalled machine, install pydev eclipse, , copy whole eclipse directory non-firewalled machine firewalled machine. there better way, , way fix properly, didn't have time work out firewall doing. this on windows 7 machine (yeah know) not work *nix versions installed through package manager yum or apt.
Read more

PHP OOP-based login system -

lets building oop-based user authentication system, , incorporate following principles: direct injection, inheritance, encapsulation, polymorphism , single responsibility principle. my background in programming has relied on procedural programming, , thus, finding difficult put these practices correct use. assume have these classes: class config { public function set($key, $value); public function get($key, $default = null); } class user { public function __construct(pdo $dbh, $id = null); public function setprofile(profile $profile); } class auth { public function __construct(config $config); public function login($username, $password, $keeploggedin = true); public function isloggedin(); public function getloggedinuser(); public function logout(); public function register(array $data); } class session { public function start($sessionname = null); public function write($key, $value); public function read($key, $default =...
Read more

c# - Nested Internal Class with Readonly Hashtable throws Null ref exception.. on assignment -

in internal game class , have both a) defined nested internal gamertags class , b) defined gamertags[] _array variable. in internal gamertags class (the nested class, simplicity left out) have readonly hashtable . after initialization, still null ref exception when try assign value. i'm not changing pointer value only , need add initialization hastable? internal class gamertags { private readonly hashtable _privatereadonlyhashtable; private string _json; private string _hash; internal idictionary privatereadonlyhashtable { { return this._privatereadonlyhashtable; } } internal string hash { { this.ensurehash(); return this._hash; } } internal object this[string key] { { return this._privatereadonlyhashtable[k...
Read more