[Java] Random kleur behalve één in O(1) tijd

[dtech]

Hallo,

ik ben een puzzeltje aan het oplossen, de restricties zijn als volgt:
- Je hebt een enum met 3 kleuren (rood, groen, blauw). Je hebt een kleur en wilt random een van de andere terugkrijgen.
- Je moet gebruik maken van het java Collections framework
- Het moet in O(1) tijd

Ik heb al uitgesloten dat het een (Array)List, LinkedList, Binary Tree of HashMap is. Het komt er eigenlijk dus op neer: wat is er nog meer? (behalve dan misschien P-Queue)

Een stukje code dat ik al heb zonder Collections:

code:

private static Color randomOther(Color excluded) {
    Random rng = new Random();
    ShapeColor[] values = values();
    // Get the last value and replace the "excluded" one
    values[excluded.ordinal()] = values[values.length-1];
    // Return a value from the array, except the last entry (but since the last replaced the excluded this works)
    return values[rgn.nextInt(values.length-1)];
}

Iemand een idee?

[MSalters]

Gezien het feit dat je inputgrootte O(1) is, is elke oplossing automatisch O(1).

[Dooievriend]

MSalters schreef op woensdag 07 juli 2010 @ 14:11:
Gezien het feit dat je inputgrootte O(1) is, is elke oplossing automatisch O(1).

Los daarvan, laten we even aannemen dat de grootte van je orde het aantal kleuren is. Dus als je bijvoorbeeld een Arraylist neemt, daar N kleuren in stopt, en dan een random getal tussen 0 en N-1 genereert, dan heb je al een basisprogrammaatje dat in O(1) een random kleur genereert. Immers, al heb je duizend kleuren, je programma zal er niet langer door draaien.

Nu komt de eis dat de kleur niet één vooraf aangegeven kleur mag zijn. Na het genereren van het random getal R (tussen 0 en N-1) ga je dus de kleur uit de Arraylist op plaats R halen. Indien deze kleur de meegegeven kleur is, genereer je nieuw getal R' en doe je hetzelfde. Dit geeft een oplossing voor het probleem, maar niet snel genoeg. Worst case krijg je zelfs geen oplossing: indien je random getal toevallig steeds de reeds meegegeven kleur teruggeeft. Dit is dus O(oneindig). Nog niet perfect dus.

Goed, we denken door. Deze keer genereren we een random getal S tussen 0 en N-2. Indien op de S^de plaats in de Arraylist de reeds meegegeven kleur zit, geef je in de plaats de kleur op plaats N-1 terug. Aangezien dit ten hoogste twee keer een kleur opvraagt, onafhankelijk van het aantal kleuren, zal je programma dus in O(1) werken. Anders gezegd, het programma doet er bij een hoger aantal kleuren niet langer over.

Merk bovendien op dat de kans voor elke kleur uniform verdeeld blijft. Dit aantonen mag je nog zelf uitvissen

Wat ik dus niet begrijp is wat je datastructuur (Arraylist of Hashmap ofzo) te maken heeft met dit probleem. Het probleem zit in het theoretisch oneindig lang genereren van random getallen, niet in het doorzoeken van een datastructuur...

[.oisyn]

dtech schreef op woensdag 07 juli 2010 @ 13:43:
Een stukje code dat ik al heb zonder Collections:

code:

private static Color randomOther(Color excluded) {
    Random rng = new Random();
    ShapeColor[] values = values();
    // Get the last value and replace the "excluded" one
    values[excluded.ordinal()] = values[values.length-1];
    // Return a value from the array, except the last entry (but since the last replaced the excluded this works)
    return values[rgn.nextInt(values.length-1)];
}

Iemand een idee?

Je algo is niet O(1) (nou ja, eigenlijk wel om de reden die MSalters al aangaf, maar als we even uitgaan van een variabel aantal kleuren) omdat je elke keer een array moet constructen. Sowieso hoef je die swap niet uit te voeren, je kunt een random getal tussen 0 en N-1 genereren, en als dat getal gelijk is aan de index van de te excluden kleur dan pak je de laatste ipv die kleur. Nou is dit op zich nog niet zo'n hele belangrijke optimalisatie, maar het betekent wel dat je de array nooit aan hoeft te passen zodat je die kunt cachen. Elke keer een nieuwe RNG constructen lijkt me bovendien ook niet bijzonder handig. Niet voor de performance, maar ook niet voor de distributie.

Dus, mijn aanpassingen:

Java:

private static Color randomOther(Color excluded) {
    static Random rng = new Random();
    static ShapeColor[] values = values();

    // choose a random color, excluding the last color
    int ordinal = rng.nextInt(values.length - 1);

    // if chosen color is excluded color, take the last color
    if (ordinal == excluded.ordinal())
        ordinal = values.length - 1;

    return values[ordinal];
}

[ Voor 21% gewijzigd door .oisyn op 07-07-2010 14:53 ]

[Remus]

Misschien iets als

Java:

List<Color> colors = Arrays.asList(Color.values());
Random rng = new Random();

public Color randomColor(Color excluded) {
  int idx = random.nextInt(colors.size() - 1); // -1 because we exclude one of the items in range
  if (idx >= excluded.ordinal()) {
    idx++;
  }
  return colors.get(idx);
}

[dtech]

Nog even een toelichting over het O(n): natuurlijk is het altijd O(1) omdat je een max aantal kleuren hebt. Bedoeling is echter wel dat het niet significant langzamer werkt bij zeg 10.000 kleuren dan bij 3 kleuren.

@Remus
dat is inderdaad een goede oplossing, wel ongeveer gelijkend aan de mijne. Het probleem is dus echter dat de oplossing in een van de Java Collections zou moeten zitten.

@.oisyn
Nu heb je een (klein) probleem: color[n-1] heeft nu 2 keer zoveel kans als de rest. Dit is wel op te lossen, dan krijg je zoiets als Remus heeft

[Janoz]

Misschien ben ik wel net wat te naief, maar het gaat om een puzzel en in de omschrijving heeft men het over 3 kleuren. Vervolgens moet er in O(1) random een andere kleur gekozen worden.

Het eerste dat bij mij naar boven komt is een circulaire double linked list (waarbij de next van het laatste element weer naar de eerste wijst). Je kiest dan random gewoon of de vorige, of de volgende.

--edit--

Bedoeling is echter wel dat het niet significant langzamer werkt bij zeg 10.000 kleuren dan bij 3 kleuren.

Nergens in de opdracht staat dat het algoritme ook voor 10.000 kleuren zou moeten werken .

[ Voor 22% gewijzigd door Janoz op 07-07-2010 15:16 ]

[dtech]

@Janoz
dat werkt inderdaad voor 3 kleuren, maar niet (uniform verdeeld) voor meer kleuren.

[ Voor 6% gewijzigd door dtech op 07-07-2010 15:15 ]

[.oisyn]

dtech schreef op woensdag 07 juli 2010 @ 15:13:
@.oisyn
Nu heb je een (klein) probleem: color[n-1] heeft nu 2 keer zoveel kans als de rest. Dit is wel op te lossen, dan krijg je zoiets als Remus heeft

Ik ben uitgegaan van het feit dat jouw code klopte. Ik ken de exacte implementatie van Java's Random class niet, maar aangezien jij rgn.nextInt(values.length-1) deed ging ik er vanuit dat die functie een getal tussen 0 (inclusief) en values.length-1 (exclusief) retourneerde. Als jij nu beweert dat dat niet zo is dan klopt jouw originele code ook niet.

.edit: en dat klopt idd ook: http://java.sun.com/j2se/.../Random.html#nextInt(int). Jouw bewering is dus incorrect. Remus' code is een variant op de mijne, alleen roteert hij de lijst met kleuren na de te excluden kleur. Uiteindelijk maakt dat natuurlijk geen zak uit aangezien de distributie toch uniform is.

Grappig trouwens dat je beweert dat bij mij een kleur 2x kan voorkomen terwijl je denkt dat dat bij Remus niet het geval is, terwijl we beide N-1 als parameter voor de nextInt() geven

[ Voor 30% gewijzigd door .oisyn op 07-07-2010 15:28 ]

[Remus]

dtech schreef op woensdag 07 juli 2010 @ 15:13:
Nog even een toelichting over het O(n): natuurlijk is het altijd O(1) omdat je een max aantal kleuren hebt. Bedoeling is echter wel dat het niet significant langzamer werkt bij zeg 10.000 kleuren dan bij 3 kleuren.

@Remus
dat is inderdaad een goede oplossing, wel ongeveer gelijkend aan de mijne. Het probleem is dus echter dat de oplossing in een van de Java Collections zou moeten zitten.

Je stelde alleen dat er gebruik gemaakt moest worden van het Collection Framework, niet dat de oplossing in het framework moet zitten, en dat lijkt mij eigenlijk ook wel sterk. Tenzij de oplossing echt alleen voor 3 stuks moet werken, dan is de oplossing van Janoz mogelijk.

@.oisyn
Nu heb je een (klein) probleem: color[n-1] heeft nu 2 keer zoveel kans als de rest. Dit is wel op te lossen, dan krijg je zoiets als Remus heeft

De oplossing van .oisyn is equivalent aan de mijne, behalve - naast mijn gebruik van het Collection Framework - dat ik de geretourneerde index verschuif, en dat .oisyn de Color op de laatste index substitueert indien de gevonden Color de excluded is. NB: Random.nextInt(int) is exclusief de upper limit!

BTW: een mogelijk andere oplossing is:

Java:

Random rng = new Random();
public Color randomColor(Color excluded) {
  EnumSet<Color> colorSet = EnumSet.complementOf(EnumSet.of(excluded));
  List<Color> colorList = new ArrayList<Color>(colorSet);
  return colorList.get(rng.nextInt(colorList.size());
}

[.oisyn]

Die is O(n)
.edit: of heeft een EnumSet de restrictie dat je nooit meer dan 64 enum waardes mag hebben?

[ Voor 80% gewijzigd door .oisyn op 07-07-2010 16:16 ]

[lolcode]

Blijft het aantal kleuren na het starten van het programma constant? Kweet niet of deze al genoemd is, maar komt-ie:
Maak een array met de kleuren, kies een x = random(0,array.length-2) index, en vooordat je de Color returnt swap je positie x met positie array.length-1 (laatste element dus). De volgende keer dat je deze functie aanroept krijg je dus weer een andere kleur terug.

Array index opzoeken is O(1), array "swappen" kan in O(1), dus lijkt me in O(1)?

En nu in (pseudo)code:

Java:

int aantal = #kleuren;
Color[] kleuren = new Color[aantal];

private Color randomKleur(){
    int x = (int)(Math.random()*(aantal-2));
    Color result = kleuren[x];
    kleuren[x] = kleuren[aantal-1]; //swap
    kleuren[aantal-1] = result;
    return result;
}

Edit @ .oisyn hieronder: al de halve dag met een tentamen leren bezig zijn en dat dit even tussendoor doen was toch niet echt een goed idee...ik had het topic zelfs doorgelezen, kun je nagaan

[ Voor 10% gewijzigd door lolcode op 07-07-2010 16:47 ]

[.oisyn]

Kweet niet of deze al genoemd is

Newsflash: als je de topic doorleest voor je post weet je dat wél.

[ Voor 54% gewijzigd door .oisyn op 07-07-2010 16:34 ]

[dtech]

.oisyn schreef op woensdag 07 juli 2010 @ 15:24:
[...]

Ik ben uitgegaan van het feit dat jouw code klopte. Ik ken de exacte implementatie van Java's Random class niet, maar aangezien jij rgn.nextInt(values.length-1) deed ging ik er vanuit dat die functie een getal tussen 0 (inclusief) en values.length-1 (exclusief) retourneerde. Als jij nu beweert dat dat niet zo is dan klopt jouw originele code ook niet.

Klopt, het foutje dat ik bij het lezen van je code maakte was dat ik dacht dat je zoiets deed:

code:

if(value == forbidden){
    value = value-1;
}

En dan zou de random natuurlijk inclusief de allerlaatste moeten zijn, dan heb je wel die 2x kans. Maar dat is dus niet het geval

[dtech]

Bedoeld was de EnumSet. Maar die is eigenlijk ook maar O(1/64*n)...

[prototype]

dtech schreef op woensdag 07 juli 2010 @ 22:40:
Bedoeld was de EnumSet. Maar die is eigenlijk ook maar O(1/64*n)...

Bij big O notation mag je de constante factor weghalen aangezien het er niet echt toe doet over oneindig groter wordende n ;-), dus ipv O(1/64 * n) mag je ook O(n) schrijven. Je beschrijft immers asymptotisch gedrag.

Verder, hoe kom je aan de 1/64 in O(1/64 * n) ? Ik vermoed dat je de 64 hebt afgeleid uit het feit dat het geimplementeerd is met bitvectoren en dat er in een 64 bits woord 64 elementen zouden kunnen zitten. Maar operaties als contains etc... kunnen volgens mij gewoon in constante tijd met bitwise operatoren (in best case), worst case zul je alle 64 bits woorden w.s. af moeten gaan in lineaire tijd. Een complementOf kan b.v. in constante tijd als je 't bij 64 kleuren zou houden op 64 bits, maar bij b.v. 128 kleuren zou je 2x zoveel tijd nodig kunnen hebben, en bij 256 dan 4x zoveel etc... Dit schaalt gewoon lineair op, en ik kom op O(n) als worst case.

[ Voor 10% gewijzigd door prototype op 07-07-2010 23:39 ]

[.oisyn]

Het ging om

Java:

EnumSet.complementOf(EnumSet.of(excluded));

Dat is O(n), je hebt n/64 (of n/32 ofzo) ints die gezet en gecomplementeerd moeten worden.

[dtech]

Ja, daarom vond ik het ook zo vaak. Maar de argumentatie van degene die het verzonnen had is dat je toch nooit enums hebt met meer dan 64 velden... ofzo...

Maar dan vind ik de andere implementaties (die dus al gegeven waren) beter, die zijn echt /altijd/ O(1)

Ik vind het ook een beetje vaag, zoals ik als zei dat het eigenlijk ook maar O(1/64*n) was.

[prototype]

.oisyn schreef op woensdag 07 juli 2010 @ 23:46:
Het ging om

Java:

EnumSet.complementOf(EnumSet.of(excluded));

Dat is O(n), je hebt n/64 (of n/32 ofzo) ints die gezet en gecomplementeerd moeten worden.

Mijn punt/vraag was eerder: Dat setten en complementeren gaat toch niet serieel binnen 1 woord? Kan de CPU / implementatie dat niet in 1 operatie? Ik weet niet hoe bitwise operatoren geimplementeerd zijn in de CPU, maar volgens mij is dat gewoon 1 operatie met bitwise OR (setten) en bitwise NOT voor complement. Dan maakt het volgens mij geen moer uit hoeveel bits je in die woord wil setten/complementeren aangezien dat gewoon in constante tijd gaat :-)

[ Voor 32% gewijzigd door prototype op 08-07-2010 00:55 . Reden: Unsetten -> complementeren ]

[.oisyn]

Natuurlijk wel, maar je hebt toch niet altijd maar 1 word? Je hebt er ceil(N/32), die allemaal aangemaakt moeten worden, en vervolgens gecomplementeerd. Je zou de complementOf eventueel kunnen bypassen en direct beginnen met N/32 words op 0xffffffff waar je de juiste bit eruit filtert, maar nog steeds heb je dan N/32 words die eerst op 0xffffffff geinitialiseerd moeten worden. En vervolgens wordt daar weer een array van Colors van gemaakt, waardoor elke individuele bit dus weer afgelopen moet worden.

[ Voor 14% gewijzigd door .oisyn op 08-07-2010 00:55 ]

[prototype]

.oisyn schreef op donderdag 08 juli 2010 @ 00:55:
Natuurlijk wel, maar je hebt toch niet altijd maar 1 word? Je hebt er ceil(N/32), die allemaal aangemaakt moeten worden, en vervolgens gecomplementeerd. Je zou de complementOf eventueel kunnen bypassen en direct beginnen met N/32 words op 0xffffffff waar je de juiste bit eruit filtert, maar nog steeds heb je dan N/32 words die eerst op 0xffffffff geinitialiseerd moeten worden. En vervolgens wordt daar weer een array van Colors van gemaakt, waardoor elke individuele bit dus weer afgelopen moet worden.

Nee, dat snap ik dat het over meerdere woorden kan gaan (zie mijn eerste reactie in dit topic), maar ik snap nu ook waar jullie die fraction vandaan halen; jullie baseren n op het aantal kleuren, ik dus later in mijn verhaal op het aantal woorden... daar zat het verschil in denken in. ;-)

[voodooless]

In feite wil je at random een index in een array uitzoeken, behalve een specifieke index. Dan genereer je een random getal van 0 tot (lengte-2). Dan tel je dat getal op bij de index die niet wil gebruiken, doe nog even modulus lengte, en je bent klaar

[.oisyn]

Ja dat is nu al 3x gezegd, maar dan in iets andere bewoordingen (zoals, als je dat element kiest die verwisselen met de laatste, of als je grotergelijk als de te excluden index kiest er 1 bij optellen)

[voodooless]

.oisyn schreef op donderdag 08 juli 2010 @ 12:06:
of als je grotergelijk als de te excluden index kiest er 1 bij optellen)

Dan is de random verdeling niet meer uniform. De kans dat je exclusion index +1 krijgt is groter omdat deze afgevangen wordt door twee getallen.

[Soultaker]

Ik denk dat je .oisyn's algoritme verkeerd begrepen hebt. Voor een lijst met N getallen (indices 1..N) en een uitgesloten element met index K, kiest hij een getal i uit 1..(N-1), en als i == K, dan i = N. Remus doet precies hetzelfde, behalve dat hij i = i + 1 als i >= K doet. In beide gevallen hebben alle indices (behalve K) gelijke kans om gekozen te worden (onder de aanname dat de uniform random selectie van i goed gaat, wat in het begin dus mis ging).

Feitelijk komt het er op neer dat beiden selecteren uit een lijst waar het uitgesloten element uit verwijderd is, zonder daadwerkelijk het element uit de lijst te halen. Het verschil is dan dat Remus het element gewoon uit het midden haalt, maar .oisyn 'm eerst naar het einde swapt en vervolgens vanuit daar verwijderd. Het lijkt me dat beide methoden prima zijn.

Dit is een van die problemen die je, als je wat langer programmeert, vanzelf een keer tegenkomt en oplost. Ik zelf kies altijd voor de variant van Remus, die mij blijkbaar intuïtiever voorkomt, maar .oisyn's variant is net zo goed.

[ Voor 12% gewijzigd door Soultaker op 08-07-2010 12:35 ]

[voodooless]

* voodooless moet meer tijd nemen om alle tekst te lezen

[Janoz]

Soultaker schreef op donderdag 08 juli 2010 @ 12:32:
Feitelijk komt het er op neer dat beiden selecteren uit een lijst waar het uitgesloten element uit verwijderd is, zonder daadwerkelijk het element uit de lijst te halen. Het verschil is dan dat Remus het element gewoon uit het midden haalt, maar .oisyn 'm eerst naar het einde swapt en vervolgens vanuit daar verwijderd. Het lijkt me dat beide methoden prima zijn.

Remus zijn methode is intuïtiever. .oisyns methode heeft een micro optimalisatie doordat de kans dat de extra bewerking uitgevoerd moet worden van gemiddeld 1/2 naar 1/N. Op zich herken je daaraan wel een beetje de 'normale' programmeur tegenover de 'realtime-restricted' programmeur.

[.oisyn]

Leuk bedacht, maar dat is hier niet van belang . De laatste pakken als i == k is feitelijk hetzelfde als 1 iteratie Knuth Shuffle zonder dat je daadwerkelijk array elementen swapt. In plaats van de array elementen zelf te swappen reassign je de index. Zie ook het stukje code in de topicstart. Gezien de bekendheid van de Knuth Shuffle vind ik mijn oplossing daarom intuitiever, maar het is natuurlijk maar net wat je gewend bent.

Op optimalisatieniveau heb ik er nog niet eens over nagedacht en het lijkt me bovendien een wassen neus. Wat intel hardware betreft, een goede implementatie doet niet eens een branch maar gebruikt een CMOVcc in mijn geval of een SETcc gevolgd door een ADD in Remus' oplossing. Met branching moet je rekening houden met het feit dat bij een vooruit-branch de branch predictor standaard de branch niet neemt, waardoor Remus' oplossing gemiddeld voordeliger is, tenzij je zoiets doet:

GAS:

    CMP i, k
    JE reassign
    JMP done
reassign:
    MOV i, N-1
done:

[ Voor 58% gewijzigd door .oisyn op 08-07-2010 13:25 ]

[Soultaker]

Janoz schreef op donderdag 08 juli 2010 @ 13:10:
Remus zijn methode is intuïtiever.

Vond ik ook, maar wat "intuïtief" is hangt natuurlijk van je achtergrond en je intuïtie. Ik vermoed dat als .oisyn een element uit een vector wil gooien hij iets als swap(v[k], v.back()); v.pop_back(); schrijft (want dat is efficiënter dan v.erase(v.begin() + k); als je de volgorde niet hoeft te behouden) en dan is zijn oplossing eigenlijk heel logisch.

.oisyns methode heeft een micro optimalisatie doordat de kans dat de extra bewerking uitgevoerd moet worden van gemiddeld 1/2 naar 1/N. Op zich herken je daaraan wel een beetje de 'normale' programmeur tegenover de 'realtime-restricted' programmeur.

Voor zover een enkele increment instructie relevant is ten opzichte van het genereren van een beetje zinnig pseudo-random getal natuurlijk. Het lijkt me echt een optimalisatie van niets, eerlijk gezegd. Verder ga je voor real-time programmeren uit van de worst-case en die treedt in beide gevallen op als i==k of i >= k.

[.oisyn]

Ik denk niet dat Janoz met realtime de daadwerkelijke betekenis van realtime (namelijk dat je tijdsgaranties kunt doen) bedoelt, maar eerder "realtime" zoals in games. Overigens klopt je vermoeden helemaal

C++:

void Scene::RemoveEntity(SceneEntity * pEntity)
{
    CDC_ASSERT_CODE(pEntity->m_entityIndex >= 0);
    int i = pEntity->m_entityIndex;
    m_entities[i] = m_entities[m_entities.size() - 1];
    m_entities[i]->m_entityIndex = i;
    m_entities.pop_back();
}

Alleen geen swap, maar die is in dit geval ook nutteloos. Bij dure objecten die je goedkoop kunt swappen (zoals bijv. een std::vector) wil je dat natuurlijk wel.

[ Voor 62% gewijzigd door .oisyn op 08-07-2010 15:18 ]

[Soultaker]

Ah inderdaad, std::swap() is vooral nuttig voor types waarvoor std::swap() gespecialiseerd is.

Trouwens, als je het op assembly niveau wil optimaliseren kan je het ook schrijven zonder conditional moves:

GAS:

CMP i, k
SBB i, -1

Maar geen compiler die die code verzint (vermoed ik). Overigens genereert GCC voor .oisyn's versie wel twee één instructies minder, maar ik denk niet dat je daar in de praktijk veel mee wint.

[ Voor 34% gewijzigd door Soultaker op 08-07-2010 16:00 ]

[Remus]

.oisyn schreef op woensdag 07 juli 2010 @ 23:46:
Het ging om

Java:

EnumSet.complementOf(EnumSet.of(excluded));

Dat is O(n), je hebt n/64 (of n/32 ofzo) ints die gezet en gecomplementeerd moeten worden.

Gezien de opmerking op de JavaDoc zou ik verwachten dat dit ook O(1) is (iig de complement):

Implementation note: All basic operations execute in constant time. They are likely (though not guaranteed) to be much faster than their HashSet counterparts. Even bulk operations execute in constant time if their argument is also an enum set.

Maar mogelijk is de creatie van de EnumSet zelf O(n).

[.oisyn]

Dat kan alleen als het aantal words vast staat. Daarentegen zijn gedefinieerde compiler limits ook niet vreemd, ik weet niet hoe het met Java zit maar ze kunnen best gedefinieerd hebben dat een compliant compiler nooit meer dan, weetikveel, 256 enum waardes voor een enkele enum hoeft te supporten. Als dat zo is dan gebruik je in code ook gewoon een fixed length array van words en dan is het constante tijd. Met een grote constante

[ Voor 3% gewijzigd door .oisyn op 08-07-2010 18:01 ]

[Soultaker]

Voor wie zin heeft in een uitdaging, een uitgebreider puzzeltje gebaseerd op hetzelfde principe. Stel dat je een getal uit [0..N) moet kiezen, waarbij er niet één uitgesloten getal is, maar een lijst K met lengte |K| < N. Verder zijn de getallen verschillend en binnen bereik [0..N) (formeel: 0 <= K_i < N, en K_i == K_j iff i == j). Geef een algoritme dat in O(|K|) tijd en ruimte een uniform random getal uit [0..N)\K oplevert. Pseudo-code is acceptabel; je kunt er vanuit gaan dat er een functie is om een uniform random integer te genereren uit een gewenst bereik.

Twee varianten:

• Makkelijk: de getallen in K zijn gesorteerd (K_i < K_j iff i<j).
• Moeilijk: de getallen in K staan in willekeurige volgorde.

Merk op dat het probleem van de TS een speciek geval is met K=1.

[ Voor 24% gewijzigd door Soultaker op 09-07-2010 20:18 ]

[user109731]

Te warm om te slapen, dus toch maar een oplossing voor de moeilijke:

spoiler:

[code]
randmin = len(K)
available = [True] * len(K)
for x in K:
if x < randmin:
available[x] = False
c = 0
alt = [0] * len(K)
for i, x in K:
if x >= randmin:
while not available[c]:
c += 1
alt[i] = c
c += 1
r = randint(randmin, N-1)
for i, x in K:
if x == r:
return alt[i]
return r
[/code]

Kunnen wat foutjes inzitten, maar het idee klopt volgens mij

[Soultaker]

Yep, lijkt me prima! Komt in grote lijnen overeen met wat ik zelf bedacht had. Ben benieuwd of er nog iemand iets heel anders verzint.

(Blijft jammer dat die code-tags binnen spoiler-tags niet werken trouwens.)

[ Voor 3% gewijzigd door Soultaker op 10-07-2010 07:26 ]

[user109731]

Hm idd, tijd voor de [collapse] tag Je kunt ook op "View" klikken om de code goed te zien.

Ik ben ook wel benieuwd naar een andere oplossing. Met K ongesorteerd kun je alleen heel weinig in O(K) tijd en geheugen vrees ik, maar wie weet

Wel leuk zo'n uitdaging, voor herhaling vatbaar.

[ Voor 7% gewijzigd door user109731 op 10-07-2010 11:27 ]