• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 17:27
CET 23:27
KST 07:27
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #238[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over2Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Team Liquid Map Contest #23 No more SC2 streamers on team liquid? Dark completes military service, returns to SC2 Weekly Cups (Nov 9-15): Clem and herO take over StarCraft open world shooter announced at BlizzCon
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion NaDa's Body List of top players active on ShieldBattery Light introduces ShieldBattery on his YouTube
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [Megathread] Daily Proleagues [BSL23] Ro16 Group D - Sunday 21:00 CET [BSL23] Ro16 Group B - Saturday 21:00 CET
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Warcraft III: The Frozen Throne Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
Trading/Investing Thread US Politics Mega-thread Artificial Intelligence Thread Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 12447 users

Math/Computer Science Problem

Blogs > Slithe
Post a Reply
Slithe
Profile Blog Joined February 2007
United States985 Posts
Last Edited: 2008-01-22 23:20:36
January 22 2008 23:17 GMT
#1
You have a list of unknown size N, that you are only allowed to traverse once. The goal is to devise a method to create a set of size K that is random and uniformly distributed among all the possible subsets of N that are size K. What is the method?

Remember:
1) You do not know N. Your answer should not rely on N, i.e. your memory size should not be based on N in any way.
2) You can only traverse the list once.
3) K is less than or equal to N, so there is always at least one possible set.

*****
Asta
Profile Joined October 2002
Germany3491 Posts
January 22 2008 23:39 GMT
#2
I'm too tired to think it through but will the 'picks' be evenly distributed if you choose the first K elements and then (if N > K) eliminate a random (evenly distributed) element of the K+1 (the old picks and the next one on the list)?
I think not... :D Because the first ones will be much likelier to be discarded than the last ones. Which brings us back to the initial problem that you don't know to what degree you have to favor the first ones because it depends on N. Hum...
Cascade
Profile Blog Joined March 2006
Australia5405 Posts
January 23 2008 00:31 GMT
#3
Yeah, that's how you must do it. Up to K you obvioulsy have to pick all elements to your set. When you run through the n:th element (n>K), you use it to replace a random element in your previous set of K elements with a probability K/n. Leave the set unchanged with prob (n-K)/n. Use induction to prove that it works.
zdd
Profile Blog Joined October 2004
1463 Posts
Last Edited: 2008-01-23 02:49:19
January 23 2008 00:31 GMT
#4
I think it would be something like this:
let's say n is an array of ascending integers, k is an int, set_k is an empty array

the set n would be distributed something like this: [1 - k][k+1 - 2k][2k+1 - 3k]...
i=0;
for each $element in n {
if(i<k){
if(random(1,k)=k){
$set_k[i]=$element;
i++;
}
}
}

I dunno, statistically each element in n would have a 1/k chance to become an element in set_k, so I guess in every k elements in set n there should only be around 1 element that goes into set k.

edit: oh nvm, maybe you could just copy set "n" to set "set_k", then remove random elements from set_k until length(set_k) is equal to K

int K = <some value>;
int i=0;
int[] set_k;
for each $element in n {
set_k[i]=$element;
i++;
}
while(length(set_k) != K) {
delete(set_k[random(0, length(set_k))]);
}
output set_k

edit2: cascade's idea is different, because he uses k+1 memory instead of n
it would be implemented something like:
int K = <some value>;
int i=0;
int[] set_k;
function randomkn(k, n){ //run random(1,n) k times
$var=false;
while (k>0){
k--;
if (random(1, n) == n){$var=true;}
}
return $var;
}
for each $element in n {

if (i<K+1){
set_k[i]=$element;
i++;
}

else if (randomkn(K, length(n))) {
set_k[random(0,K+1)]=$element;
}

}
output set_k
All you need in life is a strong will to succeed and unrelenting determination. If you meet these prerequisites, you can become anything you want with absolutely no luck, fortune or natural ability.
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2008-01-23 01:37:02
January 23 2008 01:30 GMT
#5
zdd, your second algorithm isn't O(1) or O(K) memory, it's O(n) memory, which breaks the problem constraints.

I'm not sure if I follow your first one.

I think the actual solution has something to do with finding the probability that the nth element should be included in the set, given k.

Obviously (at least to me, I could be wrong), the first element should be selected with (N/K) probability. Then, k := K - 1 if the first element was selected, and n := N - 1 , and repeat for the rest of the elements. This is guaranteed to return K elements.

There might seem to be a problem with the later elements (especially the last element) having a higher than (N/K) probability to be selected, but I think this is not the case. For the last L elements to always be selected, (n/k == 1) must hold. However, the probability of this happening is quite small if N is large (unless K is equally large).

I'm too lazy to calculate it myself (OK, I'm too stupid to do it), but I think if you go through with it, you'll find that the probability that the last L elements are arrived at with (k==n) is the same as 1 minus the probability that they are arrived at with (k==0).

Oh, shit, you don't know N. My idea is bunk.
Compilers are like boyfriends, you miss a period and they go crazy on you.
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
January 23 2008 01:35 GMT
#6
Yeah, I think that Cascade's idea will work. Your memory space is O(K), not O(N), so it's fine.
Compilers are like boyfriends, you miss a period and they go crazy on you.
Slithe
Profile Blog Joined February 2007
United States985 Posts
January 23 2008 02:41 GMT
#7
Yes Cascade has the right answer. Good job! I'll be posting up a significantly more difficult problem now, which I actually don't quite know the answer to, but I have a basic idea.

Regarding this problem:
Basically, since you don't know how many elements are in the list, you have to make sure at each iteration through the list, all elements up to that iteration have an equal probability, k/i, of being in the set, where "i" is the current index. If you work around that idea, then the answer comes more easily, or at least for me it did.

For Asta's answer: The key there was that you don't always discard. It seems that you already realized the problem, so you probably would have realized the fix eventually.

For zdd's answers:
The first one is incorrect because, all elements will have probably 1/k of being in the set until the set is full, and then the next elements have probability 0. In the first place, 1/k is incorrect, and the correct probability to aim for is k/i.
The second one, BottleAbuser pointed out the problem, which is that you require O(n) memory, which is not allowed.
Please log in or register to reply.
Live Events Refresh
Next event in 33m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
SpeCial 67
Nathanias 53
EmSc Tv 28
StarCraft: Brood War
Bishop 42
LuMiX 0
Dota 2
Gorgc6894
BananaSlamJamma316
monkeys_forever310
Counter-Strike
pashabiceps1834
Fnx 1234
Heroes of the Storm
Liquid`Hasu516
Trikslyr56
Other Games
summit1g5939
tarik_tv5074
Grubby2189
Liquid`RaSZi2100
FrodaN1448
shahzam440
B2W.Neo308
C9.Mang0153
PiGStarcraft32
Organizations
StarCraft 2
EmSc Tv 28
EmSc2Tv 28
[ Show 15 non-featured ]
StarCraft 2
• musti20045 26
• Hupsaiya 24
• davetesta5
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV724
League of Legends
• Stunt320
Other Games
• imaqtpie743
• Shiphtur672
Upcoming Events
Replay Cast
33m
University League
11h 33m
GSL
13h 3m
Maru vs Dark
Patches Events
15h 33m
OSC
17h 33m
Replay Cast
1d
KCM Race Survival
1d 11h
Ultimate Battle
1d 13h
ZerO vs Bisu
RSL Revival
2 days
BSL
2 days
eOnzErG vs StRyKeR
Cross vs JDConan
[ Show More ]
RSL Revival
3 days
IPSL
3 days
Ret vs ggnore13
nOmaD vs Aether
BSL
3 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
4 days
WardiTV Weekly
4 days
Kung Fu Cup
5 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
6 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.