Array Permutation (ARGH THIS IS HURTING MY HEAD)

07-31-2012, 07:19 AM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

Array Permutation (ARGH THIS IS HURTING MY HEAD)

I cannot for the life of me figure this out... here is the deal...

I am coding a statistics program for the lottery, I am at the Pick 5 stage of the program.

here is my problem.

From A Pool of 34 numbers I am trying to generate every NON-REPEATING Unique Sequence!

So Let's Say I Have a listbox with the numbers 1 to 6...

There are only 6 5 number sequences that should only be generated with numbers 1 to 6 in the listbox:

1, 2, 3, 4, 5,
1, 2, 3, 4, 6
1, 2, 3, 5, 6
1, 2, 4, 5, 6
1, 3, 4, 5, 6
2, 3, 4, 5, 6

numbers like 5, 4, 3, 2, 1 and 2, 3, 5, 6, 1.. etc should not be generated

There are 21 5 numbers sequences that should be generated with number 1 to 7 in the listbox

1, 2, 3, 4, 5,
1, 2, 3, 4, 6
1, 2, 3, 4, 7
1, 2, 3, 5, 6
1 ,2, 3, 5, 7
1, 2, 3, 6, 7
1, 2 ,4, 5, 6
1, 2, 4, 5, 7
1, 2, 4, 6, 7
1, 2, 5, 6, 7
1, 3, 4, 5, 6
1, 3, 4, 5, 7
1, 3, 4, 6, 7
1, 3, 5, 6, 7
1, 4, 5, 6, 7
2, 3, 4, 5, 6
2, 3, 4, 5, 7
2, 3, 4, 6, 7
2, 3, 5, 6, 7
2, 4, 5, 6, 7
3, 4, 5, 6, 7

I need working code for when my listbox has at least 5 numbers in it and when it has the most of 34 numbers in it and in between as well

The listbox is already sorted so you don't need to worry about sorting them.

VB6 code plz.

Your help will be GREATLY appreciated because I have been stumped on this part for 2 weeks now and my brain cannot take it anymore with trying to keep track of whats going on with all these For Loops!.

07-31-2012, 07:44 AM

DrPunk

Senior Contributor

* Expert *

Join Date: Apr 2003

Location: Never where I want to be

Posts: 1,272

Sorry, but you saying "the listbox is already sorted" makes it difficult (for me) to work out what exactly it is you need help with?

__________________
There are no computers in heaven!

07-31-2012, 10:05 AM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

The listbox has the number pool sorted already for lowest to largest

for example... if i put it 7 numbers in list box 1... 23, 12, 14, 04, 25, 09, 08

List Box 1 Looks Like This:

04
08
09
12
14
23
25

now the generating part is the tough one.

07-31-2012, 12:29 PM

passel

Sinecure Expert

Super Moderator
* Guru *

Join Date: Jun 2003

Location: Upstate New York, usa

Posts: 7,714

I assume if you searched around there may be some established algorithm for this.
I'm not familiar with the problem, and don't plan on spending time searching myself, but off the top of my head, I think I would simply use a flag to track positions and move the flags around.
You only allow five numbers, so start with the first five possitions set to 1, and all remaining positions set to 0.
Then ripple the 0's from right to left (or you could ripple the 1's) until all 0's are on the left.
For instance, the first example

Code:

1  2  3  4  5  6
--------------
1  1  1  1  1  0 = 1 2 3 4 5
1  1  1  1  0  1 = 1 2 3 4 6
1  1  1  0  1  1 = 1 2 3 5 6
...
0  1  1  1  1  1 = 2 3 4 5 6

For your 7 case:
1  2  3  4  5  6  7
-----------------
1  1  1  1  1  0  0
1  1  1  1  0  1  0
1  1  1  0  1  1  0
1  1  0  1  1  1  0
1  0  1  1  1  1  0
0  1  1  1  1  1  0   'the first 0 has reached the left, move the next 0 to the left, reset the first back to the left of the "next" 0 and repeat
1  1  1  1  0  0  1
1  1  1  0  1  0  1
1  1  0  1  1  0  1
1  0  1  1  1  0  1
0  1  1  1  1  0  1  'move next 0
1  1  1  0  0  1  1  'etc ...

For 8 numbers 
1  1  1  1  1  0  0  0
1  1  1  1  0  1  0  0
1  1  1  0  1  1  0  0
1  1  0  1  1  1  0  0
1  0  1  1  1  1  0  0
0  1  1  1  1  1  0  0
1  1  1  1  0  0  1  0
...
0  1  1  1  1  0  1  0
1  1  1  0  0  1  1  0
...
1  1  0  0  1  1  1  0
... ...
1  1  1  1  0  0  0  1
...

It is extremly likely that there is a simple recursive process that can do this, but for 34 numbers I'm not sure how deep it would get.
The iterative method describe above should not take much code either, and you wouldn't have to worry about stack depth.

__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.

Last edited by passel; 07-31-2012 at 01:02 PM.

07-31-2012, 06:13 PM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

Hey thats an awesome idea, ill try it!!!

08-01-2012, 08:15 AM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

****it, i just spent 2 hours writing code that only works with 6 numbers....... #*$#*&$#*&$*#&@(#!!!!

08-01-2012, 09:31 AM

DrPunk

Senior Contributor

* Expert *

Join Date: Apr 2003

Location: Never where I want to be

Posts: 1,272

I have to admit that I've tried thinking about it, but it hurts my head too.

You could google for Unique Combinations and it appears there's quite a bit of code out there you can try.

__________________
There are no computers in heaven!

08-01-2012, 05:54 PM

passel

Sinecure Expert

Super Moderator
* Guru *

Join Date: Jun 2003

Location: Upstate New York, usa

Posts: 7,714

I guess it is easier to describe then it is to code.
I took DrPunk's advice and did some searching on Unique Combinations.
Not so much for the coding, as I figured my approach would work, but out of curiosity to calculating the total number of combinations we would end up with.
I found several pages that looked promising, but when I tried their equation always came up with a much larger number compared to the known sets we've already established in this thread.
Pool size, combinations
5, 1
6, 6
7, 21
8, 56
9, 126
10, 252

This page looked like it was the correct answer, but when I ran numbers through the equation, I still got much larger numbers than expected.
Post 14 of that page had a link to "The On-Line Encyclopedia of Integer Sequences" which proved to be interesting.
Entering in the sequence 1,6,21,56,126,252 and doing a search turned up the continuation of the sequence and a bunch of links to various ways that sequence may come up, such as the number of combinations of values that can occur throwing six-sided dice, (1 die = 6, 2 dice = 21, 3 dice 56, 4 dice 126, etc).

Anyway, one of the links went here which is a table of that series. According to that table, with 34 items in the pool you'll have 278,256 combinations, which is not as many as I had feared.

I'm still not sure why you have to generate them all.

Well, as far as my flag rippling method is concerned, there could be a number of approaches to take to help keep things straight. It seems like a state machine with small functions to break the process up might be a good approach, but I'll outline a less structured, nested combination of If blocks and loops, and you can try to implement that.

Code:

'Assume you set up two arrays, one initialized to your array of numbers, the other 
'initialized to five 1's and trailing 0's for however many numbers you have in your pool.
'The process kind of boils down to two repeating steps (doing either one or the other
'each time around the loop).
'At the top of the loop, you print out the current combination
'The first step is to see if the first flag is 0
'If it is not then, look for the first 0, and swap it with its left neighbor (shuffling it down)
'(you'll then loop back up, print the combination and test the first position again to see if it is a zero)
'Else (the second step (the first flag is 0))
  Find the first 0 that has a 1 to its left
  If you don't find one, you're done, exit the subroutine
  If you do find a 0 with a 1 to its left, then
    Swap them (shuffling that 0 down)
    Set a pointer to the first position (the one with the 0),and another to the left of the 0 you just swapped
    'The point here is to loop while the lower pointer is pointing to a 0 and the upper pointer is pointing to a 1.
    'if that is the case, you swap them to "pack or reset" the 0's to the right and the 1's on the left
    'as soon as the lower pointer is not pointing at a 0 or the upper is not pointing to a 1
    'they've been reset to the appropriate side.
    'In addition to the 0 and 1 on opposite sides test, as we increment and decrement the
    'pointers we have to check to make sure they don't pass each other.
    'When the pointers are equal or have passed each other, we can exit the step and 
    'return to the top of the loop.
  End If

I guess that might still be confusing, and rather than prolong the thread, I'll give the snippet of code that I used that implements the above logic, but you'll have to setup the arrays or adapt the code and provide the "print" routine to do whatever you want with the combination. I "printed" them to a multi-line text box, and for 20 numbers in the pool (15,504) combinations it took about 20 seconds to display all of them in the textbox. So, assuming the process was consistent it would take about six minutes to do a pool of 34.
As it is, the display of a pool of 20 (which I had formatted to give me a count as well, like this:

Code:

 10 17 18 19 20   15498
 11 17 18 19 20   15499
 12 17 18 19 20   15500
 13 17 18 19 20   15501
 14 17 18 19 20   15502
 15 17 18 19 20   15503
 16 17 18 19 20   15504

took 341,610 characters in the textbox, which is technically quite a bit more than the textbox officially supports (around 64K characters).
Here's the code snippet.

Code:

Option Explicit
Dim PoolNumber As Integer           'how many numbers are in the pool (really upper bound so numbers - 1)
Dim FlagArray(0 To 33) As Integer   'Up to 34 numbers (PoolNumber is upper bound, not total)
Dim NumberArray(0 To 33) As Integer

Private Sub GenerateCombos()
  Dim uz As Integer  'upper zero position
  Dim lz As Integer  'lower zero position
  Dim i As Integer
  
  Do
    PrintCombo                 'Print out the current combination
    If FlagArray(0) = 1 Then   'if the first position is not a 0 then
      uz = 1                   '  Start with the second position
      Do While FlagArray(uz) = 1  'Find the next zero
        uz = uz + 1
      Loop

      FlagArray(uz - 1) = 0     'We've found the zero so swap it down
      FlagArray(uz) = 1
    
    Else '(first position is a zero) look for a zero with a 1 on its left
      For i = 2 To PoolNumber
        If (FlagArray(i) = 0) And (FlagArray(i - 1) = 1) Then  'if we found a zero with a 1 on its left
          Exit For
        End If
      Next
      If i > PoolNumber Then Exit Do 'no 0 with a 1 on the left found, we're done with all combinations
      
      'else we found a 0 that needs to be moved down, and the 0's packed on the left moved up (reset)
      FlagArray(i - 1) = 0                   'swap the zero found with its left neighbor
      FlagArray(i) = 1
      uz = i - 1                             'point the upper pointer at it
      lz = 0                                 'point the lower pointer at the first position
      Do While FlagArray(lz) = 0             'Do while the lower pointer is pointing at a 0
        uz = uz - 1                          '  Decrement the upper pointer (point to the left of a known 0)
        If FlagArray(uz) = 1 Then            '  If upper value is a 1
          FlagArray(uz) = 0                  '    swap the upper 1 with the lower 0
          FlagArray(lz) = 1
        Else  'if our upper pointer is pointing at a zero, we've swapped everthing, so continue outer loop
          Exit Do
        End If
        lz = lz + 1      'increment the lower pointer to point to the next possible 0 to be swapped
        If lz >= uz Then 'if our pointers are passing we've swapped everything, so continue outer loop
          Exit Do
        End If
      Loop          'Loop while we have 0's and 1's to swap (resetting/packing the 1's to the left, 0's to the right)
    End If  'Our two step test, first position either is 0, or is not.
  Loop 'Loop to find all combinations
End Sub

__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.

Last edited by passel; 08-01-2012 at 06:24 PM.

08-01-2012, 09:00 PM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

shouldnt we start by setting the first 5 cells of the FlagArray to 1? I tried your code and it puts me in an infinite loop and a subscript out of range error because there are no flags set to 1 yet.

here is the code I made for PrintCombos

Code:

Public Function PrintCombo(NumPool() As String, flags() As Integer)
x = 0 'first cell ID
Do While numcount < 5 'Loop while we dont have 5 numbers generated
    If flags(x) = 1 Then  'if we have a true flag
        If numcount < 4 Then 'if we have less than 4 num generated
        Seq = Seq & NumPool(x) & ", " 'generate the number followed by a comma

        numcount = numcount + 1 'we have generated a number
    Else
        Seq = Seq & NumPool(x) 'dont add the comma if it is the last digit of the sequence
        numcount = numcount + 1 'we genereated 5 numbers
End If
Else
x = x + 1 'move on to the next
End If
Loop
List2.AddItem (Seq) 'add our sequence to the listbox
End Function

Last edited by Kemikal; 08-01-2012 at 11:53 PM.

#10

08-02-2012, 12:02 AM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

Here is some code Ive added ontop of your code for the sub "Generate Combos"....

Code:

Private Sub GenerateCombos()
Dim PoolNumber As Integer           'how many numbers are in the pool (really upper bound so numbers - 1)
Dim FlagArray(0 To 33) As Integer   'Up to 34 numbers (PoolNumber is upper bound, not total)
Dim NumberArray(0 To 33) As String
  Dim uz As Integer  'upper zero position
  Dim lz As Integer  'lower zero position
  Dim i As Integer
  
  PoolNumber = List1.ListCount - 1
  For i = 0 To PoolNumber
    NumberArray(i) = List1.List(i)
Next i

  
FlagArray(0) = 1
FlagArray(1) = 1
FlagArray(2) = 1
FlagArray(3) = 1
FlagArray(4) = 1
  
  Do
    Call PrintCombo(NumberArray(), FlagArray())                'Print out the current combination
    If FlagArray(0) = 1 Then   'if the first position is not a 0 then
      uz = 1                   '  Start with the second position
      Do While FlagArray(uz) = 1  'Find the next zero
        uz = uz + 1
      Loop

      FlagArray(uz - 1) = 0     'We've found the zero so swap it down
      FlagArray(uz) = 1
    
    Else '(first position is a zero) look for a zero with a 1 on its left
      For i = 2 To PoolNumber
        If (FlagArray(i) = 0) And (FlagArray(i - 1) = 1) Then  'if we found a zero with a 1 on its left
          Exit For
        End If
      Next
      If i > PoolNumber Then Exit Do 'no 0 with a 1 on the left found, we're done with all combinations
      
      'else we found a 0 that needs to be moved down, and the 0's packed on the left moved up (reset)
      FlagArray(i - 1) = 0                   'swap the zero found with its left neighbor
      FlagArray(i) = 1
      uz = i - 1                             'point the upper pointer at it
      lz = 0                                 'point the lower pointer at the first position
      Do While FlagArray(lz) = 0             'Do while the lower pointer is pointing at a 0
        uz = uz - 1                          '  Decrement the upper pointer (point to the left of a known 0)
        If FlagArray(uz) = 1 Then            '  If upper value is a 1
          FlagArray(uz) = 0                  '    swap the upper 1 with the lower 0
          FlagArray(lz) = 1
        Else  'if our upper pointer is pointing at a zero, we've swapped everthing, so continue outer loop
          Exit Do
        End If
        lz = lz + 1      'increment the lower pointer to point to the next possible 0 to be swapped
        If lz >= uz Then 'if our pointers are passing we've swapped everything, so continue outer loop
          Exit Do
        End If
      Loop          'Loop while we have 0's and 1's to swap (resetting/packing the 1's to the left, 0's to the right)
    End If  'Our two step test, first position either is 0, or is not.
  Loop 'Loop to find all combinations
End Sub

I am getting the following results for a pool of 6 numbers (1 to 6)

01, 01, 01, 01, 01
01, 01, 01, 01, 01
01, 01, 01, 01, 01
01, 01, 01, 01, 01
01, 01, 01, 01, 01
02, 02, 02, 02, 02

seems to loop properly in terms how many sequences is should generate (6 num gives me 6, and 7 gave me 21)

but just wrong/repeating numbers in the sequence

#11

08-02-2012, 12:06 AM

Kemikal

Newcomer

Join Date: Feb 2006

Posts: 14

woops forgot to add x = x + 1 in the print combos part... worked for 6 numbers, checking 7... 7 worked.... checking 8......... 8 worked........... Looks like it works!!!!!!!! hmmm when I put 34 numbers it looks like it only generated 16,112 different combos?

Could it be cause the ListCount value of a listbox is an integer, so we could only have (0 to 32,767) so after is exceeds 32,767 it resets back to 0?

Edit:

Yes this was the problem.... good work Passal I just added a lil counter and it ended 278,256...

GREAT WORK... SALUTE!!!

Last edited by Kemikal; 08-02-2012 at 12:28 AM.

#12

08-02-2012, 10:59 AM

passel

Sinecure Expert

Super Moderator
* Guru *

Join Date: Jun 2003

Location: Upstate New York, usa

Posts: 7,714

Quote:

Originally Posted by Kemikal

shouldnt we start by setting the first 5 cells of the FlagArray to 1? ...

From my post

Quote:

...

Code:

'Assume you set up two arrays, one initialized to your array of numbers, the other 
'initialized to five 1's and trailing 0's for however many numbers you have in your pool.
...

Glad you worked it out.
My test version attached. Enter numbers, 1 line per number in the left textbox, press the button, output in the other textbox.

p.s. I added code to hide the output textbox and then show it after the combos have been generated, and that speeds up thing 6 to 10 times, i.e.
20 numbers went from 20 some seconds to 2.8.
It took 59 seconds to do 34, rather than the estimated 6 minutes (which I didn't try).
I'm sure than can be other optimizations to speed things up quite a bit, (like using numeric arrays rather than strings for collecting the output combos).

Attached Files

Pick5gen1.zip (2.8 KB, 1 views)

__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.

Last edited by passel; 08-02-2012 at 11:49 AM.