# Every possible combination code.

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.

Quatro
LVL 1
###### Who is Participating?

x

Commented:
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

Commented:
What is it that you are trying to accomplish?
0

Commented:
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

Commented:
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

Commented:
One hour is the minimum 24 hours  is the  maximum
0

Author Commented:
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

Author Commented:
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

Author Commented:
Adjusted points from 600 to 800
0

Author Commented:
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

Author Commented:
Adjusted points from 800 to 1000
0

Commented:
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

Author Commented:
That is the exact number of entities active at that hour.  There can be no more and no less.
0

Author Commented:
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

Billing EngineerCommented:
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

Author Commented:
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

Author Commented:
For this task I consider anywhere up to 5 mins to be an acceptable runtime.  If access cannot do this I will convert.
0

Commented:
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
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

Author Commented:
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

Author Commented:
Adjusted points from 1000 to 1030
0

Commented:
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
intCountComb = intCountComb + 1
comb(intCountComb) = colTemp(i)
write to result(x)
loop move comb(*) to combSave(*)
for j = i + 1 to colTemp.count
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

Commented:
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

Commented:
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

Commented:
(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

Commented:
how is that different from
Entity 1: 0:00 - 5:00???
0

Commented:
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

Commented:
I'm sorry, the numbers didn't align right. Hope it's still readable, though :-)
0

Commented:
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

Author Commented:
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

Author Commented:
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

Author Commented:
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

Commented:
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

Commented:
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

Commented:
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

Author Commented:
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

Author Commented:
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

Commented:
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:
03 xxx
02 xx-
02 -xx
02 -xx
01 x--
01 -x-
01 --x
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

Author Commented:
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

Billing EngineerCommented:
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
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
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

Dim intLoop As Integer

Visible = True
gblnInterrupt = True
DoEvents

For intLoop = MIN_HOUR + 1 To MAX_HOUR
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

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
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

Billing EngineerCommented:
* 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

Commented:
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

Commented:
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

Commented:
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

Author Commented:
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

Commented:
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

Commented:
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

Author Commented:
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

Author Commented:
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

Billing EngineerCommented:
Quatro, did you check my comment? Any comments on it?
0

Author Commented:
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

Billing EngineerCommented:
Yes, i'm sorry about that, but when i wrote it, I hadn't Access.
I'll try to change to access
0

Author Commented:
Adjusted points from 1030 to 1060
0

Author Commented:
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

Author Commented:
Adjusted points from 1060 to 1065
0

Billing EngineerCommented:
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
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

Author Commented:
VBA 6 gives me this error

"Variable not defined" on this line:

0

Author Commented:
Ignore that last comment I missed the mcolcombs declaration.
0

Author Commented:
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

Billing EngineerCommented:
Hey, then your examples for last question were wrong ??? (smile)
0

Author Commented:
Not wrong but partial :-)
0

Author Commented:
Couldn't I use a variant and sum the combination and use that as a test instead of the "Len" function?
0

Billing EngineerCommented:
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
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

Billing EngineerCommented:
Sorry, call Combs("",6) to find your list (always these copy&paste errors "*"+Ã§234"Ã§P`=)
0

Commented:
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

Billing EngineerCommented:
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

Senior DBACommented:
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

Senior DBACommented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Author Commented:
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

Commented:
Quatro:

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

Jim
0

Commented:
Community Support has reduced points from 1065 to 745
0

Commented:
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.

http://www.experts-exchange.com/bin/NewQForm?ta=91

darinw
Customer Service
0

Commented:
> 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

Author Commented:
Thanks for your help Xaphire Boolean Matrix is a great solution for this problem.

Quatro
0

Commented:
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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.