Picking several elements at random

[Legacy_Grani]

               

What's the best way to go about randomly picking a number of values from a given list (can be the pseudo-array NWScript offers)?

 

For example, I have a list of 11 string values. I want 9 of them randomly assigned to nine strings (let's say "s1", "s2", "s3" and so forth).

 

One approach I could think of was having a simple switch for the first string, then looping a second similar switch for a second string under the condition that the first and second strings are equal, then looping a third switch, etc. I'm fairly sure, though, there must be a simpler and more elegant solution. Not to mention a loop based on conditions met randomly would likely result in "too many instructions" error often.

               
               

               
            

[Legacy_Proleric]

               

Here's the algorithm I use to choose unique items from a list in a random order (allowing duplicates only when the pool is exhausted, which won't happen in your case).

// Assume we have populated a pseudoarray p[1]...p[n]
 
counter = n
 
// Iterate
    i = Random(counter) + 1
    result = p[i]
    store = p[counter]
    p[counter] = p[i]
    p[i] = store
    counter--
    if (counter == 0) counter = n

               
               

               
            

[Legacy_Shadooow]

               

assuming a pseudolist with basic functions and assuming you dont want any element to repeat - not in s1/s2/s3 standalone or together

 

 

loop 1-3

 - get num elements from list

 - get Random(num_elements)+1 element

 - assign into s1 string

 - remove element from list

endloop

reset loop counter

loop 1-3

 - get num elements from list

 - get Random(num_elements)+1 element

 - assign into s2 string

 - remove element from list

endloop

reset loop counter

loop 1-3

 - get num elements from list

 - get Random(num_elements)+1 element

 - assign into s3 string

 - remove element from list

endloop

               
               

               
            

[Legacy_Grani]

               

Alright, thanks for ideas. '>

               
               

               
            

[Legacy_Lightfoot8]

               

This should give you some Ideas on how I go about it.   

 

Keep in mind that the tokenizer that I am using out of the string lib  is not the most efficient way of doing this.  It is just what I used for simplicity in this example.  

// the Include is here only because of how I am storing the strings.
#include "X0_I0_STRINGLIB"

// This is just how I am storing the strings in an array for the example.
// You can store them any way you want.  the real trick here is placing the
// indice of for the array into a string so we can pull them out one at a time and only once.
const string sStringArray = "String one.~String Number 2.~The third string.~string 4.~Fifth string.~#6 . ~ 7 str ~8 in strings.~Ninth entry.~10th entry.~eleventh and last element";

// this is just the 1-11 indices defined outside of the function that uses it.
string sElements = "0001020304050607080910";

// function to get our random indice and remove it.
int GetAndRemoveRandomElementIdx()
{
   //Figure out how many indice we have left.
   int MaxNumIdx = GetStringLength(sElements)/2;

   // generate the start location of the index into sElements
   int nRnd = Random(MaxNumIdx)*2;

   // get the index at that location.
   int nStringIdx = StringToInt( GetSubString (sElements,nRnd,2));

   //remove the index from the string.
   sElements = GetStringLeft(sElements,nRnd) + GetStringRight(sElements,MaxNumIdx*2- nRnd-2);

   //Return the index
   return  nStringIdx;

}


// Test code OnOpen chest.

void main()
{

  // Speak out 9 of the 11 strings.
  int x;
  for (x=0;x<9;x++)
  {
    //Get random index and remove it.
    int nIdx = GetAndRemoveRandomElementIdx();

    // Speak the string selected.
   SpeakString( GetTokenByPosition(sStringArray,"~",nIdx));


   // Check elements array to make sure element is removed.
//   SpeakString ( "Element "+ IntToString(nIdx) + " Selected. "
                 +"sElements is now " + sElements);



  }
}

Here is the out put from the test run.  

 

 

 Barrel: String one.

  Barrel: Element 0 Selected. sElements is now 01020304050607080910

  Barrel: String Number 2.

  Barrel: Element 1 Selected. sElements is now 020304050607080910

  Barrel:  7 str 

  Barrel: Element 6 Selected. sElements is now 0203040507080910

  Barrel: eleventh and last element

  Barrel: Element 10 Selected. sElements is now 02030405070809

  Barrel: Ninth entry.

  Barrel: Element 8 Selected. sElements is now 020304050709

  Barrel: Fifth string.

  Barrel: Element 4 Selected. sElements is now 0203050709

  Barrel: #6 . 

  Barrel: Element 5 Selected. sElements is now 02030709

  Barrel: The third string.

  Barrel: Element 2 Selected. sElements is now 030709

  Barrel: string 4.

  Barrel: Element 3 Selected. sElements is now 0709

               
               

               
            

[Legacy_WhiZard]

               

This should give you some Ideas on how I go about it.   
 
Keep in mind that the tokenizer that I am using out of the string lib  is not the most efficient way of doing this.  It is just what I used for simplicity in this example.

Wouldn't a bit field work better? Even if it is too long to express as an integer, you can have a long hex string (0-F) and perform operations by portions.
               
               

               
            

[Legacy_meaglyn]

               

The tokenizer is used to extract the string data itself, that you certainly couldn't use a bit field for. So I assume you mean using a bit field for the indices (sElements in the code).

 

So, with that assumption... No. I don't think that it would.

 

The string method Lightfoot used has the properties of  1) knowing easily how many valid options are still available, and 2) knowing immediately which are valid, because only valid items are still in the search space.

 

Using a bit field you would need to calculate the hamming weight (number of bits set) each time to see how many are still set.

 

And then you'd have to search for the Nth _set_ bit out of the field rather than just using the Nth item immediately because the bit set does not maintain the second property.

 

You can certainly do it with a bit set, but it would be more complicated.

               
               

               
            

[Legacy_WhiZard]

               

You can certainly do it with a bit set, but it would be more complicated.

Yeah, I see that we don't have HexStringToInt(). That in itself would make things a whole lot easier.

The manual computation looks a little hefty too.
 

int HexStringToInt(string sHex)
{
string sIndex = "0123456789ABCDEF";
int nInt = 0;
string sChar = "";
int nIndex;
int nLength = GetStringLength(sHex);
if(GetStringLeft(sHex,2) == "0x")
  {
  sHex = GetStringRight(sHex, nLength -2);
  sLength -=2;
  }
while(nLength--)
  {
  sChar = GetStringLeft(sHex, 1);
  nIndex = 16;
  while(nIndex--)
    {
    if(GetSubString(sIndex, nIndex, 1) == sChar)
      {
      nInt = 16 * nInt + nIndex;
      break;
      }
    }
    sHex = GetStringRight(sHex, nLength);
  }
return nInt;
}

               
               

               
            

[Legacy_Squatting Monk]

               

Here's Axe Murderer's conversion function from his flagsets script, if it helps:

int HexToInt(string sHex)
{
    sHex = GetStringLowerCase(sHex);
    if (GetStringLeft(sHex, 2) == "0x")
        sHex = GetStringRight(sHex, GetStringLength(sHex) -2);

    if ((sHex == "") || (GetStringLength(sHex) > )
        return 0;

    string sConvert = "0123456789abcdef";
    int nValue = 0;
    int nMult  = 1;
    while(sHex != "")
    {
        int nDigit = FindSubString(sConvert, GetStringRight(sHex, 1));
        if (nDigit < 0)
            return 0;
        nValue += nMult *nDigit;
        nMult  *= 16;
        sHex    = GetStringLeft(sHex, GetStringLength(sHex) -1);
    }
    return nValue;
}