Programming question

[Cor]

I have an arraylist of lets say 200 passwords

Now I want to put randomly in another array 50 unique passwords from the password list.


What's the best way to do this something like below or has anyone a better(faster) solution.

for passwords = 0 to maxpasswords

for uniquepasswords = 0 to 50

next

next

[blueznl]

hey cor, isn't it easier to use a linked list for this?

say, you've got 200 paswords:

pasword_n.l = 200
random_pick.l = random(password_n-1)
selectelement(list(),random_pick)
addelement()
list() = whatever

(just from the top of my head, that's no real code above )

[Cor]

Hello blueznl,

The 50 choosen passwords must be unique, it must be done with arrays

[Berikco]

someting like this could maybe help?
Not real code, just quickly type

Code: Select all

for uniquepasswords = 0 to 200 
array(1)=0
next 


uniquepasswords = 0  
Repeat
  pick=random(200)
  if array(1)= 0 ; not yes picked
    array(1)=1
    uniquepasswords + 1
  endif
until uniquepasswords = 50

[blueznl]

hey bericko, once you add passwords, the array get bigger, so your random should reflect that

[Psychophanta]

Cor, your question is very interesting, it is not trivial to make a "perfect" and the fastest algorithm to extract randomly a number (50 in this case) of items from a "bag" of a bigger number of items (200 in this case).

It is needed to put brains to work to do it :roll:

For me is interesting, I'll try.

[blueznl]

ooops, cor, i didn't read your question properly, tonight i'll give it another try

(effe knutselen)

[dmoc]

Berikco's suggestion will work but run time is random (sort-of). Best way is to put your pw's in a list and use a random number 0..ListCount-1 to select one then remove the selection. Think of a dealing from a deck of cards.

[Berikco]

Berikco's suggestion will work but run time is random (sort-of). Best way is to put your pw's in a list and use a random number 0..ListCount-1 to select one then remove the selection. Think of a dealing from a deck of cards.

Yup, list is much better, but seems Cor wanted to use array.

[dmoc]

Yeah, but he could use a temp list or would you say that's cheating?

PS: And anyway he's clearly schizo... "arraylist"

[blueznl]

see personal message

[blueznl]

oh zo...

this will do it...

Code: Select all

password_n = 500
user_n = 200
;
Dim passwords.s(password_n)
Dim gekozenpasswords.s(user_n)
;
For n = 1 To password_n
  passwords(n) = "watdanook"+Str(n)
Next n
;
For n = 1 To user_n
  r = Random(password_n-1)+1
  gekozenpasswords(n) = passwords(r)
  passwords(r) = passwords(password_n)
  password_n = password_n-1
Next n
;
For n = 1 To user_n
  Debug gekozenpasswords(n)
Next n
;

[dontmailme]

hey cor, isn't it easier to use a linked list for this?

say, you've got 200 paswords:

pasword_n.l = 200
random_pick.l = random(password_n-1)
selectelement(list(),random_pick)
addelement()
list() = whatever

(just from the top of my head, that's no real code above )

I like this suggestion.... it seems the best.... all is neede is to delete the element selected from the list of 200 then your next random will be to select from 199 etc.....

Surely would be most efficient ?!

[Psychophanta]

blueznl, your algorithm is fast, even it destroys the content of the source array.

I have the same question than dontmailme:
Surely would be most efficient ?!



NOTE for blueznl: please use english words in code too, because code should be much more quickly understandable.

[stan]

Hi blueznl,

this will do it...
Code:
password_n = 500
user_n = 200
;
Dim passwords.s(password_n)
Dim gekozenpasswords.s(user_n)
;
For n = 1 To password_n
passwords(n) = "watdanook"+Str(n)
Next n
;
For n = 1 To user_n
r = Random(password_n-1)+1
gekozenpasswords(n) = passwords(r)
passwords(r) = passwords(password_n)
password_n = password_n-1
Next n
;
For n = 1 To user_n
Debug gekozenpasswords(n)
Next n
;

Sorry but it doesn't, I checked this way :

Code: Select all

OpenConsole( )

; blueznl code (no change )

password_n = 500 
user_n = 200 
; 
Dim passwords.s(password_n) 
Dim gekozenpasswords.s(user_n) 
; 
For n = 1 To password_n 
  passwords(n) = "watdanook"+Str(n) 
Next n 
; 
For n = 1 To user_n 
  r = Random(password_n-1)+1 
  gekozenpasswords(n) = passwords(r) 
  passwords(r) = passwords(password_n) 
  password_n = password_n-1 
Next n 

; End of blueznl code

; Check if passwords are all different
 
Ok = 1
For n = 1 To user_n - 1
  For m = n + 1 To User_n 
    If FindString(gekozenpasswords(n), gekozenpasswords(m), 1) 
      Ok = 0
    EndIf
  Next m
Next n 

If Ok
  PrintN( "It works" )
Else
  PrintN( "It doesn't work" )
EndIf
  
Input( )
CloseConsole( )

The reason behind it is that it is very unlikely that a FLOAT random number generator will give 200 different INT numbers (obtained by discarding the decimal part) when called 200 times in a row ...

For an int random number generator which would work may I suggest a look at :

http://www.math.keio.ac.jp/~matumoto/emt.html

Bests.

Stan.