[ASP] Array met twintig unieke nummers vullen

[avon]

Voor een aantal scripts ben ik al enige tijd aan het denken over een Array vuller die er voor zorgt
dat een array met grootte x wordt gevuld met unieke niet repeterende nummers

Een voorbeeld bij Array grootte 5
array[0] = 4
array[1] = 1
array[2] = 2
array[3] = 5
array[4] = 3

De volgende code heb ik zelf al uitgedacht

code:

x = gewenste grootte

Loop de array door tot x

    Array[positie] = Nieuwnummer(x+1)

        Do while akkoord = fout

            Loop de array door tot huidge x

                if Array[positie] = Array[e] then

                    Array[positie] = Nieuwnummer(x+1)

                end if

            *

            Volgende                        

        Next    

Volgende

*en hier zit het hem dus... stel dat hij nou niet voorkomt hoe laat ik hem er dan uitspringen?

[ Voor 12% gewijzigd door avon op 03-06-2005 21:55 ]

[Jelmer]

Break

Maar wat sneller is:
Maak een 2e array met als index je integer waarde. Initialiseer alles op 0. Dan kun je dus met O(1) een controle uit voeren ipv O(n). Als de waarde nog 0 is, is ie nog niet gebruikt, bij 1 wel en moet je dus een nieuwe zoeken. (als je het een beetje efficient wil houden pak je niet zomaar een 2e array, maar eentje waarbij je van de elementen alle bits als boolean gebruikt)

[JaWi]

Zonder je aan een specifieke taal te binden kun je het volgende proberen:

1. vul je array gewoon gesorteerd (middels een simpel loopje);
2. pas het Fisher-Yates shuffle algorithme toe, om efficient deze array te shuffelen.

Et voila, een array met unieke waarden in willekeurige volgorde...

Fisher-Yates in pseudo-code (runt in O(n) tijd):

code:

sub FisherYates( input : Array ) : Array
{
  for i : ( input.length .. 0 )
  {
     // pak een willekeurige waarde tussen 0 en i + 1...
     j = random( i + 1 );

     if ( i == j )
       continue;

     // verwissel de waardes van indexen i & j...
     tempI = input[i];
     input[i] = input[j];
     input[j] = tempI;
  }

  return input;
}

[ Voor 45% gewijzigd door JaWi op 03-06-2005 22:16 ]

[avon]

Het duurd even, maar volgens mij begrijp ik wat de Fisher-Yates code uitvoerd.

Hij verwisseld positie's per stuk. Interessant, bedankt.
Ga even deze code proberen te verwerken in een functie in niet pseudo taal.

code:

Function randomnummer


        RANDOMIZE
        LowestNumber = 0
        HighestNumber = 5
        randomnummer = Int((HighestNumber-LowestNumber+1)*Rnd+LowestNumber)

End Function

    Dim Array(5)

    Response.write "Reguliere loop door de array <br>"

    For e = 0 to 5

        Array(e) = e
        Response.write Array(e) & "<br>"

    Next


    Response.write "Pas de Fisher-Yates shuffle toe <br>"

    For e = 0 to 5

        nieuwnummer = int(randomnummer)

            temp1 = array(e)
            temp2 = array(nieuwnummer)
 
            array(e) = temp2
            array(nieuwnummer) = temp1


    Next

    For e = 0 to 5

        Response.write Array(e) & "<br>"

    Next

Output:

code:

Reguliere loop door de array 
0
1
2
3
4
5
Pas de Fisher-Yates shuffle toe 
5
4
3
1
0
2

Top!! bedankt JaWi

[ Voor 80% gewijzigd door avon op 03-06-2005 22:39 ]

[Soultaker]

Tjonge jonge, dat je zo'n triviaal algoritme voor een random permutatie nog een naam moet geven... en het dan nog naar twéé 'bedenkers' noemen ook.

Het idee ervan is in ieder geval dat je begint met een lege lijst als uitvoer en elk element uit de invoer daar achtereenvolgens op een willekeurige plek in invoegt. Om de boel efficiënter te maken voeg je de invoerelementen niet in, maar kies je per uitvoerelement welk invoerelement op die plek komt, en aangezien je dus feitelijk alleen waardes verplaatst heb je aan een enkele lijst voldoende.

Ik kan 'm ook wel korter formuleren:

code:

for(n = 0; n < input size; ++n)
    swap(input[n], input[random(n, input size)]);

Het idee is hetzelfde: je loopt de lijst één keer door en verwisselt elk element met een willekeurig element dat er niet voor ligt. Dat levert een goed gedistribueerde random permutatie op (ie. elke permutatie heeft gelijke kans om voor te komen).

[JaWi]

Soultaker schreef op vrijdag 03 juni 2005 @ 22:50:
Tjonge jonge, dat je zo'n triviaal algoritme voor een random permutatie nog een naam moet geven... en het dan nog naar twéé 'bedenkers' noemen ook.

Och, hij is ook wel bekend onder "(Better) Linair Shuffle" en zelfs de ons welbekende Knuth heeft een soortgelijk algorithme beschreven. Als het beestje maar een naampje heeft (tenzij je "permutatie-algorithme-dat-twee-willekeurige-indexen-in-een-loop-verwisselt" een handigere naam vindt )

[avon]

Nou al met al heeft het Linaire geshuffel mij toch "maak een memory spel in asp" opgeleverd

Beta release uiteraard http://www.hobbyjournaal.nl/memory.asp

[ Voor 5% gewijzigd door avon op 03-06-2005 23:47 ]

[Soultaker]

Je kunt het gewoon een algoritme voor het genereren van een random permutatie noemen, want dat is het, en deze implementatie is eigenlijk altijd waar je op uitkomt. Die namen van de auteurs erin suggereren dat zij er een bijzondere bijdrage aan hebben geleverd wat naar mijn mening te veel eer is (ook wel sneu als je je naam aan zo iets simpels moet hangen).

Voor Knuth heb ik dan wel respect; die heeft al zijn algoritmes op een rijtje en beschrijft ze zonder het nodig te vinden alle eer naar zichzelf toe te trekken.

AvOn schreef op vrijdag 03 juni 2005 @ 23:44:
Nou al met al heeft het Linaire geshuffel mij toch "maak een memory spel in asp" opgeleverd

Beta release uiteraard http://www.hobbyjournaal.nl/memory.asp

Als ik twee overeenkomende vakjes open, doet 'ie die ook weer dicht.
En als ik snel genoeg klik kan ik ze allemaal tegelijk openmaken.

[ Voor 32% gewijzigd door Soultaker op 03-06-2005 23:52 ]

[avon]

Inderdaad leverd een search op "random permutation" meer hits op dan Fisher-Yates op.
Heb je een handig overzicht van Knuth zijn algoritmes beschrijvingen?

_{Had ik al gezegd dat de beta IE only is?}

[ Voor 19% gewijzigd door avon op 03-06-2005 23:52 ]

[Soultaker]

Als je in algoritmen en datastructuren zou je z'n serie The Art of Computer Programming kunnen lenen/aanschaffen. Het is wel een standaardwerk. (Er komt ook een herziene versie van, geloof ik.)

[NMe]

AvOn schreef op vrijdag 03 juni 2005 @ 23:52:
Inderdaad leverd een search op "random permutation" meer hits op dan Fisher-Yates op.
Heb je een handig overzicht van Knuth zijn algoritmes beschrijvingen?

[google=knuth algorithms]?

Wil je trouwens de volgende keer als je hier een topic opent in de titel vermelden om welke taal het gaat? Je oorspronkelijke vraag was behoorlijk taalspecifiek, en dan helpt het je niet als we moeten raden naar een taal.