Random Unique Lists of 12 Numbers

Hello am trying to create a program which will

Generate Lists of unique numbers of 12 between 1-90 until there can be no more unique lists to product

e.g

12 2 4 5 7 9 8 19 90 70 18 56
23 4 8 9 10 12 11 13 60 55 60

-So Creating Multiple Strings of Numbers between 1-90 each string containing only 12 numbers(a string of 12 numbers cannot contain duplicate numbers in it )

-But two strings can contain multiple duplicate numbers as long as the two strings are not the same.(So the program must be able to somehow compare previous generated strings in order to avoid creating an exact same string)

-Sequence of the numbers in each string matter.So the program cannot create a string identical to another already generated but with a different sequence.


Create lists untill no more strings can be create and display a msgbox to stop.


Any ideas?This is a very very hard project for me and i need an A.;(

I cannot do this alone i need help!


Thanks

-

What code do you have so far, what did you already do?

Quote:

---

Originally Posted by baja_yu

What code do you have so far, what did you already do?

---

Well no am still thinking how am going to do this.. Its complicated.. and am i bit rusty when it comes to vb6

"Generate Lists of unique numbers of 12 between 1-90 until there can be no more unique lists to product"

First, you need to know at least basic combinatorics in math (permutations and combinations) to be able to do this. If you take into account 1-90 span, with 12 elements in list, I think the number of possible lists will be huge, and checking that there are no duplicate lists might be slow.

If you still want to generate all possible combinations, then you shouldn't be looking into random number generation, it will be faster to use a combinatorics algorithm to generate them all.

Yes but its too long to create combinatorics algorithm to generate the list.Computing power is no problem the program will be tested on a new 6 core computer ;]

In that case you still need the basic math to calculate exactly how many possible combinations there are, otherwise the algorithm can go on forever. Pseudo code would look something like this

Code:

---

Dim lngCombinations As Long
Dim I As Long

Do
  For I = 1 To 12
      AddItemToList(Int(Rnd * 90 + 1))
  Next I

  'check that generated list is not identical to all previously generated
  If ListIsUnique Then
      'add it
      lngCombinations = lngCombinations + 1
  End If
Loop While lngCombinations < [possible_combinations]

---

I just refreshed my math studies from college. The number of unique 12 element sequences, without repetition, from a set of 90 elements (1-90) is equal to 90 to the 12th power.

So MS Calc says that for 90^12 you would have in total 282,429,536,481,000,000,000,000 sequences. Generating those on random, while constantly comparing the one generated randomly against all other already generated will take ages to finish, even for a supercomputer.

My suggestion would be to read up on permutations and create an algorithm to generate the sequences in order, rather than endlessly generating random ones.

EDIT: Googling "Visual Basic 6 permutations" I got this: http://www.codeguru.com/vb/gen/vb_mi...mbinations.htm

Quote:

---

Originally Posted by baja_yu

I just refreshed my math studies from college. The number of unique 12 element sequences, without repetition, from a set of 90 elements (1-90) is equal to 90 to the 12th power.

---

You're actually off by a bit. 90^12 includes permutations with repeating numbers (ie two instances of 12 in teh same sequence), which the OP says is disallowed. However, the OP was vague as to whether or not he wanted permutations or combinations, as the following statement seems to me to be a contradiction:

Quote:

---

-Sequence of the numbers in each string matter.So the program cannot create a string identical to another already generated but with a different sequence.

---

In any case, if he wants permutations, then the total is 90!/(90-12)! = 131,197,375,012,291,112,448,000. If he wants combinations, it is 90!/(12!(90-12)!) = 273,897,571,557,780. However, this does not negate your point that the problem is intractable:

Assuming the lesser of two evils, lets use combinations. Given that each line would take approximately 40 bytes, the output list size would be approximately 10 PETABYTES in length.

I don't know about the OP, but my hard drive doesn't quite hold that. And 6 cores or not, something tells me his classmates will have graduated by the time his program finishes running.

So to the OP, I think one of four things is taking place here:
- You either did not properly communicate to us the actual problem
- Your teacher did not properly communicate the problem with you
- Your teacher is posing a trick question to you
- You're posing a trick question to us

Regardless, your problem as stated has no solution. So if you want any actual help, you'll need to clarify the problem statement. A lot.

Good luck

I might be a bit rusty, but I think that the n^k forumula is for permutations without repetition. For combinations n! / k!(n-k)! is also correct. Permutations return a list of sequences, whereas combinations return a list of sets. The difference being that in sequences the order of items matters (1, 2, 3) is different from (1, 3, 2), whereas with combinations the order of elements is not important so {1, 2, 3} is the same as {1, 3, 2}, {2, 3, 1} etc, thus the much lesser count of combinations than permutations.

But like you said, much clarification is needed on the problem. Still, as you illustrated the size point later which I didn't think of, even with the best possible scenario of all those, the size would still be huge.

EDIT: It really depends on the missing details, and the real purpose of this. If you just want to test the computational power/speed of the CPU, you might be better off looking at some ready made software like SuperPI http://en.wikipedia.org/wiki/Super_PI.

EDIT2: I was wrong with my original formula. n^k is for permutations with repetition, and n! / (n-k)! is without repetitions. Combinations without repetition on the other hand are n! / k! (n-k)!

Lengg

Priceless !!

Spoo

Think about this. Lets say the resulting size is not a problem, and computational power is not a problem. The total number of unique sequences is what Lenggries calculated to be: 273,897,571,557,780.

Now, assume the random generation algorithm has managed to find: 273,897,571,557,779 of those (one less than total). Now imagine how many times it will need to run doing this:

1. Generate random sequence
2. Do a For loop 273,897,571,557,779 times to compare the newly generated sequence with all the old ones to check if it's not a match to any of them.
3. Repeat.

Even if the For loop in step 2 was lightning fast, I just can't imagine how many times it will do those three steps until it, by random, finally nails the last remaining sequence. :)

If there is any chance in the universe of doing this, doing it by random guessing would be the least possible and effective way to get it done. Training monkeys to write and teaching them math so they can write all the combinations manually would probably be faster.

Please don't laugh after viewing this code...:bigyello:

Code:

---

Option Explicit

Private Sub Command1_Click()
    Randomize
   
    Dim myArray(1 To 90) As Integer
    Dim num As Integer
    Dim i As Long
    Dim counter As Integer
   
    Do While counter <= 12
        num = Int(Rnd * 90 + 1)
        If myArray(num) = 0 Then
            myArray(num) = 1
            counter = counter + 1
        End If
    Loop
   
    Dim strOutput As String
    For i = 1 To 90
        If myArray(i) = 1 Then strOutput = strOutput & " " & i
    Next
   
    MsgBox strOutput
End Sub

---

...:wave:

achileshbc: you can introduce one more array to remember the order of each myarray index, ie. order(counter) = num and then loop through this array instead of For Looping 1 to 90. myarray could be Boolean.

Thanks for the suggestion Merri...:wave:

Here's the updated code:

Code:

---

Option Explicit

Private Sub Command1_Click()
    Randomize
   
    Dim myArray(1 To 90)    As Boolean
    Dim myOrder(11)        As Integer
    Dim num                As Integer
    Dim i                  As Long
    Dim counter            As Integer
    Dim strOutput          As String
   
    Do While counter < 12
        num = Int(Rnd * 90 + 1)
        If myArray(num) = False Then
            myArray(num) = True
            myOrder(counter) = num
            counter = counter + 1
        End If
    Loop
   
    For i = 0 To 11
        strOutput = strOutput & " " & myOrder(i)
    Next
   
    MsgBox strOutput
End Sub

---

...:wave:

OK! That code produce one random sequence of 12 different numbers.
How can you know that an output sequence is not the same as one of the previous ones?
What the OP wants is all the output sequences must be different to each other.

Quote:

---

Originally Posted by anhn

OK! That code produce one random sequence of 12 different numbers.
How can you know that an output sequence is not the same as one of the previous ones?
What the OP wants is all the output sequences must be different to each other.

---

I missed those lines while reading :)

I worked out some code:

Code:

---

Option Explicit

Private Sub Command1_Click()
    '~~~ We are going to produce 4 lines of unique sequence
    Dim OutputArray(11)    As Byte    '~~~ This will hold the numbers generated using the function
    Dim strUni(4)          As String  '~~~ Unicode value(of byte array) of all 4 lines
    Dim strOutput          As String  '~~~ Final result
    Dim strTemp            As String
    Dim n                  As Long
    Dim i                  As Long
   
    Do While n < 4          '~~~ We are generating 4 lines of sequence
        If n > 0 Then
            strTemp = StrConv(OutputArray, vbUnicode)  '~~~ Getting the unicode string for the generated array values
            i = 0
            Do While i < 4                              '~~~ We are going to check this unicode value with others.
                If strTemp = strUni(i) Then            '~~~ If it is matched, then the array is shuffled and the checking is restarted.
                    ShuffleArray OutputArray            '~~~ Shuffle the array
                    strTemp = StrConv(OutputArray, vbUnicode)  '~~~ Unicode value of the shuffled array
                    i = 0                              '~~~ Start the checking (loop) from the beginning
                Else
                    i = i + 1
                End If
            Loop
        End If
       
        strUni(n) = mySequence(OutputArray) '~~~ Storing the unicode string of the present byte array values
       
        '~~~ Creating that line of sequence of the present byte array values
        For i = 0 To 11
            strOutput = strOutput & " " & OutputArray(i)
        Next
       
        strOutput = strOutput & vbCrLf  '~~~ We are going to start a new line
        n = n + 1
    Loop
   
    MsgBox strOutput    '~~~ Final result
End Sub

Private Function mySequence(ByRef myOrder() As Byte) As String
    Randomize
   
    Dim myArray(1 To 90)    As Boolean
    Dim num                As Byte
    Dim counter            As Integer
   
    Do While counter < 12          '~~~ 12 values (for each line)
        num = Int(Rnd * 90 + 1)    '~~~ Finding a random number from 1 to 90
        If myArray(num) = False Then    '~~~ Check if it is already selected
            myArray(num) = True        '~~~ Marking it as selected number
            myOrder(counter) = num      '~~~ Storing the number
            counter = counter + 1
        End If
    Loop
    mySequence = StrConv(myOrder, vbUnicode)    '~~~ Returning the unicode value of this byte array

End Function

' Knuth shuffle (very fast). Thanks to "Ellis Dee" for this shuffle code
Public Function ShuffleArray(pvarArray As Variant)
    Dim i As Long
    Dim iMin As Long
    Dim iMax As Long
    Dim lngReplace As Long
    Dim varSwap As Variant
   
    iMin = LBound(pvarArray)
    iMax = UBound(pvarArray)
    For i = iMax To iMin + 1 Step -1
        lngReplace = Int((i - iMin + 1) * Rnd + iMin)
        varSwap = pvarArray(i)
        pvarArray(i) = pvarArray(lngReplace)
        pvarArray(lngReplace) = varSwap
    Next
End Function

---

I don't know how efficient it is (I don't think it is efficient at all :bigyello:)....:wave:

Quote:

---

Originally Posted by akhileshbc

I worked out some code:

I don't know how efficient it is (I don't think it is efficient at all :bigyello:)....:wave:

---

Well I know my code isn't efficient, it never is! :p
Creating 32,000 seqs this is about 11 secs faster on my PC (26s VS 37s), if I did it right, probably take a day to create 64K seq :eek2: its all down hill....

Code:

---

'  requires a listbox named List1 & Knuth shuffle by Ellis Dee
Option Explicit

Private Sub Form_Load()
    Randomize
End Sub
 
Private Sub cmdRun_Click()
    Dim Low As Long, High As Long, MaxNums As Long
    Dim n As Long, j As Long, i As Long
    Dim sTmp As String
    Dim t As Single
    ' How many numbers do we need?
    Const NumbersNeeded As Long = 12
    'set number range
    Low = 1: High = 90
    ' how many numbers will we need?
    MaxNums = High - Low
    'produce 32K lines of unique sequence
    Dim UniqArray(31999) As String
    ' dim array to max possible number range
    ReDim lngArray(0 To MaxNums) As Long
   
    ' CLEAR DISPLAY
    List1.Clear
    DoEvents
    t = Timer
   
    ' add range of numbers from low to high to array
    For i = Low To High
        lngArray(j) = i
        j = j + 1 ' increment array position
    Next i

BuildSeq:
    ' shuffle numbers in array
    ShuffleArray lngArray ' Knuth shuffle by Ellis Dee
 
    ' get numbers from array, add to string
    sTmp = vbNullString ' clear old usage of temp string
    For i = 0 To NumbersNeeded - 2 'add all array items to string with a space except last one! (-2)
        sTmp = sTmp & CStr(lngArray(i)) & " "
    Next i
    ' add last item in array to temp string without space.
    sTmp = sTmp & CStr(lngArray(i))
   
    ' Search for match in UniqArray
    For i = 0 To UBound(UniqArray)
        If sTmp = UniqArray(i) Then Exit For
    Next i
   
    ' if no match then add to UniqArray
    If i > UBound(UniqArray) Then
        UniqArray(n) = sTmp
        List1.AddItem sTmp
        n = n + 1 ' increment position for UniqArray
        ' is array filled yet?
        If n > UBound(UniqArray) Then ' all done!
            MsgBox Timer - t & " - " & List1.ListCount
            Exit Sub
        Else  ' get another string of 12 non-repeating random numbers.
            GoTo BuildSeq
        End If
    Else ' match found, Try again
        GoTo BuildSeq
    End If
           
End Sub

---

Regular Rnd doesn't give enough variation for results (see anhn's signature about pseudo-random), so:

Code:

---

Option Explicit

Public Function Random12() As String
    Dim Result(0 To 11) As String, Taken(0 To 89) As Boolean
    Dim I As Long, R As Long, V As Long
   
    For I = 0 To 11
        If I Mod 4 = 0 Then R = RndM * 65610000
        V = R Mod 90
        Do While Taken(V): V = (V + 1) Mod 90: Loop
        Taken(V) = True
        Result(I) = V + 1
        R = R \ 90
    Next I
   
    Random12 = Join(Result)
End Function

Public Function RndM(Optional ByVal Number As Long) As Double
    Static X As Long, Y As Long, Init As Boolean
    Dim R As Double
    If Init And Number = 0 Then
        X = (170 * X) Mod 12632251
        Y = (171 * Y) Mod 12558383
    Else
        If Number = 0 Then Number = Timer * 60 Else Number = Number And &H7FFFFFFF
        X = (Number Mod 12632251)
        Y = (Number Mod 12558383)
        If X = 0 Then X = 170
        If Y = 0 Then Y = 171
        Init = True
    End If
    R = CDbl(X) / 12632251# + CDbl(Y) / 12558383#
    RndM = R - Int(R)
End Function

Private Sub Form_Load()
    Debug.Print Random12
End Sub

---

This does not validate for if same sequence already exists. I find that a matter for another topic, and I also find it next to impossible for this function to generate the very same sequence within, say, a few million calls (and then waiting to be proven wrong...).


Edgemeal: a very minor code length & speed optimization tip: if you Step -1 in a For Loop, you don't need to call UBound for an extra time after the loop to see whether the loop was looped through or not. You'll always get -1 instead (if lower bound is 0).

You guys are awesome....;)

@Merri:
Output of Merri's code in my PC:

Code:

---

72 64 53 27 86 31 81 33 68 85 45 42
77 39 54 27 12 55 24 35 53 73 89 5
68 28 60 27 29 52 36 46 47 26 20 14
54 63 60 27 11 53 12 47 56 4 25 49
84 85 60 27 32 82 54 47 8 50 41 39
41 18 62 27 63 6 88 49 79 73 25 83
2 41 62 27 35 75 40 50 68 9 28 74
60 5 63 27 22 31 54 51 65 68 35 90
77 51 63 27 26 76 52 53 33 78 14 79
11 75 63 27 37 83 5 53 46 44 60 69
6 3 64 27 58 82 39 53 1 12 7 44
72 15 64 27 65 3 66 53 6 16 69 89
83 29 64 27 56 71 90 53 59 80 40 50
64 49 65 27 58 26 38 54 45 71 44 31
36 61 64 27 7 40 60 54 62 28 41 73
49 70 64 27 26 69 77 54 22 19 25 16

---

Did you noticed that the 4th row is showing the same result (27) !

@EdgeMeal:
It took 124 seconds without any modification and 134 seconds when I used DoEvents like this:

Code:

---

'...
'.....
'......
' if no match then add to UniqArray
    If i > UBound(UniqArray) Then
        UniqArray(n) = sTmp
        DoEvents
        List1.AddItem sTmp
        n = n + 1 ' increment position for UniqArray
'......
'....
'..

---

...:thumb:

I'll test my code now...;)
Ah! The test result is: 241 seconds for 31999 sequences :bigyello: :down:
Tested code:

Code:

---

Option Explicit

Private Sub Command1_Click()
   
    Dim OutputArray(11)    As Byte    '~~~ This will hold the numbers generated using the function
    Dim strUni(31999)          As String
    Dim strOutput          As String  '~~~ Final result
    Dim strTemp            As String
    Dim n                  As Long
    Dim i                  As Long
    Dim t                  As Single
   
    t = Timer
    Do While n < 31999
        If n > 0 Then
            strTemp = StrConv(OutputArray, vbUnicode)  '~~~ Getting the unicode string for the generated array values
            i = 0
            Do While i < 31999                              '~~~ We are going to check this unicode value with others.
                If strTemp = strUni(i) Then            '~~~ If it is matched, then the array is shuffled and the checking is restarted.
                    ShuffleArray OutputArray            '~~~ Shuffle the array
                    strTemp = StrConv(OutputArray, vbUnicode)  '~~~ Unicode value of the shuffled array
                    i = 0                              '~~~ Start the checking (loop) from the beginning
                Else
                    i = i + 1
                End If
            Loop
        End If
       
        strUni(n) = mySequence(OutputArray) '~~~ Storing the unicode string of the present byte array values
       
        '~~~ Creating that line of sequence of the present byte array values
        For i = 0 To 11
            strOutput = strOutput & " " & OutputArray(i)
        Next
       
       
        List1.AddItem strOutput
        strOutput = ""
        n = n + 1
    Loop
   
    MsgBox Timer - t & " - " & List1.ListCount
End Sub

Private Function mySequence(ByRef myOrder() As Byte) As String
    Randomize
   
    Dim myArray(1 To 90)    As Boolean
    Dim num                As Byte
    Dim counter            As Integer
   
    Do While counter < 12          '~~~ 12 values (for each line)
        num = Int(Rnd * 90 + 1)    '~~~ Finding a random number from 1 to 90
        If myArray(num) = False Then    '~~~ Check if it is already selected
            myArray(num) = True        '~~~ Marking it as selected number
            myOrder(counter) = num      '~~~ Storing the number
            counter = counter + 1
        End If
    Loop
    mySequence = StrConv(myOrder, vbUnicode)    '~~~ Returning the unicode value of this byte array

End Function

' Knuth shuffle (very fast). Thanks to "Ellis Dee" for this shuffle code
Public Function ShuffleArray(pvarArray As Variant)
    Dim i As Long
    Dim iMin As Long
    Dim iMax As Long
    Dim lngReplace As Long
    Dim varSwap As Variant
   
    iMin = LBound(pvarArray)
    iMax = UBound(pvarArray)
    For i = iMax To iMin + 1 Step -1
        lngReplace = Int((i - iMin + 1) * Rnd + iMin)
        varSwap = pvarArray(i)
        pvarArray(i) = pvarArray(lngReplace)
        pvarArray(lngReplace) = varSwap
    Next
End Function

---

I think its time for upgrading my PC...:blush:

i was thinking of a different approach..if you control how the ID's are made, then you could create an ID that would be the same for every sequence of the same numbers ({1,2,3} would create the same ID as {2,1,3}), which i would think it would speed up your searching.

Code:

---

Option Explicit

Private Sub Form_Load()

Dim MyData(0 To 11) As Byte
Dim ID As String
Dim i As Long

'you'd put code here to add 12 unique numbers

'you would flag each number like this, but in a loop
'For i = 1 to 12
'  Call FlagBit(MyData, MyRandomNumbers(i))
'Next i

Call FlagBit(MyData, 1) 'i just call them individually for my example
Call FlagBit(MyData, 2)
Call FlagBit(MyData, 9)
Call FlagBit(MyData, 89)
Call FlagBit(MyData, 90)

ID = StrConv(MyData, vbUnicode)
'ID would contain your unique string, not readable by the user, but you can change that if needed.
'  either by putting 24 bytes as a HEX string or possibly Base64

'then you'd have to search your database or whatever to see if the ID exists already.

End Sub

Private Sub FlagBit(ByRef pArr() As Byte, ByVal pBit As Byte)

    Dim MyByt As Byte
   
    MyByt = pBit \ 8
    If pBit Mod 8 = 0 Then
        MyByt = MyByt - 1
    End If
    pArr(MyByt) = pArr(MyByt) Or 2 ^ ((pBit - 1) Mod 8)

End Sub

---

@Billy Conner: Your idea looks cool. :wave:

Storage would be another problem... you can squeeze bitmap of 0-90 into 12 bytes (96 bits, 24 hex characters), but you also need to store list info (since numbers in list aren't displayed always in ascending order). That would be another 12 bytes (1 byte per number in list) for a total of 24 bytes (doubled size requirement).

Cost of minimized storage is increased CPU load (bit manipulation/masking, copy memory operations, etc) in order to format as numeric.

As already discussed, array storage is half (array data portion only, 12 bytes, no unique key/flag) but cost is CPU load from iterations.

Don't waste your time on this tough stuff even on Core 64 computer (not mention Core 6) if you don't understand what is behide pseudo-random number generator (PRNG).

It is impractical to check a new generated sequence against an existing unique sequences for this topic because our lives are too short to see it finishes.

There is only one practical way is to generate a series of unique sequences without going back to check whether a sequence already existed or not, ie. each sequence is unique when produced without checking.

So far in this thread, perhaps only Merri can understands the problem as he refered to a thread of mine in CodeBank of 2.5 years ago in that he had a big contribution.

You need to build a PRNG that generates a set of integers (not Integer and not Double) between 0 and at least upto 90¹² = 282,429,536,481,000,000,000,000.

The return of a Double value from RndX() or RndM() can have a precision not more than 15 digits that is the precision of the Double data type.

* The native VB Rnd() function can gives only 16,777,216 numbers before it repeats the same sequence.
* The W&H RndX() can produce a set of maximum 27,817,185,604,309 numbers.
* The RndM() seems to produce a set of maximum 158,640,646,210,133 numbers that is still too far behind 90¹².

Thanks for the valuable info guys...:wave:

I'll stop here..:)

Now all we need is to have a cameo appearance of the OP

I made the scale of RndM larger: see anhn's PRNG thread. It seems to also solve the problem reported by achilleshbc in post #19. Since my strength is more in problem solving than math I don't know the maximum set of numbers generated by the updated function. It uses the Decimal subtype of Variant instead of Double. This will greatly slow the function down, but that is the cost of breaking the limitations.

Quote:

---

Originally Posted by akhileshbc

I think its time for upgrading my PC...:blush:

---

241s, Is that with the CPU in your sig?

Ran your code and got 34.85156 on AMD 550-X2 (unlocked to quad core @ 3.4GHz).

Quote:

---

Originally Posted by leinad31

Storage would be another problem... you can squeeze bitmap of 0-90 into 12 bytes (96 bits, 24 hex characters), but you also need to store list info (since numbers in list aren't displayed always in ascending order). That would be another 12 bytes (1 byte per number in list) for a total of 24 bytes (doubled size requirement).

Cost of minimized storage is increased CPU load (bit manipulation/masking, copy memory operations, etc) in order to format as numeric.

As already discussed, array storage is half (array data portion only, 12 bytes, no unique key/flag) but cost is CPU load from iterations.

---

From what i get, the OP wants to display a list of all sequences of 12 different numbers 1-90, but without using the same exact numbers in a different sequence. i really don't see why the sequence order would be important since there is only one available sequence per group of numbers to be used. He doesn't say the numbers are inputted, as far as i know they could be incremented in the loop. He says sequence matters but he goes on to say that you cannot have the same numbers in a different sequence, that is all he says; nothing about "i need to use the sequence in my program for some other purpose", so i cannot say for sure this isn't what he's looking to do. BUT if the number sequence turns out to be important in whatever it is that he is making, its only 6 more bytes to store instead of the 12 you suggest to hold the info needed to return the numbers to the exact order in which they were presented.(you only need 4 bits to hold 0-11 or 1-12)

anhn has the right idea when it comes to performing this task, which is you don't need to loop to check for duplicate sequences, if you can loop 90^12 times and grab the bits from it(as i do in my example) then you can find every possible non-duplicate sequence that exists in order. Some may argue that vb cannot work with numbers that large but there are ways around the number limitation to get the job done. the only thing stopping you with it is it would still take forever to loop every single sequence, and there is no place large enough for you to store the sequences anywhere.

Quote:

---

Originally Posted by Billy Conner

the only thing stopping you with it is it would still take forever to loop every single sequence, and there is no place large enough for you to store the sequences anywhere.

---

I don't think anybody is saying the the algorithm to do it can't be made. It's just that processing and storage to do it isn't available. There are many ways to go about creating such a list of all possible permutations, some slower some faster, but doing a task like that with random generation is probably the slowest possible. And the fastest still has the storage problem, if nothing else.

The OP is nowhere to be seen. But judging by that it's a school project, it's probably not going to be used at all. The professor probably just wants to test his logic, maths and problem solving skills.

Quote:

---

Originally Posted by Merri

I made the scale of RndM larger: see anhn's PRNG thread. It seems to also solve the problem reported by achilleshbc in post #19. Since my strength is more in problem solving than math I don't know the maximum set of numbers generated by the updated function. It uses the Decimal subtype of Variant instead of Double. This will greatly slow the function down, but that is the cost of breaking the limitations.

---

Thanks for the updated code...:wave:

Quote:

---

Originally Posted by Edgemeal

241s, Is that with the CPU in your sig?

Ran your code and got 34.85156 on AMD 550-X2 (unlocked to quad core @ 3.4GHz).

---

Yeah, the same PC on my signature :blush:

It never ceases to amaze me how a well-defined (not really in this case) conceptual problem brings out the best programmers on this forum. Regardless, I enjoyed reading all of it, and it makes me consider getting back into the classroom to present problems to students that they will report and beg for solutions here.

That way, I would learn at least as must as the students would. :rolleyes:

I'm a bit surprised that the Knuth shuffle did not emerge. :ehh:

Quote:

---

Originally Posted by Billy Conner

From what i get, the OP wants to display a list of all sequences of 12 different numbers 1-90, but without using the same exact numbers in a different sequence. i really don't see why the sequence order would be important since there is only one available sequence per group of numbers to be used. He doesn't say the numbers are inputted, as far as i know they could be incremented in the loop. He says sequence matters but he goes on to say that you cannot have the same numbers in a different sequence, that is all he says; nothing about "i need to use the sequence in my program for some other purpose", so i cannot say for sure this isn't what he's looking to do. BUT if the number sequence turns out to be important in whatever it is that he is making, its only 6 more bytes to store instead of the 12 you suggest to hold the info needed to return the numbers to the exact order in which they were presented.(you only need 4 bits to hold 0-11 or 1-12)

anhn has the right idea when it comes to performing this task, which is you don't need to loop to check for duplicate sequences, if you can loop 90^12 times and grab the bits from it(as i do in my example) then you can find every possible non-duplicate sequence that exists in order. Some may argue that vb cannot work with numbers that large but there are ways around the number limitation to get the job done. the only thing stopping you with it is it would still take forever to loop every single sequence, and there is no place large enough for you to store the sequences anywhere.

---

Sorry, I don't see how it can be compressed to 6 bytes. Please explain again.

Quote:

---

Originally Posted by leinad31

Sorry, I don't see how it can be compressed to 6 bytes. Please explain again.

---

ok, we know there are 12 numbers that represent 1-90

the bit represented numbers in the original data are always in order.(90 bits)
now we take binary values of our 1-12
0000=0, 0001=1, 0010=2, ... 1100=12

we use them as placement order. 1 would represent the lowest number used(lowest flagged bit), 12 the highest. so we place the binary numbers (1-12) in the order that the originals were in as far as value went.

so if we had values of 1,6,70,45,22,90
you would come up with 1,2,5,4,3,6 order placement.


0001 0010 0101 0100 0011 0110
so six numbers would compress to 3 bytes(24 bits).
of course we have 12 numbers in the real data, so it would just double my example.

But you need to save the actual sequence, not just the order of elements in each sequence.

If you've saved: 1,2,5,4,3,6 how would you know if the sequence was: 1,6,70,45,22,90 or 2,7,71,46,23,90?

the 6 extra bytes im talking about now are appended to the 12 bytes from my ID variable on my code in post #20
leinad31 said it would double it(making 24 total) if i wanted to know what order they went in, in post #22

Ok, the 12 byte way means you either reference the 1-91 bitmap or store the actual number itself giving you 1 byte (pointer to position in bitmap or value itself) x 12 numbers in list.

Doing it the other way around means for each bit in bitmap you need to allocate 4 bits for its position in list, zeroed out if not in list. That would give 4 bits x 90 = 45 bytes of additional storage.

Quote:

---

Originally Posted by leinad31

Ok, the 12 byte way means you either reference the 1-91 bitmap or store the actual number itself giving you 1 byte (pointer to position in bitmap or value itself) x 12 numbers in list.

Doing it the other way around means for each bit in bitmap you need to allocate 4 bits for its position in list, zeroed out if not in list. That would give 4 bits x 90 = 45 bytes of additional storage.

---

ok i'll explain again.

to save the headache im going to work with 6 numbers instead of 12

lets say our numbers in sequence are 8,5,4,3,12,10

i put those in a 12 byte string as explained in post #20. 001110010101 .....rest zeros to 90

ok so now we have 12 bytes that hold the numbers we are using in the sequence, and they are in numerical order.

we want to append more bytes to the 12 to show placement order.
so our sequence was 8,5,4,3,12,10
our placement is 4,3,2,1,6,5
each of the placement numbers become 4 bits each.
so 4,3,2,1,6,5 becomes 0100 0011 0010 0001 0110 0101
thus making 24 bits(3 bytes)
so now we have our ID string(12 bytes) and our Placement string(3 bytes,6 bytes if 12 numbers)
ok we compressed it.
ok so now we retrieve the data back from the original string and we get numbers 3,4,5,8,10,12 in that order. (original was 8,5,4,3,12,10)
but we saved the placement data in the 3 bytes..4,3,2,1,6,5
so the 4th number of "3,4,5,8,10,12" is 8
the 3rd is 5
the 2nd is 4
etc...
only 15 bytes of data used in my example.
there is only 18 bytes of data used total if you have 12 numbers instead of 6..

Ok but that would be even more CPU intensive compared to mentioned alternatives (more bit masking required) due to use of 4 bits instead of native 1 byte.

Perhaps, but if we really want to produce a list of all these numbers, then it comes down to balancing time and space requirements. My original estimation was based on using 40 bytes per sequence and requiring about 10 petabytes. Reducing the storage estimation from 40 bytes to 18 bytes using Billy Conner's suggestion reduces the storage cost to about 5 petabytes. That's nothing to sneeze at. Furthermore, the conversion data formats for a single sequence is O(n), where n is the number of elements within a sequence (in this case 12). Happily the fastest method of producing a sequence would also be O(n), which means algorithmically, Billy Connor's method does not increase the complexity at all while reducing storage by 50%. What's not to love about it?

You don't need to store them all. Using a PRNG you can initialize at certain point and just go ahead and generate from there. If a more intelligent algorithm is written that by purpose is able to avoid generating same 12 number sequence (in different order) then all you need is knowing the initialization point to get the ones you may want. So instead of making an afterwards check one should write something that avoids the need for the check in the first place.

Except that the OP specifically says that the program needs to "create lists untill no more strings can be create." Like the other requirements, it's a bit vague, but as this thread has gone well beyond the point of merely helping him with his homework assignment, it is not unreasonable for us to consider some of the ramifications of both creation and storage.

That said, a 1-for-1 hashing between a random integer and a valid sequence, as you suggest, is almost certainly the ideal solution for sequence generation. I'm sure it could be done by almost everyone that has posted in this thread so far, but doing so and posting the solution here would hand the OP an A+ on a silver platter, and frankly, I don't think he's earned it yet.

You can't create more when you run out of memory ^___^

If I've read the requirements correctly. The first valid sequence is(sorted) 0,1,2,3,4,5,6,7,8,9,10,11, and the last valid sequence would be 79,80,81,82,83,84,85,86,87,88,89,90(again, sorted).

You can basically store this information in an array of type byte with 12 indices. Dim Numbers(11) as Byte '0 to 11 = 12 indices

Well, I suppose we should start from the beginning, so lets initialize Numbers() to the minimum sequence:

Code:

---

For x = 1 To 11
  Numbers(x) = x
Next x

---

Then we'll want to check, inside a Do loop, for any duplicates in Numbers(). So do a For x = 0 to 10, and nested inside of that, for loop y = (x + 1) to 11. This will go through every possible combination only once.

Code:

---

  For x = 0 To 10
    For y = x + 1 To 11
      If Numbers(x) = Numbers(y) Then GoTo AGAIN 'two numbers match, yes... a goto really is the easiest(most efficient) way to break out of nested loops
    Next y
  Next x

---

You could also unroll that for more speed(do it without the loops, the much longer way).

Line label AGAIN can be the place in the routine where Numbers() is incremented(and carry over). Just like addition:

Code:

---

AGAIN: 'increment

  Numbers(0) = Numbers(0) + 1
  For x = 0 To 10
    If Numbers(x) > 90 Then
      Numbers(x + 1) = Numbers(x + 1) + 1
      Numbers(x) = Numbers(x) - 90
    End If
  Next x

---

The Loop on the Do loop should be approximately around here.

I would suggest sorting valid Numbers() prior to storing them. This will make it easier(more efficient) to check for preexisting valid matches.

The bonus to incrementing over randomization is you can easily pause and resume the process at any time, and you're not generating the same sequences repeatedly.

Good luck, as I'm not going to code your entire assignment for you(but I have no problem answering questions). :lol:

Homework or Assignment? That was just an assumption so far.

Quote:

---

Originally Posted by Lenggries

That said, a 1-for-1 hashing between a random integer and a valid sequence, as you suggest, is almost certainly the ideal solution for sequence generation. I'm sure it could be done by almost everyone that has posted in this thread so far, but doing so and posting the solution here would hand the OP an A+ on a silver platter, and frankly, I don't think he's earned it yet.

---

That does not include me. I cannot do it.

Quote:

---

Originally Posted by FireXtol

Good luck, as I'm not going to code your entire assignment for you(but I have no problem answering questions). :lol:

---

I have a big problem answering the question.
Please code it here so I (and may be others) can learn, not just the OP.

Quote:

---

Originally Posted by anhn

Homework or Assignment? That was just an assumption so far.

---

The OP said "This is a very very hard project for me and i need an A.;(" so we assume it's a school project of some sorts.

Quote:

---

Originally Posted by baja_yu

.."Just avoid holding it in that way." - Steve Jobs ..

---

Priceless !