WE know how to SORT arrays, but how about UNSORTING? 5

[Mudassar]

Many people have asked over and over how to sort arrays. But how would I Unsort (MIX) them? I looked everywhere but nobody seemed to have asked this question.

I am making a program with questions. These questions are in an array and i want the questions to pop up randomly. HOWEVER, I can't use the RND command beacuse it may get that same random number twice (or more). In other words, I don't want the same question to pop up twice. So how would I MIX the questions?
-----------------
MK

Everybody should use AntiVirus! Are you protected now?

 

[jmarler]

Add one more column to your array and then seed that number with random numbers. Then Sort the array based upon the column with the random numbers. This will "unsort" the array while ensuring that you do not get the same question asked twice. - Jeff Marler B-)

 

[Mudassar]

I don't understand what you mean. could you give me an example jmarler? -----------------
MK

Everybody should use AntiVirus! Are you protected now?

 

[jmarler]

OK . . . here is the code that you will need to "unsort" your questions. Actually, I just came up with this code today at work for a very similar problem. I adapted what I had to work for your questions. The code only has 4 questions, bu you can add as many as you'd like and you may choose to use a more power sorting algorithm depending upon how many question you have. Here is the code . . . hope it helps . . .

   Dim strQuestions() As String
   Dim strTemp() As String
   Dim lngIndex As Long
   Dim lngArrayElementCount As Long
   Dim lngLoopIndex1 As Long
   Dim lngLoopIndex2 As Long
   Dim lngRandomSeed As Long
   Dim strQuestion As String

   '** Generate some sample questions.
   '***********************************************************************.

   ReDim strQuestions(3)
   strQuestions(0) = "What is your name?"
   strQuestions(1) = "What is your favorite color?"
   strQuestions(2) = "What do you do for a living?"
   strQuestions(3) = "What is your EMail address?"

   '***********************************************************************

   '** Copy the questions over to a temp array and then seed a column in
   '** the array with random numbers.
   '***********************************************************************.

   lngArrayElementCount = UBound(strQuestions)
   ReDim strTemp(lngArrayElementCount, 1)
   For lngIndex = 0 To lngArrayElementCount
      Call Randomize

'** Seed the Random Number generator

      strTemp(lngIndex, 0) = CLng(Rnd() * 100000)

'** Store the Random Number

      strTemp(lngIndex, 1) = strQuestions(lngIndex)

'** Store the question

   Next lngIndex

   '***********************************************************************

   '** Now Sort the array by random number. This uses a basic bubble sort,
   '** but you may choose to use a more efficient sorting algorithm like
   '** a binary sort.
   '***********************************************************************.

   For lngLoopIndex1 = UBound(strTemp) To LBound(strTemp) Step -1
       For lngLoopIndex2 = LBound(strTemp) + 1 To lngLoopIndex1
           If strTemp(lngLoopIndex2 - 1, 0) > strTemp(lngLoopIndex2, 0) Then
               lngRandomSeed = strTemp(lngLoopIndex2 - 1, 0)
               strQuestion = strTemp(lngLoopIndex2 - 1, 1)
               strTemp(lngLoopIndex2 - 1, 0) = strTemp(lngLoopIndex2, 0)
               strTemp(lngLoopIndex2 - 1, 1) = strTemp(lngLoopIndex2, 1)
               strTemp(lngLoopIndex2, 0) = lngRandomSeed
               strTemp(lngLoopIndex2, 1) = strQuestion
           End If
       Next lngLoopIndex2
   Next lngLoopIndex1

   '***********************************************************************

   '** After sorting on the Random seed, the numbers should be "unsorted".
   '** Go ahead an return them to the original array in their new order.
   '***********************************************************************.

   For lngIndex = 0 To lngArrayElementCount
      strQuestions(lngIndex) = strTemp(lngIndex, 1)
   Next lngIndex

   '***********************************************************************.

There you go! I hope that is what you were looking for . . . - Jeff Marler B-)

 

[Mudassar]

thanks jmarler!

I studied the code carefully, did the code pick random numbers of a large range (0 to 100000) so there would be a lot less chance of getting the same number?



Thats a good idea. I wonder why I didn't think of that..

thanks again!

-----------------
MK

Everybody should use AntiVirus! Are you protected now?

 

[jmarler]

Mudassar,
Yes, the reason for picking a large range (much larger than the available choices) is to make it less likely that that same number gets picked twice. It could still happen, but using this algorithm, it won't matter. You will just get two questions placed next to each other in the sort, but you will not get the same question asked twice. - Jeff Marler B-)

 

[MichaelRed]

I have a few 'issues' with the soloution.

First, the change in the order of magnitude of the random number is irrelevant to the process. If "K" is a constant and "V" is a variable, the relation ship between Various values of "V" is exactly the same as the relationship betwee the various values of "K * V", so to simply generate "K * V" to sort on theis value is no different than sorting on the value of "V" alone.


Second, the SORT is a bit to SIMPLISTIC. There is not even a flag to exit when the sort is complete. Thus, instead of sorting the expected (~ 0.5 * N ^ 2, where N = Number of elements), this will always and FOREVER LOOP the entire N ^ 2 times. For the 4 elements, this is -of course- inconsequential. For other uses, it may become intolerable.

Last (and probably least), this exercise BEGS (to me) for the use of an (albiet simplistic) UDT, which obviates the need for at least the replacement of the original array of strings.

Some additional enhancements are (or at least appear to me to be) necessary for use in a real production application. the questions should be safely stored away somewhere, a real database woould be appropiate. However this immediatly raises other issues, such as adding attributes appropiate to the application to the question set. If it were an 'academic' situation, the subject and the gradelevel would appear to appropiate, whereas a 'public survey' might want to include location or other personal attributes.

Without going into the 'enhancements' and using jmarler's overall structure:

Option Compare Database
Type MyQuestionType
    MyInquiry As String
    MyIndx As Single
End Type
Dim MyQuestion(3) As MyQuestionType
'_____________this is the Declarations Section________


Public Function basRndOrder()

    Dim tmpQuestion As MyQuestionType
    Dim Idx As Long
    Dim Jdx As Long

    'Instantiate sample questions.
    MyQuestion(0).MyInquiry = "What is your name?"
    MyQuestion(1).MyInquiry = "What is your favorite color?"
    MyQuestion(2).MyInquiry = "What do you do for a living?"
    MyQuestion(3).MyInquiry = "What is your EMail address?"

    'Add the random numbers.
    For Idx = 0 To UBound(MyQuestion)
       MyQuestion(Idx).MyIndx = Rnd()
    Next Idx

    'Sort the array by the random number.
    
    SwapFlag = True
    Do While SwapFlag
        SwapFlag = True
        For Idx = 0 To UBound(MyQuestion) - 1

            If MyQuestion(Idx).MyIndx > MyQuestion(Idx + 1).MyIndx Then

                SwapFlag = False
                'Do The Sort / Swap Thinggy
                'Save the Jdx one
                tmpQuestion.MyInquiry = MyQuestion(Idx).MyInquiry
                tmpQuestion.MyIndx = MyQuestion(IJdx).MyIndx
                'Move Idx + 1 to Idx
                MyQuestion(Idx).MyInquiry = MyQuestion(Idx + 1).MyInquiry
                MyQuestion(Idx).MyIndx = MyQuestion(Idx + 1).MyIndx
                'Move (OLD)Idx to Idx + 1
                MyQuestion(Idx + 1).MyInquiry = tmpQuestion.MyInquiry
                MyQuestion(Idx + 1).MyIndx = tmpQuestion.MyIndx

            End If
        Next Idx
    Loop

End Function

MichaelRed
mred@att.net

There is never time to do it right but there is always time to do it over

 

[jmarler]

MichaelRed,
Let me address some of the issues that you have with my solution as well as touch upon some of your suggestions.

1) You said,

"First, the change in the order of magnitude of the random number is irrelevant to the process."

Actually, the order of magnitude here is very important. It is used to ensure that each row gets a unique number. Remember that each row gets its own random number assigned to it and ideally, these random numbers should be as unique as possible in the set of rows to ensure that all of the rows are "unsorted". The sort algorithm sorts on the random number column and only the random number column, so if you picked an integer number between 0 and 1 (i.e. only two choices) the chances of the final results be truly random is not as great as if a larger range of number was used.

For Example, given the dataset as follows . . .

Questions     Low Range Sort     High Range Sort

    Question 1          1                   34212
    Question 2          1                   21093
    Question 3          0                   54210
    Question 4          0                   10293

The low range sort would be sorted as follows . . .


Question 3
Question 4
Question 1
Question 2


While the High Range Sort would be sorted as


Question 4
Question 2
Question 1
Question 3


You can see that the first would still follow some of the basic order while the second option would have a much better chance of breaking away from the original order. This may not be real obvious with only 4 question (which is all I used form my example), but add alot more question and run the app several times and statistically speaking, the higher the order of magnitude, the better the randomization will be.

2) You said,

Second, the SORT is a bit to SIMPLISTIC.


YES IT IS! I will be the first to agree with you on this. As a matter of fact, if you go back and look at my code comments as well as the text in my post, you will see that I state the very same thing! The routine that I used at work used an ADO recordset and the ADO Sort method to sort on the randomized field so I did not have to write any sorting code. However, the question here was for an array, not a recordset, So I quick threw together a VERY BASIC sort for a VERY BASIC example of the idea. The demo code here was not intended to be an example of ideal sorting algorithms, but rather a demo of how to unsort an array.

3) You said,

Last (and probably least), this exercise BEGS (to me) for the use of an (albiet simplistic) UDT, which obviates the need for at least the replacement of the original array of strings.


Yes , I would agree with you here to and I even thought of doing it . . . however, as I said before, the idea here was not to make the code elaborate, but rather to show the basic idea. There are many ways to expand on this and some of your ideas are great. However, adding too much to this demo would detract from it original purpose. Yes I could have stored the question in a database (and in the real world I would have and do - I help develop computerized testing applications that are used for Certification Tests - such as MS certification) but once again for a quick demo, it was easier hardcode them into the application.

Anyway, I have said more than my 2 cents on this, but I did feel a need to address some of your points. - Jeff Marler B-)

 

[Francis]

The Rnd Function Returns a Single variable containing a random single value.
So declare the extra column a single variable, then you do not have to worry about significant figures.
Throw away the rnd column after the new sort to ensure randomness.

 

[jmarler]

Francis,
In this case, the extra column is part of a String array (the questions are strings), so the extra column can not be declared as Single. If you choose to use a UDT (MichaelRed idea!) you could do that. However, for this to work and to be as close to random as possible over time (at least statistically) a larger random number is better. And yes, the randon number column is removed at the end. That is why the code goes through the array again at the end. It is just to transfer the sorted values into the orginal array and get rid of the random number field. - Jeff Marler B-)

 

[Mudassar]

Thanks jmarler and MichealRed. You've been a big help.

Too bad you can't had restrictions to the RND command.
eg: int(rnd * 10, <> 2) or something like that.



-----------------
MK

Everybody should use AntiVirus! Are you protected now?

 

[WildWill]

A different approach would be to shuffle the questions array in the way cards are shuffled in a card game. This is a lot shorter winded and is how we worked in the games industry a long long …. time ago

Create an array of questions (eg 100 questions)

Then shuffle them by


loop x amount of times
generate random1 ( 1 to 100)
generate random2 ( 1 to 100)
tempQuestion = question (random1)
question(random1) = question(random2)
question(random2) = tempQuestion
end loop


Simple

X-)
Billy H

bhogar@acxiom.co.uk

 

[jmarler]

WildWill,
Yes, I like your approach to this, but I see one problem with it (or maybe I'm just missiing something) . . . can you guarantee that the same question is not asked twice? If that was not a constraint, then your approach would be perfect. - Jeff Marler B-)

 

[WildWill]

Yes

Because you are shuffling the qusetions(I.E. Chosing two questions and swaping them) you will not get any duplicates.

Just like you do not get any duplicates in a card game.

X-) Billy H

bhogar@acxiom.co.uk

 

[strongm]

WildBill,

I like this solution - but I'm biased, since it is essentially the same as a shuffle routine I wrote some (a lot of) years ago for a blackjack game that I wrote. In the end, the shuffle routine was the best thing in it...

 

[Mudassar]

WildWill that is perfect!! thanks alot! -----------------
MK

Everybody should use AntiVirus! Are you protected now?