[JS]Fisher-Yates shuffler werkt niet in IE7 - Softwareontwikkeling

woensdag 3 december 2008 20:04

Acties:

0 Henk 'm!

Verwijderd

Topicstarter

Hallo mensen!

Ik ben nieuw hier, eerste post enzo dus doe aub niet raar als dit een domme vraag is.
Mijn probleem is als volgt:

Via Google heb ik het volgende JavaScript-shuffle algoritme gevonden:

code:

function fisherYates ( myArray ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;
   }
}

Dit schijnt een bekend shuffle algoritme te zijn voor arrays in Perl en de maker van deze versie heeft hem "omgebouwd" naar JavaScript. Ik ben van plan om een string waarin een aantal tekens uit de ASCII-tekenset (erin gezet via String.fromCharCode) allemaal exact twee keer voorkomen te "husselen". Omdat JavaScript strings niet, zoals C dat bijvoorbeeld doet, als arrays ziet, heb ik mijn string, laten we hem "str1" noemen (zo heet hij niet in het script dat ik schrijf maar dat maakt niks uit), omgezet naar een array aan de hand van:

code:

1 2	var strarray = new Array(); strarray = str1.split("");

Vervolgens roep ik de fisherYates(strarray) functie aan en voeg ik de array weer samen met

code:

1	var str2=strarray.join("");

Als ik vervolgens beide strings onder elkaar op mijn scherm zet met

code:

1	document.write(str1 + "<br>" + str2);

dan blijkt str2.length in veel gevallen kleiner te zijn dan str1.length. Er vallen dus op de één of andere voor mij onverklaarbare manier in deze bewuste gevallen tekens "weg te vallen".

Mijn vraag aan jullie is of jullie mij kunnen helpen dit script werkend te krijgen zodat ik weer aan de slag kan!
Het is mogelijk dat er een fout in mijn source zit, maar dat verlkaart niet waarom er gevallen zijn waarin het script wel werkt.

Groeten:

Lefty2007

woensdag 3 december 2008 23:58

Acties:

0 Henk 'm!

crisp

Devver

Pixelated

De volgende testcase geeft voor mij toch dezelfde lengths en een geshuffelde array terug:

JavaScript:

function fisherYates ( myArray ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;
   }
}

var s1 = 'De kat krabt de krullen van de trap!!!';
var a1 = s1.split('');
fisherYates(a1);
var s2 = a1.join('');

alert(s1.length + ' ' + s2.length);
alert(s1 + ' ' + s2);

bij wat voor soort strings gaat het fout volgens jou?

Intentionally left blank

donderdag 4 december 2008 11:46

Acties:

0 Henk 'm!

Verwijderd

Ik gebruik zelf altijd deze implementatie:

JavaScript:

var shuffle = function(o) {
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
};

van http://snippets.dzone.com/posts/show/849

donderdag 4 december 2008 12:48

Acties:

0 Henk 'm!

Verwijderd

Topicstarter

Ik gebruik een string die is gebaseerd op:

code:

var length=prompt("Voer het aantal paren in...",10);
if (length > 93)
{
alert("Error!");
length=1;
}
var mystring = "";
var asciilength=1*length+33;
for (i=33; i<=asciilength; i++)
{
mystring = mystring + String.fromCharCode(i);
}
mystring = mystring + mystring;

in de string staan dus de leesbare ascii-codes vanaf 33 t/m het aantal paren ingevoerd als length + 33, het maximum aantal paren is 93 omdat alleen de ascii code's 33 t/m 126 een in te typen resultaat geven (en natuurlijk is 126-33 gelijk aan 93). Stel je houdt je aan de standaardinvoer van 10, dan krijg je dus de volgende string:
!"#$%&'()*
Omdat in de laatste stap deze string met zichzelf geconcateneerd wordt krijg je uiteindelijk:
mystring =
!"#$%&'()*!"#$%&'()*
In de code die ik getest heb, met een lengte van 50, werd mijn uitvoerstring (str2) na behandeling door Fisher/Yates korter dan str1 welke ik gelijk heb gesteld aan mystring. In totaal heb ik ongeveer de volgende code gebruikt voor het testen van Fisher/Yates, dit voorbeeld gaf bij mij de fout:

code:

<html>
<head><title>Test</title>
<script language="JavaScript">
function fisherYates ( myArray ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;
   }
}
</script>
</head>
<body>
<script language="JavaScript">
var length=prompt("Voer het aantal paren in...",10);
if (length > 93)
{
alert("Error!");
length=1;
}
var mystring = "";
var asciilength=1*length+33;
for (i=33; i<=asciilength; i++)
{
mystring = mystring + String.fromCharCode(i);
}
mystring = mystring + mystring;
var str1=mystring;
var strarray=new Array();
strarray=str1.split("");
fisherYates(strarray);
var str2=strarray.join("");
document.write(str1 + "<br>" + str2);
</script>
</body>
</html>

Dit gaf bij mij in een aantal gevallen geen twee regels met dezelfde lengte.

Edit: @Blues: Ik heb "jouw" code snippet er ook eventjes ingezet en die gaf hetzelfde probleem...

donderdag 4 december 2008 14:24

Acties:

0 Henk 'm!

Verwijderd

Ah ik zie het. Je probleem is niet dat de strings niet gelijk qua lengte (dat zijn ze namelijk wel) maar dat de lengte van de HTML-output verschilt! Ter vergelijking:

JavaScript:

1 2	document.write('ABCD<'); // geeft "ABCD<" in je scherm document.write('<ABCD'); // geeft ""!

Je moet de < wel escapen naar < natuurlijk anders wordt er een HTML tag van gemaakt.

donderdag 4 december 2008 14:35

Acties:

0 Henk 'm!

sig69

Of zet het in <pre></pre> tags

Roomba E5 te koop

donderdag 4 december 2008 14:58

Acties:

0 Henk 'm!

Verwijderd

sig69 schreef op donderdag 04 december 2008 @ 14:35:
Of zet het in <pre></pre> tags

Dan moet je nog steeds je <, > en & encoden.

HTML:

<pre>
function hello() {
    <strong>important_code();</strong>
}
</pre>

Dit zal "important_code()" gewoon bold afdrukken.

donderdag 4 december 2008 15:55

Acties:

0 Henk 'm!

Verwijderd

Topicstarter

Bedankt voor het idee, maar hoe moet je dit uitwerken, de manier die ik eventjes snel bedacht kan op de één of andere manier niet, dat is deze:

code:

lengthstrarray = strarray.length;
for (i=1; i<=lengthstrarray; i++)
{
if (strarray[i] = "<")
{
strarray[i] = "&lt;";
}
else if(strarray[i] = ">")
{
strarray[i] = "&gt;";
}
else if(strarray[i] = "&")
{
strarray[i] = "&amp;";
}
else if(strarray[i] = '"')
{
strarray[i] = "&quot";
}
}

Blijkbaar zijn ook dubbele quote, de ampersand en de is groter/kleiner dan-tekens ook in JavaScript belangrijk, wat mij niet logisch lijkt. Mijn uitvoer is:

code:

1	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<!<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

En de plaats van het uitroepteken is "random" (bij opnieuw uitvoeren v.h. script staat ie ergens anders)

Iemand een idee?

donderdag 4 december 2008 16:31

Acties:

0 Henk 'm!

Verwijderd

= --> ==

donderdag 4 december 2008 16:50

Acties:

0 Henk 'm!

Verwijderd

Topicstarter

Oké mensen hardstikke bedankt! Het werkt nu perfect! Ik zou er echt niet zelf uitgekomen zijn en zonder jullie hulp had ik het echt niet gered! Kan ik nu eindelijk weer verder "scripten"

Oh ja voor het geval jullie nieuwsgierig waren waarom ik die == was vergeten, ik ben ondertussen ook bezig met een programma in Visual Basic, vandaar!

Allemaal bedankt voor de hulp!

Lefty2007