Solved

Every possible combination code.

Posted on 2000-03-24
83
1,459 Views
Last Modified: 2012-06-27
I need a piece of code that can give me every possible combination for a situation.  Here is the situation

A user has on  his screen a text box for every hour of the day (24 text boxes).  s/he enters into each box the total number of entities they requre on site in each hour.

ie.

00:00  |  01:00  | 02:00 | 03:00 |  04:00  |  05:00  |
    1             1           2           2           3             3

I need to place  in an array every possible start and finish time  to have these entities on site.

ie.

Entity One:  00:00 - 05:00
Entity  Two: 02:00 - 04:00
Entity Three: 04:00 - 05:00

Above  would be  one combination

Another may be to have 12 different entities all there  for only one hour each.

Thank you in advance,

Quatro
0
Comment
Question by:Quatro
83 Comments
 
LVL 1

Expert Comment

by:mb1ake
Comment Utility
What is it that you are trying to accomplish?
0
 

Expert Comment

by:Staz
Comment Utility
Is one hour the minimum an entity can work and 8 hours the maximum? And what are the maximum number of entities that can be on site at one time?
0
 

Expert Comment

by:Staz
Comment Utility
Is one hour the minimum an entity can work and 8 hours the maximum? And what are the maximum number of entities that can be on site at one time?
0
 
LVL 6

Expert Comment

by:billy21
Comment Utility
One hour is the minimum 24 hours  is the  maximum
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Billy and Staz,
Yes 1 hour is the minimum number of hours  an entity can be active and 24 hours is the maximum an  entity can  be active.

mb,
I've been experimenting with  genetic algorithms.  They seem to work in many situations such as locating bus stops and radio transmitters.  I  do however have trouble using my inventory in the most effective  manner possible at a job site.  Genetic Algorithms suck at that.  I figure this  way I can create every possible situation and  choose the best one without having to think too much about it.

Quatro
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
I should add that the time periods don't have to be attached to a particular entity or barcode.  I usedthe terms "Entity 1:" etc to make the problem easier to understnad.  A simple list of startand finish times will be fine.

Thanks,

Quatro
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Adjusted points from 600 to 800
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
When I attempted this the biggest hurdle I had was having multiple length timeperiods in  a combination.  For instance several one hour time periods followed by a 3 hour time period and possibly a 24 hour time period and coming up with every combination.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Adjusted points from 800 to 1000
0
 
LVL 28

Expert Comment

by:AzraSound
Comment Utility
can you explain again what the time involvement is?  minimum number of entities at that hour?  so there can be more present at that hour but not less?
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
That is the exact number of entities active at that hour.  There can be no more and no less.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
For  example. If the scenario was something like this:

00:00  |  01:00  | 02:00 | 03:00 |  
   1         2       2        2

Only one entity could be active for the first hour.  The time periods could be:

Combo 1
00:00 - 03:00
01:00 - 03:00

Combo 2
00:00
01:00 - 03:00
01:00 - 03:00

Combo 3
00:00
01:00
01:00 - 03:00
02:00 - 03:00

Combo 4
00:00
01:00
01:00
02:00 - 03:00
02:00 - 03:00

Etc.
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
I thought about the problem, and came to the following results:
* The "simplest" will be using a recursive algorithm (however approaching the physical limits). I may try how i imagine the solution method (but this will take some lines to explain)
* This will take much time to run (development is not too diffucult)
* You may fix a limit the maximum entities for one hour
* You should fix the maximun entities to shorten execution of the solution
* Do you post such a question in Access section, because you want to develop it in access (horror). Things like this MUST be developed in languages like C/C++/lisp/... if you want to get a result during your lifetime (smile)
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Thank you for your response Angel.  I have done many things in access that people say cannot or should not be done.  This I intend to at least first attempt to work in access before I make a decision to purchase VB or C++ Enterprise editions.  I do of course understand your concerns however people do tend to underestimate the power of msaccess and VBA.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
For this task I consider anywhere up to 5 mins to be an acceptable runtime.  If access cannot do this I will convert.
0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Nice problem !
As stated before, probably the best way is to try the gaming section, as they often struggle with this type of problems too.

However I'll try to give it a theoretical shot how I would approach this.

To start with I would build a table containing all possible length entries, with as many occurrences as the minimum value entered in that range.

This table I would process using two pointers. The base-pointer for the combination and a control pointer to work through the remaining entries untill a good combination is found.
This control pointer starts at the value of the base pointer and progresses throug the combinations and will return to its starting position of the first accepted entry + 1 to check for new combinations.

Confused ? I would be, therefor a small sample:

00:00  |  01:00  | 02:00
   1         2       2

Level 1 hour entries:
00:00
01:00
02:00
Level 2 hour entries:
00:00 01:00 (minimum is 1)
01:00 02:00
01:00 02:00 (minimum is 2)
Level 3 hour entries:
00:00 02:00 (minimum is 1)
To make it easy these entries are "converted" to a string table like:
Level 1:
x--
-x-
--x
Level 2:
xx-
-xx
-xx
Level 3:
xxx

To find the combinations you accept every combination of lines that (added up) contains xxx.
So base-pointer starts with 1
x--
Position pointer starts with 2
-x-
This is added and as "sum" is xx- we'll continue with next:
--x
This adds up so first combination found:
x--
-x-
--x
As all following entries will be acceptable now, you can add them in a loop. First by adding all single rows (creating 4 entry combinations), then adding to these 4 entry combinations  combinations every other single entry <> the entry of the 4 entry combination and so on.....
Then reset position-pointer to 2 and reset combination to value of base pointer:
x--
position-pointer finds:
--x
No match add next:
xx-
Match and the above story starts again.
Etc.etc.

For your 24 * 12 table this will create an enormous number of combinations, so you are warned!
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Nico,

The level 1 hour entries would actually be:
00:00
01:00
01:00
02:00
02:00

or perhaps

00:00  - 1
01:00  - 2
02:00  - 2

Level 2  would be
00:00 - 01:00
01:00 - 02:00
02:00

There has to be a combination of time periods.  The best solution may contain a 1 hour time period 2 x 5 hour time periods a 12 hour time period and a 24 hour time period for instance.  I need every combination of time periods that fit the criteria.

It would be even more useful if the programmer or user could suggest some limits for the time periods.  However, it would still have to be capable of both extremes.

When you talk of a table are you referring to an access database table?  I thought it would be more appropriate to use an array.

I think I would understand an algorithm in pseudo code or structured english better.  If possible though I would prefer VBA code.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Adjusted points from 1000 to 1030
0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Your correct about the level1 hours.
So you got that part.

Building the temporary x--, -x-, etc will be clear too I assume.
store them in a table or better perhaps a collection called colTemp.

The rest of the solution in pseudocode:

'Initialize pointers
base-pointer = 1
posi-pointer = 2


DO WHILE base-pointer < colTemp.count
 'Init combination array (or collection?) for solutions
 intCountComb = 0
 comb(intCountComb) = colTemp(base-pointer)
 'init posi match string
 strPosimatch = "---"
 'Build combination(s)
 posi-pointer-loop = posi-pointer
 DO WHILE strPosimatch <> "xxx" and posi-pointer-loop < coltemp.count
  'Here you need a function that replaces the "-" in the strPosimatch
  'Binary speeking when it are 0 and 1 bits you would perform
  'a logocal AND
  strPosimatch = strPosimatch "AND" colTemp(posi-pointer-loop)
  'store found rows
  intCountComb = intCountComb + 1
  comb(intCountComb) = colTemp(posi-pointer-loop)
  posi-pointer-loop = posi-pointer-loop + 1
 WEND

 'test ready when strPosimatch <> "xxx" and end of collection/array reached
 'just testing strPosimatch will do the trick
 if strPosimatch <> "xxx" then
  exit
 else
  'valid combination found
  'nb * stands for number of items in comb()
  'nb x stands for loopcount for result table/array/column
  'first store "basic" found combination like:
  store all entries from comb(*) to one new entry of result(x)
  'start creation combinations easiest with double loop:
   for i = posi-pointer to colTemp.count
    'start with basic comb and add each time the next entry
    intCountComb = intCountComb + 1
    comb(intCountComb) = colTemp(i)
    write to result(x)  
    'save to combSave to be able to return to previous comb when ready with j loop
    loop move comb(*) to combSave(*)
    for j = i + 1 to colTemp.count
     'always start with saved set and add/overwrite last single j-entry
     combSave(* + 1) = colTemp(j)
     write to result(x)  
    next j
   next i
 endif
 '
 base-pointer = basepointer + 1
End do
 
Basically this is the pseudo code.
It's rough and you'll need to make some functions for comparing the -x- strings (personally I would try to do this in another language, offering me the possibility to store the 24 hrs in 3 bytes and manipulate the bits with a logical AND)
And have a result table/array/collection created, but basically that won't disrupt the logical processing.
And have a function to translate the -x- string back.
When the number of time periond are limited, you should test the intCountComb as this contains the number of time periods.

Success
0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Oooops
Forgot to continue with the posi-pointer, read the end as:

 base-pointer = basepointer + 1
' posi-pointer starts always with next to basepointer entry
basepointer + 1
End do
0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Oooops again:

 base-pointer = basepointer + 1
 ' posi-pointer starts always with next to basepointer entry
 posi-pointer = basepointer + 1
End do

BTW you speak of a best solution, is this also an algoritm, that can perhaps cut down on the number of "result" entries drastically!
0
 
LVL 7

Expert Comment

by:Believer
Comment Utility
(Referring to your original question): Do the hours for any given entity have to be contiguous?  In other words, for your original set of data:

00:00  |  01:00  | 02:00 | 03:00 |  04:00  |  05:00  |
    1             1           2           2           3             3

Is this a valid solution:

Entity 1: 0:00 - 3:00, 4:00-5:00
Entity 2: 2:00 - 4:00
Entity 3: 4:00 - 5:00
Entity 4: 3:00 - 4:00

0
 
LVL 28

Expert Comment

by:AzraSound
Comment Utility
how is that different from
Entity 1: 0:00 - 5:00???
0
 
LVL 7

Expert Comment

by:Believer
Comment Utility
It introduces a fourth entity AND breaks the first entity's hours into two segments.  (Entity 1 is *not* in the time slot 3:00-4:00.)
Quatro said that, at an extreme, every hour slot could be a different entity.  I'd like to know if it's valid to break an entity's hours up (e.g. non-contiguous).
0
 
LVL 1

Accepted Solution

by:
Xaphire earned 745 total points
Comment Utility
I think this problem can be solved using solutions generation and backtracking. It might not be the most efficient way, but I think it's possible.

For a given problem, for example00:00  |  01:00  | 02:00 | 03:00 |  04:00 |  
     1        1       2        3

The maximum number of entities any solution will have is the sum of the numbers needed (1+1+2+3) = 7, corresponding to the solution with each entity only appearing for one hour.

You can then build a boolean matrix

   |  01:00  | 02:00 | 03:00 |  04:00  
ent1
ent2
ent3
ent4
ent5
ent6
ent7

where each place in the matrix corresponds to an entity being present or not.

In this case, this would give you 7 (max. number of entities) * 24 (number of hours in the real problem) ^ 2 = 28,224 possible solutions. Quite a lot, but not impossible with Access.

Of these, only the ones where the sum of the column equals the desired amount of entities are feasible solutions.

For example:

   |  01:00  | 02:00 | 03:00 |  04:00  
ent1    1         0      0       1
ent2    0         1      0       1
ent3    0         0      1       1
ent4    0         0      1       0
ent5    0         0      0       0
ent6    0         0      0       0
ent7    0         0      0       0
--------------------------------------
        1         1      2       3
would be a correct solution,

where
   |  01:00  | 02:00 | 03:00 |  04:00  
ent1    1         1      1       1
ent2    1         1      1       1
ent3    1         1      1       1
ent4    1         1      1       1
ent5    1         1      1       1
ent6    1         1      1       1
ent7    1         1      1       1
--------------------------------------
        7         7      7       7

is not.

A stupid algorithm would be to generate all possible solutions, and then filter out the correct ones.

You can use backtracking to apply the filter criterium during the generation of the solutions, quiting the work on the current solution if the constraints are violated. The constraint would be when the column sum exceeds the needed amount. If in fact an entity may only be 'alive' once (contigiously), you can add this as a constraint as well. (See Believers question)

I know this is all theoretical talk, but maybe this can help you or some other programmer a little. Like you, I think Access is underestimated :-) I have a 4 GB Access database with 250,000,000 records in one of my tables for my Master's project...
0
 
LVL 1

Expert Comment

by:Xaphire
Comment Utility
I'm sorry, the numbers didn't align right. Hope it's still readable, though :-)
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Can a given entity be on site during more than one separate interval?
Would a re-numbering of the entities count as a different combination?
(even if not, there could still be a huge number of possible combinations, are you sure you want to fill an array with every possible one?)
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Xaphire & Nico,

I see what you mean about keeping only best soluutiions.  I intended to take your code and include a generic weighting system (user can modify the weights).  I didn't mention it because I thought it would complicate the issue.  If you can give me code that creates every solution I can add the weighting system.  Of course you could add such a system with your code if you wish , however it isn't the area I am having  trouble with.  At runtime Iwill check to see if  one solution weighs higher than the current.  Perhaps I  will keep only the top five but my understanding is that even if I do this I require every possible combination simply to be compared with the current list.

Believer,

The important part of this exercise is the time periods rather than the individual entities.  I need a set  of time periods first then I can think about which entity# is placed where and in how many timeslots.

Everyone,

I'll check out the algorithms and get back to you all ASAP.  I'm guessing its the middle of the night for most.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Ozo,

In this exercise there is no need to  actually place an entitiy to a  timeslot.  I apologise to everybody for this.  I mislead everybody by using the:

Entity1: .........

What I meant was an entity will be placed in that time slot eventually.  They entity placed  in the first timeslot could also be placed in the last etc.  Don't worry about that though.  Just produce a set of timeslots with the view that later these timeslots will be filled by entities.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Ozo,

In this exercise there is no need to  actually place an entitiy to a  timeslot.  I apologise to everybody for this.  I mislead everybody by using the:

Entity1: .........

What I meant was an entity will be placed in that time slot eventually.  They entity placed  in the first timeslot could also be placed in the last etc.  Don't worry about that though.  Just produce a set of timeslots with the view that later these timeslots will be filled by entities.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
It's not hard to generate all possible solutions, except that there can easily be trillions of them.
If you're looking for the best solution, what makes one solution better than another?
0
 
LVL 6

Expert Comment

by:billy21
Comment Utility
Ok here are some weights I was playing with.

Positive Weights
Highest Weight -  12 hour timeslots  (these are most preferred)
                         -  10  hour timeslots
                         -   8 hour timeslots
                         -   5 hour timeslots
                         -   4 hour timeslots
Negative Weights
Lowest              -  1 hour timeslots  (These are least preferred)
                          - 24 hour timeslots
                         -  2 hour timeslots
                         -  23 hour timeslots
                         -  3 hour timeslots
                         - 22 hourtimeslots
                         - 21 hourtimeslots
                         - 20 hourtimeslots
                         - 19 hourtimeslots
                         - 18 hourtimeslots
                         - 17 hourtimeslots
                         - 16 hourtimeslots
                         - 15 hourtimeslots
                         - 14 hourtimeslots
                         - 13 hourtimeslots

For instance a situation where 24 x 1  hour periods all reqired 1 entity the best option would be:
00:00 - 11:00
12:00 - 23:00

I'm assuming everybody understands that when I specifyan hour I mean the entire hour.  In this case 23:00 actually would be 23:59.

Note also that the user would have to be able to specify these weights.

0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Quatro,

I've to agree with ozo that the number of solutions just can be too big.

Lets say the maximum is entered and suppose the total number of combinations is the modulus of (24-1) being: 23*22*21*20......etc
The total number of combinations will then be  2,5852016738885 E+22
Oke, it's probably the worst scenario but...

To solve these type of problems generally you would take a different approach: Let the user specify what out come he finds reasonable. Generate first the 'less' combinations (my pseudo-code minus the double "i-j" loop)
and weigh every outcome. When within the user's expectations just stop.
When not, show the best result and ask or further processing is wanted.

Then start the first "i" loop for all 'less' combinations and give the best when better but again ask whether or not to continue.(you might decide here only to continue to work here with the most promesing values like the top 10 and with 5 randomly choosen, thus creating a sort of genetic algorithm)

This way you are giving the user control and let him decide whether he wants to wait for better results or not.

Another help for the user (and always appealing) might be the display of found (best) results graphically. (kind of progressbar)

From your comment I read that you would like to have the code to generate all combinations. Regrettably I don't have enough time to write it. I'm more the theoretical guy and when I did this type of programming in the past (I wrote some logical puzzle solution programs) I was having a vacation and found out that writing the code and getting it working was very rewarding but also very time consuming. Also seeing the fact that you have to add a weighing algoritm and probably some intermediate "user-stops", I think it's better to write the code yourself, being better equipped to add changes to it.
However if you are having troubles with the creation, drop me a line (address in profile) and I'll try to solve it.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Billy21,

You've just given me an idea that may reduce the number dramatically.

Your rating system looks good but what if I had some absolute values.  What if the user specifies the lengths of the shifts s/he wants.  For instance Instead of having any lengths between 1 and 24 the user specified only 4 or 5 lengths that are appropriate.  If they cannot be filled perfectly then we settle for the "best fit" scenario.

12 hour timeslots
8 hour timeslots
5 hour timeslots
4 hour timeslots

How does that sound Nico?  I only really need at maximum 6 different time lengths.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
For instance

if the user said only 11 hour timeslots were appropriate and you require 24 x 1 entity then the best fit may be:

00:00 - 10:00
11:00 - 22:00
13:00 - 23:00

You end up with more entities than needed in this case however to avoid that the user would have to specify a criteria that is actually possible.
0
 
LVL 54

Expert Comment

by:nico5038
Comment Utility
Quatro,

Billy's system can be implemented easily in the pseudocode sample I gave you.
Basically you only need a sort!
After building the "-x-" table/array/collection as I colled it, you can decide to sort it to get the wanted timeslots at the start.
This can be achieved in two ways:
1) Just place a column with the length in front of it and sort this descending to get the longest first
or
2) a column with a grade and a length.
(Using both releases the user from the task to rate all lengths and by adding the length you still can get the longest first)
To make it visible just a sample:
ad 1)
03 xxx
02 xx-
02 -xx
02 -xx
01 x--
01 -x-
01 --x
ad 2)
A 02 xx-
A 02 -xx
A 02 -xx
B 01 x--
B 01 -x-
B 01 --x
B 03 xxx
As you want a maximum of six, just stop when the [intCountComb] has reached this value. When all hours are covered then take result, otherwise stop acessing this solution.
Perhaps you can make this maximum also "user adjustable".







0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Sounds good to me.  I will try write the code to all the algorithms posted here and award the points to the algorithm that operates most efficiently.  New algorithms are also welcome of course.

Thanks,

Billy
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Quatro:
* I left off yesterday, as i wanted to switch from my slow job pc (IDE/P200/64MB Ram) to my private PC(SCSI-UW2/2xPII 350/256MB Ram) to get some results. Unfortunately, the solution is build in VB6, but you may be able to transform it in Access, as almost nothing is in the interface part.

* As I could not follow the discussion meanwhile, i could not adjust the coding eventually.

If you don't know how to handle the 3 modules (Form1.frm, module1.bas and class1.cls) i may provide additional hints.

----------FORM1.FRM------------
VERSION 5.00
Begin VB.Form Form1
   Caption         =   "Form1"
   ClientHeight    =   5340
   ClientLeft      =   60
   ClientTop       =   345
   ClientWidth     =   14370
   LinkTopic       =   "Form1"
   ScaleHeight     =   5340
   ScaleWidth      =   14370
   StartUpPosition =   2  'CenterScreen
   WindowState     =   2  'Maximized
   Begin VB.CommandButton cmdReset
      Caption         =   "Reset"
      Height          =   375
      Left            =   1800
      TabIndex        =   5
      Top             =   0
      Width           =   1455
   End
   Begin VB.ListBox lstCombinations
      Height          =   3210
      Left            =   0
      Style           =   1  'Checkbox
      TabIndex        =   4
      Top             =   960
      Width           =   975
   End
   Begin VB.TextBox txtResult
      BeginProperty Font
         Name            =   "Courier"
         Size            =   9.75
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   3255
      Left            =   1080
      Locked          =   -1  'True
      MultiLine       =   -1  'True
      ScrollBars      =   2  'Vertical
      TabIndex        =   3
      Top             =   960
      Width           =   12615
   End
   Begin VB.CommandButton cmdCalc
      Caption         =   "Calculate Now"
      Height          =   375
      Left            =   120
      TabIndex        =   2
      Top             =   0
      Width           =   1335
   End
   Begin VB.TextBox txtUnits
      Alignment       =   1  'Right Justify
      Height          =   285
      Index           =   0
      Left            =   120
      TabIndex        =   0
      Top             =   600
      Width           =   615
   End
   Begin VB.Label lblHour
      Caption         =   "00h-01h"
      Height          =   255
      Index           =   0
      Left            =   120
      TabIndex        =   1
      Top             =   360
      Width           =   615
   End
End
Attribute VB_Name = "Form1"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Option Explicit

Private mdatInit As Distribution


Private Sub cmdCalc_Click()
  Dim intLoop As Integer
  Static datStart
 
  Dim intData As Integer
 
  Dim objDistribution As clsDistribution
 
  If gblnInterrupt Then
    gblnInterrupt = False
    cmdCalc.Caption = "Stop"
    datStart = Timer
   
    gintMaxUnits = 0
    For intLoop = MIN_HOUR To MAX_HOUR
      intData = Val(txtUnits(intLoop).Text)
      If intData > gintMaxUnits Then
        gintMaxUnits = intData
      End If
    Next
   
    lstCombinations.Clear
    Set mcolResults = New Collection
   
    Set objDistribution = New clsDistribution
    With objDistribution
      .InitDistribution mdatInit
      .Calculate
    End With
    gblnInterrupt = True
  End If
  gblnInterrupt = True
  cmdCalc.Caption = "Calculate Now"

  Caption = "Found " & mcolResults.Count & " Combinations (Elapsed time=" & Timer - datStart & ")"
  For intLoop = mcolResults.Count - 1 To 0 Step -1
    On Error GoTo Err
    lstCombinations.AddItem "K" & intLoop
  Next
 
Err:
End Sub


Private Sub cmdReset_Click()
  Dim intLoop As Integer
  For intLoop = MIN_HOUR To MAX_HOUR
    txtUnits(intLoop).Text = 0
  Next
 
End Sub

Private Sub Form_Load()
  Dim intLoop As Integer
   
  Visible = True
  gblnInterrupt = True
  DoEvents
 
  For intLoop = MIN_HOUR + 1 To MAX_HOUR
    Load lblHour(intLoop)
    With lblHour(intLoop)
      .Move lblHour(intLoop - 1).Left + .Width, lblHour(intLoop - 1).Top
      .Caption = Format(intLoop, "00") & "h-" & Format(intLoop + 1, "00") & "h"
      .Visible = True
    End With
 
    Load txtUnits(intLoop)
    With txtUnits(intLoop)
      .Move txtUnits(intLoop - 1).Left + .Width, txtUnits(intLoop - 1).Top
      .Visible = True
    End With
  Next
 
  cmdReset = True
End Sub

Private Sub Form_Terminate()
  Set mcolResults = Nothing
End Sub


Private Sub lstCombinations_ItemCheck(Item As Integer)
  Dim intLoop As Integer
  Dim intFound As Integer
  Dim strKey As String
  Dim clsData As clsDistribution
   
  txtResult = ""
  For intLoop = 0 To lstCombinations.ListCount - 1
    If lstCombinations.Selected(intLoop) Then
      intFound = intFound + 1
      strKey = lstCombinations.List(intLoop)
      Set clsData = mcolResults.Item(strKey)
     
      txtResult = txtResult & "Combination " & intFound & vbCrLf _
                & "-------------------------" & vbCrLf _
                & clsData.Display & vbCrLf _
                & clsData.Status & vbCrLf
    End If
  Next
End Sub

Private Sub txtUnits_Change(Index As Integer)
  Dim intLoop As Integer
  Dim intData As Integer
 
  intData = Val(txtUnits(Index).Text) - 1
  mdatInit.Avail(Index) = intData + 1
  For intLoop = MIN_UNIT To MAX_UNIT
    mdatInit.Unit(Index, intLoop) = IIf(intData < intLoop, -1, 0)
  Next
End Sub

Private Sub txtUnits_LostFocus(Index As Integer)
  Dim intData As Integer
  intData = Val(txtUnits(Index).Text)
  If intData > MAX_UNITS Then
    intData = MAX_UNITS
  End If
  txtUnits(Index).Text = intData
End Sub


--------- Module1.bas -------------
Attribute VB_Name = "Module1"
Option Explicit

Public Const MAX_UNITS = 265
Public Const MIN_HOUR = 0
Public Const MAX_HOUR = 23
Public Const MIN_UNIT = 0
Public Const MAX_UNIT = 10

Public gblnInterrupt As Boolean
Public gintMaxUnits As Integer


Public Type Distribution
  Unit(MIN_HOUR To MAX_HOUR, MIN_UNIT To MAX_UNIT) As Integer
  Avail(MIN_HOUR To MAX_HOUR) As Integer
End Type

Public gdefDistribution As Distribution

Public mcolResults As Collection

-------------- Class1.cls -----------
VERSION 1.0 CLASS
BEGIN
  MultiUse = -1  'True
  Persistable = 0  'NotPersistable
  DataBindingBehavior = 0  'vbNone
  DataSourceBehavior  = 0  'vbNone
  MTSTransactionMode  = 0  'NotAnMTSObject
END
Attribute VB_Name = "clsDistribution"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = True
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
Option Explicit

Public mintStartHour As Integer
Public mintStartUnit As Integer


Public mintUnits As Integer
Public mintIntervalSize As Integer

Private mdatDistribution As Distribution


Friend Sub InitDistribution(Init As Distribution)
  LSet mdatDistribution = Init
End Sub


Private Function GetIntervalSize() As Boolean
  Dim blnStop As Boolean
  Dim blnFound As Boolean
 
  mintIntervalSize = 0
 
  'Find the leftmost, bottommost 0 in the grid
  mintStartHour = MIN_HOUR
 
  While Not (blnStop Or blnFound)
    blnFound = mdatDistribution.Avail(mintStartHour) > 0
    If blnFound Then
      mintStartUnit = MIN_UNIT
      While Not mdatDistribution.Unit(mintStartHour, mintStartUnit) = 0
        mintStartUnit = mintStartUnit + 1
      Wend
    Else
      mintStartHour = mintStartHour + 1
    End If
    blnStop = mintStartHour > MAX_HOUR
  Wend
 
  ' there is an interval, check it's size
  If blnFound Then
    blnStop = False
    While Not blnStop
      'increase the interval size
      mintIntervalSize = mintIntervalSize + 1
      'stop if the end of the hours arrived
      blnStop = (mintStartHour + mintIntervalSize > MAX_HOUR)
      'now check (if item exists) if <> -1
      If Not blnStop Then
        blnStop = mdatDistribution.Avail(mintStartHour + mintIntervalSize) = 0
      End If
    Wend
  End If
 
  GetIntervalSize = (mintIntervalSize > 0)
End Function

Public Sub Calculate()
  Dim intLoop As Integer
  Dim intHour As Integer
  Dim clsCalculate As clsDistribution
 
  If GetIntervalSize Then
    mintUnits = mintUnits + 1
   
    'limit the damages
    If mintUnits > MAX_UNITS Then Exit Sub
   
    'now we have to calculate all the variations on this interval,
    'and create a new clsDistribution to calculate the rest
    For intLoop = 1 To mintIntervalSize
      'what hour will be the starthour for the next distribution class
      intHour = mintStartHour + intLoop - 1
     
      'what is the unit
      mintStartUnit = MIN_UNIT
      While mdatDistribution.Unit(intHour, mintStartUnit) > 0
        mintStartUnit = mintStartUnit + 1
      Wend
           
      mdatDistribution.Unit(intHour, mintStartUnit) = mintUnits
      mdatDistribution.Avail(intHour) = mdatDistribution.Avail(intHour) - 1
     
      Set clsCalculate = New clsDistribution
      With clsCalculate
        .InitDistribution mdatDistribution
        .mintUnits = mintUnits
        .Calculate
      End With
      Set clsCalculate = Nothing
      If gblnInterrupt Then Exit Sub
    Next
  Else
    If mintUnits > 0 Then
      mcolResults.Add Me, "K" & mcolResults.Count
      Form1.Caption = "Found " & mcolResults.Count & " combinations so far..."
      Status
    End If
  End If
End Sub

Public Function Display() As String
  Dim intUnit As Integer
  Dim intHour As Integer
 
  Dim intUnitID As Integer
  Dim intStartHour As Integer
  Dim intEndHour As Integer
 
  Dim strResult As String
 
  For intUnitID = 1 To mintUnits
    intStartHour = -1
    intEndHour = -1
    For intHour = MIN_HOUR To MAX_HOUR
      For intUnit = MIN_UNIT To MAX_UNIT
        If mdatDistribution.Unit(intHour, intUnit) = intUnitID Then
          If intStartHour = -1 Then
            intStartHour = intHour
            intEndHour = intHour
          Else
            intEndHour = intHour
          End If
        End If
      Next
    Next
   
    strResult = strResult & "UNIT " & Format(intUnitID, "00") & ": " & Format(intStartHour, "00") & "h-" & Format(intEndHour + 1, "00") & "h" & vbCrLf
  Next
   
'    intUnitID = -1
'    For intHour = MIN_HOUR To MAX_HOUR
'      If mdatDistribution.Unit(intHour, intUnit) = -1 Then
'        If intUnitID <> -1 Then
'          'stop the previous charge:
'          intEndHour = intHour - 1
'          strResult = strResult & "UNIT " & Format(intUnitID, "00") & ": " & Format(intStartHour, "00") & "h-" & Format(intEndHour + 1, "00") & "h" & vbCrLf
'          intUnitID = -1
'        End If
'      Else
'        Select Case intUnitID
'          Case -1
'            'start a new charge:
'            intUnitID = mdatDistribution.Unit(intHour, intUnit)
'            intStartHour = intHour
'          Case mdatDistribution.Unit(intHour, intUnit)
'            'continue the current charge:
'
'          Case Else
'            'stop the previous charge...:
'            intEndHour = intHour - 1
'            strResult = strResult & "UNIT " & Format(intUnitID, "00") & ": " & Format(intStartHour, "00") & "h-" & Format(intEndHour + 1, "00") & "h" & vbCrLf
'            '...and start the new charge
'            intUnitID = mdatDistribution.Unit(intHour, intUnit)
'            intStartHour = intHour
'        End Select
'      End If
'    Next
'
'    If intUnitID <> -1 Then
'      'Finish the last charge:
'      intEndHour = MAX_HOUR
'      strResult = strResult & "UNIT " & Format(intUnitID, "00") & ": " & Format(intStartHour, "00") & "h-" & Format(intEndHour + 1, "00") & "h" & vbCrLf
'    End If
'  Next
  Display = strResult
End Function


Public Function Status() As String
  Dim intHour As Integer
  Dim intUnit As Integer
 
  Dim strResult As String
 
  strResult = "@ |"
  For intHour = MIN_HOUR To MAX_HOUR
    strResult = strResult & Format(intHour, " 00") & "&"
  Next
  strResult = strResult & vbCrLf
 
  For intUnit = gintMaxUnits To MIN_UNIT Step -1
    strResult = strResult & Format(intUnit, "00") & "|"
    For intHour = MIN_HOUR To MAX_HOUR
      If mdatDistribution.Unit(intHour, intUnit) = -1 Then
        strResult = strResult & "- 1&"
      Else
        strResult = strResult & Format(mdatDistribution.Unit(intHour, intUnit), "000") & "&"
      End If
    Next
    strResult = strResult & vbCrLf
  Next
 
  Form1.txtResult = strResult & vbCrLf
  DoEvents
  Status = strResult
End Function

0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Some comments however:
* This algorythm (as other algos also) need an Exponential time to calculate the combinations.
* The optimal combinations will be found last
* With the setting 1-1-1-2-2-2-3-3-4-3-3-3-4-3-3-3-2-2-2-2-2-1-1 i stopped after 110 seconds and 15'000 combinations found (please refer to my computer config), just to give you a sample of it (a setting of 1-2-1 was completed in 0.2 seconds).
0
 
LVL 7

Expert Comment

by:JimMorgan
Comment Utility
I believe that the problem can be solved with tables and queries.  I did a similar task several years ago so that a person could calculate the odds of wins at a roulette table for a particular set of numbers.

Tomorrow I will look up the DB which did this and see if it can be applied here.
0
 

Expert Comment

by:isasori
Comment Utility
If to fill in all 24 hours by one entity, then variants will be  2 ^ (24-1).
For two at one o'clock : (2 ^ (24-1) * 2 ^ (24-1)).
Etc.
You are sure, what can allocate the array of such size?
Correct me, if I am wrong.
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 4

Expert Comment

by:wileecoy
Comment Utility
Quatro -

Let me clarify, forgive me for not knowing already - after reading most of the messges, I found that I became more, not less confused.

I beleive that you can do this through Access and VBA.

It appears that you are scheduling "Entities" to be present based on the requirements that your user enters into the system.

Also - it appears that your program is intended to tell the user how many "Entities" will be required, and when the shifts will begin and end.

Am I okay so far?

Are there multiple users / sites??

If you don't already have it solved, I will offer my input.

Thanks.

0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Willeecoy,

The user states how many active entities s/he needs during each hour.  This code then comes up with a "best fit" series of time periods for the entitties to be active.

The user also specifies all the possible shift lengths and weighs them.  This way we can hopefully arrive at the time periods the user would like.

What types of entities there are is irrelivent.  It could be a bulldozer for instance.
0
 

Expert Comment

by:GOLLEM
Comment Utility
O.k. my turn to have a go at this problem...

let's analyze it shall we???

Basically what you want is an amount of timeslots which is as small as possible right??

Then the solution is simple:



Tables:

TTimeslotTable : table where the best possible solution is written to
TVarTable      : the amount of entities in the textboxes on screen (hour1 = record1)



Variables: (I+xxx = Integer, $+xxx = String and B+xxx = Boolean)

ITimeSlot#     : recordnumber for table TTimeslotTable
$TimeslotValue : value for field ( begintime - endtime )
IVar#          : recordnumber for TVarTable
IVarValue      : value for field (integer : number of entities left for hour)
IHours         : lenght in hours for timeslot
IStartHour     : begin time for timeslot
BPossible      : boolean



VBCode: (modify this code to meet your demands)

ITimeSlot# = 1

'loop through the different lengths for timeslots
   for IHours = 24 to 1

   'loop through the possible starting hours
      for IStartHour = 1 to (24 - (IHours - 1)

      'check if a timeslot is possible with that particular starting hour
         for IVar# = IStartHour to (IStartHour + IHours-1)
            'check if possible
            'table TVarTable : recornumber IVar# : value IVarValue
            'If IVarValue =0 then
            'BPossible = false
            'End If
         next IVar#

      'if timeslot is possible, then update, go to next record in TTimeslotTable
      'and make sure the loop is run again for the same starting hour
      if BPossible then
         for IVar# = IStartHour to (IStartHour + IHours-1)
            'subtract one from the IVarValue
            'table TVarTable : recordnumber IVar# : value IVarValue = IVarValue -1
         next IVar#
         'write to table
         ITimeslot = ITimeSlot + 1      
         IStartHour = IStartHour - 1
      end if
      'reset boolean
      BPossible = True

   next IStartHour

next IHours


This code will provide you with only the best possible solution.
If this is not what you want then I simply missed the point and I apologize...

It's a lot quicker than the code samples above though :)
 
0
 

Expert Comment

by:GOLLEM
Comment Utility
if you want to use variable shift lengths, remove the first loop and the  line 'ITimeSlot =1' and make a procedure out of the code...

example:
sub getpossible(IHours As Integer)

then the code for it would be:


ITimeSlot = 1
getpossible(3)
getpossible(7)
getpossible(24)
.....
.....


until all possible timeslot lengths have been explored

the table then gives the best possible solution for the weighed timeslot lengths....

Sorry I missed that bit :)




 
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Pseudo code would be more useful to me than VB code.  I have to actually convert the VB code back to pseudo before I can write the VBA.

Sorry it has taken so long, I was called interstate on contract.  I will attempt to convert the code tonight.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
I am having a terrible time trying to understand the VB and Pseudo posted here.
The only reason I have trouble writing this myself is that I can't come up with an algorithm to give me every possible combination of anything.

If I have a 24 hour period(and the period will be user defined and any length from 1-24) I need to generate a list of every possible time length to fill the overall time period.

I can't figure a way to have multiple lengths within one combination.
For instance:

2 x 1 hour shifts + 2 x 6 hour shifts + 1 x 10 hour shifts

My solution could only give me
24 x 1 hour shifts or
4 x 6 hour shifts or
2 x 12 hour shifts etc.

There must be a way to do this with loops.  Perhaps increment the number of each shift to produce.  I will try further to write the code for the algorithms I have but what I really need is a concept rather than an algorithm.  I can write the code if I have a concept that works.
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Quatro, did you check my comment? Any comments on it?
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Hi Angel,

I had a lot of trouble attempting to convert your VB code to VBA.  Firstly I get the compile error "User defined type not defined" at this line:
Friend Sub InitDistribution(Init As Distribution)

Then there are a lot of declarations and words not accepted by VBA.  I wish I had a copy of VB here but I don't.
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Yes, i'm sorry about that, but when i wrote it, I hadn't Access.
I'll try to change to access
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Adjusted points from 1030 to 1060
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
I have managed to write code that gives me many combinations but still not all combinations.  This is probably a basic standard concept that I don't yet have.  How do I get every combination of a sequence of numbers?

I can get:
111
121
123
232
333
for instance

I need to be able to get:
131
133
121
122
213
And all other possible combinations
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Adjusted points from 1060 to 1065
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
This is much easier, you develop a simple recursive procedure:
Private mcolCombs as new collection

Public Sub Combs( RootPart as string, CombPart as string, MaxLength as Long)

if CombPart = "" then exit sub

if Len(RootPart) = MaxLength then
  mcolCombs.Add RootPart
  exit sub
endif

dim lngLoop as Long
for lngLoop = 1 to len(CombPart)
  call Combs(RootPart & mid(CombPart,lngLoop,1) , CombPart, MaxLength )
next

End sub

Call Combs("","123",3)
and you will find all the combinations in the mcolCombs collection

(I'm still on the other part....)

0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
VBA 6 gives me this error

"Variable not defined" on this line:

mcolCombs.Add RootPart
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Ignore that last comment I missed the mcolcombs declaration.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Angel,

The problem with your code is that I have to specify a max length for the combination.  What I need is all combinations that equal a particular sumation.

ie.
111111
222
123
33
21111

etc.
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Hey, then your examples for last question were wrong ??? (smile)
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Not wrong but partial :-)
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Couldn't I use a variant and sum the combination and use that as a test instead of the "Len" function?
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Private mcolCombs as new collection

Public Function ValueOf(ByVal RP As String) As Long
  Dim lngValue As Long
  While Len(RP) > 0
    lngValue = lngValue + Val(Left(RP, 1))
    RP = Mid(RP, 2)
  Wend
  ValueOf = lngValue
End Function

Public Sub Combs(  RootPart as string, MaxValue as Long)

If MaxValue = 0 then exit sub


dim lngLoop as Long
lngLoop = MaxValue - ValueOf(RootPart)
if lngLoop = 0 then
  mcolCombs.Add RootPart
  Exit Sub
end if
if lngLoop > 9 then lngLoop = 9
while lngLoop > 0
   call Combs(RootPart & chr(Asc("0") + lngLoop), MaxValue)
   lngLoop = lngLoop-1
wend

End sub

Call Combs("","123",3)
and you will find all the combinations in the mcolCombs collection
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
Sorry, call Combs("",6) to find your list (always these copy&paste errors "*"+ç234"çP`=)
0
 
LVL 9

Expert Comment

by:BrianWren
Comment Utility
AngelIII,

While the code is active, (putting in a break-point), I can access the items of mcolCombs.  But once the code has run, I cannot.  How is this sub to be used?

Can you explain the role that 'RootPart,' and 'MaxValue' play?

Brian
0
 
LVL 142

Expert Comment

by:Guy Hengel [angelIII / a3]
Comment Utility
In fact, i defined the mcolCombs as NEW collection, but this may not be adequate for you. You have to define this collection at module level (or form level), as procedure is recursive (other way is much more complicated)

You may replace the mcolCombs by somethings else, ie put the value into a ListBox or TextBox or ListView or ...

RootPart represents the part of the string that has already been calculated, whereas MaxValue represents the sum of the digits that has to be reached.
CAll Combs ("",6) will call recursively
  CALL Combs ("6",6)
  CALL Combs ("5",6)
    CALL Combs ("51",6)
  CALL Combs ("4",6)
    CALL Combs ("42",6)
    CALL Combs ("41",6)
      CALL Combs ("411",6)
  CALL Combs ("3",6)
  ... aso



0
 
LVL 32

Expert Comment

by:bhess1
Comment Utility
I have some VB code here that will put out all possible combinations to a text file -

Sub TimeEnd(ByVal StartTime%, ByVal S$)
    Dim T%
    If StartTime <> 24 Then
        For T = 1 To 24 - StartTime
            TimeEnd StartTime + T, S & "," & T
        Next T
    Else
        Print #1, S
        If S1 <> Left(S, 4) Then
            Debug.Print S; ":"; Now
            S1 = Left(S, 4)
        End If
    End If
End Sub

To generate the text file, I used:

    Dim I%
    Open "C:\Hour" & I & ".TXT" For Output As #1
    For I = 1 to 24
        S = "" & I
        TimeEnd I, S
    Next I
    Close #1

I don't know if this will do what you need, but it should.
0
 
LVL 32

Expert Comment

by:bhess1
Comment Utility
Whoops - left some debug code in the function:

Sub TimeEnd(ByVal StartTime%, ByVal S$)
    Dim T%
    If StartTime <> 24 Then
        For T = 1 To 24 - StartTime
            TimeEnd StartTime + T, S & "," & T
        Next T
    Else
        Print #1, S
    End If
End Sub
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
DOne? Still in a Hurry? I read a note to ignore all the older comments, but this looks like context is needed.

If this is about some kind of shift up to 8 hrs, no more, then optimizations could be built in, but I wonder whether accomodation is intended for the 'graveyard shift" of 11 PM to 7 AM, and note no mention of the typical use of half-hours.

Programatically, some 'manual cheats' could be used to make a table, likely similar to the reference above on dumping to text file. (As instructed, I did not read all of this yet, for it may even be done by now)
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
I've read and got more confused. This sounds like a big project with several large modules, of which I am not quite sure which you want more help on. If not theoretical but practical. I often say cheat, find inside knowledge and apply it to make the whole thing less general and more doable. Maybe it is 'cause I did not study genetics, but this looks programmatically undoable in a complete sense without placing constraints on the user input. How big a number? Millions of screws? Billions? You referenced inventory. How about a trillion nuts at 3:00 and 2 trillion at 4:00 but only a billion Bolts for them for the whole day?  I looked above twice and still see no upper bound that contrains the user.  So, skipping anything on resolving best fit.

Except, best fit algorithms usually work best as largest first. Consider allocating Ram or disk. That goes smallest unit available for fit to reduce fragmentation. This situation looks more applicable to what some want in disk defragger, allocate that largest one first.  In other words, I think that the weighting situation may be easily simplified.

But the main question that I read may be doable, and that is finding the combinations. In access and and chipware, it is best to take the static details that you would have in an array and place them in a table for permanence. At first this sounds like some summation up to 24, a factorial - large.  Disk is best for large stuff (ie table, not array in ram, consider space issue). The ram/array is what you'd use, in a condensed form of the table, to do your computes like best fit or inclusion of weights to scale off results. The weights themselves also kept in a table.

The hours are confusing some. So why not change the problem to use of only #'s 1-24, the slots on the user screen, the first one is #1, not text/time 00:00. The user presentation can translate from the 1 to 00:00 if you like through another translation table of only 24 lines.

So, if you are with me, I am in camp with those using identifier '24' and less, down to '1'.  If you change the concept of from what time to what time, forget for now the end time, think of the duration or length.

Each hour can be from 1-24 long (or is 0 allowed? if so, is 24? Regardless either distinction is minor role).

The combos then are 24 for one, 24 for two, 24 for three, .... 24 for 24 !

That is 24 times 24 combos. Or what am I missing? A 24 x 24 array, or a similar table. Not too bad.

The bad I see is no limits on the amount of entities requested. With # bus stops the limit could have been street corners. With an inventory of screws, I dunno, could be thousands per hour quite easily, but they are then removed from inventory, needing replacement.

Anyway, I think by the time I'd done all this (slow) thying here, I could have manually entered those 576 odd variations into a table, do you still need them or their algorithm?

Or do you just want to know what to do with them once you have them?
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
I meant to say too that Table design is personal. For relational, non-keyed dB, a two column table is created. Rules:

Column 1 gets each number (1-24) exactly 24 times.

Column 2 gets each number (1-24) exactly 24 times.

Only one time only can a given value in column 2 be associated with a Value in column 1.

Actually, Access allows multiple column keys, so doing so will dump the errors possible. Add constraint of whole number <= 24 and pump values in until you get the magic # 24*24 (or whatever ) and know that you are done.
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
Maybe this can be thought of as a work assembly group that needs so many tools per hour?  Like 5 screwdrivers withdrawn from tool pool and 6 wrenches one hour, then 2 screwdrivers and 3 wrenches and four hammers the next hour? So they return three screwdrivers & wrenches to pool, allowing others to use them (or else they do not get the hammers, they get hammered!)?

WorkAreas tend to perform better on two hour intervals. Fits human needs for breaks.  But for assembly, it depends more on how quickly a change in plan (what is built) can take. Usually setup time is long but it can be short. For weights, again inside knowledge helps.

Still there's have to be a ceiling placed on how many hammers & screwdrivers that each can have. Helps to know the problem to make practical resolution doable (cheat - use tricks).

Say, do it in excel or other spreadsheet, it can generate #'s easily from 1-24 (by adding value 1 to value prior cell). SOunds like a 5 minute job, then cut/paste into access, trim any fat, and you've got .mdb you can VB to. Very quick static table creation.
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
OK you don't got eXcel, skip coding and if you cut/paste good here's a five minute table in access.

Define a table. Two columns. Text only (lest i scare that it is math). Column 1 is hours, two is tie. Save and View, enter 24 rows, value 1-24 (in sequence is better for eyes, but not needed_. In column two put all ones. Again, this is all text.

Close and make a copy called anything you like. I made one called Hours and the other duration.

Make 3rd table with query of first two, joined on "tie" (every record now joined to every record!). I called it result. Output the two remaining columns, and you get exactly 576 records. Open the new table, you don't like the titles? channge in seconds. One can be begin hou, the other the end hour. Or it can be the duration. Where 24 possible, the items to check are 576. If you like do quick search replace of 24 changed to 0 or 00:00 if you like.  But done in 5.

Make it a ten minute solution, double time to understand the concept and and correct my typos here. There may be a quicker prettier way than using all the 24 ones (twice), but implementation was so easy, why think?

Oh, now destroy the first two tables, they are now meaningless drivel. Now that you have the 'answer' to get the combinations, you can change format to one of only 24 rows if you like the square matrix appeal. But. You cannot finish the best fit for there are still no constraints on that human input which will drown you.

The 'best fit' remains unsolvable, as do the 'favorite fits' (presenting the top good ones to a human for a manual final selection), but you now have a table to use to find it by using 'combinations'.
0
 

Expert Comment

by:GOLLEM
Comment Utility
Quatro->

I don't have time to write the code for this solution, but I'm sure one
of the other experts can do this for you, or maybe you can do it yourself.




The way to solve this is by using a table with all possible timeslots.
The fields in this table should be booleans.
tablename: Timeslots

Your entities per hour are stored in the first record ofanother table.
tablename: Entities

the current combination as you are looping through the code (yopu remember the timeslots used
and go back one possibility once all combinations are used up
tablename: CurrentCombination

There should also be a table having three fields: one for the combination number,
one for the row number and one for the timeslot (you could also do this in an array)
tablename: Combinations


code:

step1 - Check all possible timeslots for the first record of the entities table.
        This is the first record in your timeslots table

step2 - create a loop that loops the first record of the timeslots table.
        if the boolean for a timeslot is true, then a variable is incremented,
        the second record is created for the entities table (by subtraction)
        and you jump into the next loop. Also the second record in the CurrentCombination
        table is written.
        When no possibilities are left this second record is destroyed again and you jump
        to the next timeslot in the first loop.

step3 - Check all possible timeslots for the second record of the entities table
        this is the second record in your timeslots table

step4 - the next loop, same as step 2 only now you loop the second record of the entities
        table and create the third record of the entities table


These loops can be dealt with by using a function that calls another instance of itself, when
another loop is needed (you can see the repetition)

an endpoint is reached when the next record put into the entities table is one where all
booleans are false. (then there is not even a one-hour timeslot left.)
If so then the function saves the CurrentCombination values into the Combinations table

To weigh the timeslots in a different way, the only thing you need to do is change the order
they are checked and used in the loop. This should not be so hard, just use the case statement.

       


This definitely is the solution, although maybe a bit late.....
Hope your boss isn't too angry at you :D

Regards,

      Michiel
0
 

Expert Comment

by:GOLLEM
Comment Utility
P.S. the amount of records in the CurrentRecord table is also the amount of loops used, the value indicates how far the loop has proceeded through the record in the timeslots table
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
IMHO, an elegant solution that is pretty, concise and applicable to every possible algorithm combo fo projects down the road - should be not attempted for completion where implementation time is of essence and there are 'expectations' from others. One keeps concept of 'the ultimate' in method of design, but gears initially for the precise situation at hand.

> It could be a bulldozer for instance

This raises situation quite dissimilar to other approaches. Bulldozers have not the high quantity of screws available nor are they expendable. While they are re-usable items like hammers and screwdrivers, their share-abiity is nowhere near the same. It is easy to hand a wrench from one employee to another nearby, or to pass from one workgroup to a common storage area where it can be picked up by another workgroup in another hour of the same 24 hour period. So one would think that answer to:

Believer> Do the hours for any given entity have to be contiguous?  

- would seem to be yes, that a bulldozer cannot be quickly moved in an hour to another constuction site in another town.
also, for:

AzraSound> minimum number of entities at that hour?  

I still wonder why so little concern here over maximum, but looking back I see no examples listed of less than one entity. So, is it a given that at least one unit will be active in each of the 24 hour periods? No idle hour ever? But obviously there won't be millions of bulldozers available to anyone. Still ceilings should be addressed.

If there is always 1 or more any given hour, THEN one will Always have at least one combination that ranges 24 hrs

00:00 - 24:00 (or 23:59 if preferred)

and at Least 24 of one hour periods. So one could state that as a given and not compute/reduce for it (cheat), change the table of 24 values input by subtracting one from each. Following This method can quickly reduce the compute time dramatically for the remainder of combos. For

Quatro> to have these entities on site.

If this is a case where (similar to) a single site that is large, can accomodate multiple bulldozers and cranes, it still won't have very many lest people get run over, but it impacts on

Believer> Do the hours for any given entity have to be contiguous?  

in that they no longer need contiguity. A bulldozer on one hill for two hours can easily be moved to a neaby hill for a three hour period. In such a case there are several other simplifications available.

Min # bulldozers required = Max number in any hour that day. Assign one the 1st 24 hr period, the 2nd the next 24 hr period (cases where # >=2) and continue, what falls out is the highest needed any hour is the highest needed that day, so that is how many bulldozers are needed that day.

This in inequitable computation for it does not address any load balancing. One entity run 1 hr, another 24 hrs.  But you have yet to indicate any need for an equitable balance for allocation.

A human could demand more than is possible.  A clerk entering totals of requests from all foremen at the site may find that all 12 want a bulldozer during a single hour but the company has only 6 bulldozers, and in a pinch can only borrow/lease one. So some of these won't get their requests honored.

Yet I see nothing in your task that addresses either testing for user request exceeding the entities available, or for any potential rescheduling, where an offer could programatically be made of a 'better fit' of allocating entities per hour. Only that if an entity is 'available' the period of availability lies between 1 and 24 hrs. Nothing on min/max for entities, which in my background was more critical in refining the scope of the problem.

Suppose, 12 foremen each as for 1 bulldozer only, for time 12:00 to 13:00. They each want only one hour that day. Only six bulldozers available. Each foreman responsible for work crews entire 24 hr period. From a request that is unworkable, one could respond that each foreman could have a bulldozer for 1/2 day, 12 hours, not merely one, but at least half of them would not get the specific hour requested.  No need for an 'all possible combinations' algorithmic approach, but again I see no indication of such a programatic request.

In short, back to my lead-in,, dealing less with the nebulous 'all possible', knowing more about the specific issues that are involved, can lead one towards a simplification scheme that can be put in place more timely, if time to implementation has any value. I now feel need to repeat -
mb1ake> What is it that you are trying to accomplish?
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
I concur with most of the previous

GOLLEM> The way to solve this is by using a table with all possible timeslots.
> The fields in this table should be booleans.
> tablename: Timeslots

With time I'd do it different, but I'd modify to ensure it had the two fields for timeslots, begin time and either end time or duration in hours. As stated above, the mere 576 records can be quickly generated. Depending on implementation scheme, one could either put the booleans in a range of rows in that table, or, clone the table for the other booleans.

What they can be is
- indicate whether you checked the slot
- indicate whether you used the slot
- indicate whether the slot is available, etc

If you take a more recursive approach, having a stable table that you copy from to a new table to reindicate all not checked yet, could be feasible.

I'd consider adding a numeric column or two to one of the tables. One could be initialized to the highest value possible. Another would contain the number of entities not yet addressed in the potential solution list (decrement). Once this column is reduced to zeroes, this pass of solution retrieval is complete. Meaning, 'some' of the total possible combinations, feasible or not - need NOT be checked. Using tables for the booleans and counters consumes to much time compared to you array suggestion. Bu if the tables are used to limit/reduce the 'check all possible', then it will also save time.

Which is quicker tradeoff, table/array is obviously dependent upon the nature of the instream data. If a human is manually entering 24 fields here and there, this instream will not be anywhere near a random list of all possible entries/combos. Know your environment. Or, "Know Your Limitations" (Dirty Harry).
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Thank you everybody for your input.  I wrote some every possible solution code of my own and manipulated it to the extent that it only requires 2 seconds to run.  That is I added my constraints.  I could not do this with Angels every combination code.  Especially considering Angel's code only allowed numbers from 1-9.  I need numbers from 0-infinity.

Along with this "every combination" code I used Xaphires boolean matrix and Billy21s weighting system.  I will make a request to experts exchange to split the points 70% to Xaphire and 30% to Billy21.

Thank you all again for your help.
0
 
LVL 7

Expert Comment

by:JimMorgan
Comment Utility
Quatro:

Could you post the code that you finally used?  I'm very interested in seeing what you were able to accomplish.

Jim
0
 
LVL 3

Expert Comment

by:darinw
Comment Utility
Community Support has reduced points from 1065 to 745
0
 
LVL 3

Expert Comment

by:darinw
Comment Utility
Hello all,

I have reduced the points on this question to 745. Quatro, you can accept one of the comments posted by one of the two Experts to award points. Remember, the Accept Comment as Answer button is in the header of the comment.

For the second Expert, you should post a new question in this topic area. The title should be 'For ExpertName -- 10317240' using the ExpertName of the unawarded Expert. The points should be 320 to make up the balance.

For your convenience, use this link for the new question:
http://www.experts-exchange.com/bin/NewQForm?ta=91

darinw
Customer Service
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
> I'm very interested in seeing what you were able to accomplish.

ditto.
Glad it worked out for you, especially under that time constraint.
0
 
LVL 1

Author Comment

by:Quatro
Comment Utility
Thanks for your help Xaphire Boolean Matrix is a great solution for this problem.

Quatro
0
 
LVL 7

Expert Comment

by:JimMorgan
Comment Utility
For those who don't understand what a Boolean Matrix is, it would be great to see the final code in order to better understand what to do to solve the problem.

Think about those who have not been a part of this thread.  It will cost them 75 question points to see the discussion but not the final answer.  I get very angry when I pay to see an PAQ and find that the solution is not really there.

Jim
0
 
LVL 24

Expert Comment

by:SunBow
Comment Utility
Hey, I remember now, boolean is light on/light off, 0/1 condition, and matrix could be math junk, but 2D is like spreadsheet in Lotus, so it is just rows/columns as:

0 1 0 1 0
1 0 1 0 1
1 1 0 0 1

Kinda simple. I can imagine how it can be useful in SOME part of problem. But not all of it, and I am one of those with little clue to the actual use of it in the solution used, so I'm in camp of 'incomplete solution' the way I read JimM remark.

I hadn't thought on that aspect for awhile, and I now know I don't have to pay here.  But supplemental remark, I have been in threads were a pair go off and do eMail to clear code solution.  My wish is that they'd make it more clear to new potential cotributors that they have taked it on the table, and that once they are done, they do clarify the solution used part, for my own main interest in EE is as a learning exercise, either to address a specific problem or to learn techniques and gain knowledge not available elsewhere.  So far I've had better luck with the latter.

So in support of request, I will really get unhappy if I run out of points searching, and finding no solutions, and end up having no points left to phrase it another way.

Not to fear, I have plenty of pts today (miser) for I also learn by commenting live on the cheap.

Feedback on the live interaction - I did have a rough idea of 2-3 ways you might be running booleans, and I do recall feeling there was a gap in the solution part at end (limited audience). Overall I thought it went very well as the parties exchanged their thoughts.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

In a multiple monitor setup, if you don't want to use AutoCenter to position your popup forms, you have a problem: where will they appear?  Sometimes you may have an additional problem: where the devil did they go?  If you last had a popup form open…
A simple tool to export all objects of two Access files as text and compare it with Meld, a free diff tool.
Learn how to number pages in an Access report over each group. Activate two pass printing by referencing the pages property: Add code to the Page Footers OnFormat event to capture the pages as there occur for each group. Use the pages property to …
Using Microsoft Access, learn some simple rules for how to construct tables in a relational database. Split up all multi-value fields into single values: Split up fields that belong to other things into separate tables: Make sure that all record…

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now