algorithm help

I'm having trouble understanding what you are attempting.  I think that maybe my problem is that your input and output sample has problems.  For instance, in your input you have 20-1-763, but in your output list it says 20-7-763.  Is that supposed to be a 7?  Another problem that I think is a problem is that you list out only 4 records that have the first and third numbers the same; however, I see 6 records that should be a part of that set (5 of which are unique).  Why do you say there are only 4 records that are the same?  You see how your example might be confusing?  Please give another example that shows the input data and also shows the output data.  Be careful not to have any errors in your example because that is what I use to try to figure out what you are trying to do (black box approach).

What I am hearing you say is the following.

Find a record that has a unique third number and call it RecA.
Find a group of records that have both the first and third numbers the same and call that SetA.
For each number in SetA subtract its first column number from the first column number in record RecA.
If that result is between -6 and 6 (inclusively) then output that number (or put a 1 in the forth column?)

If this is what you want then there is one major issue that you must assure me will always occur?  In order to do the above you can only have 1 record (and only 1 record) in your multidimensional array that has a unique third number.  Also, you can only have 1 set (and only 1 set) that has both the third and forth numbers the same.  For instance, you cannot have the following input list.

1-2-3
4-5-6
7-1-9
7-2-9
7-3-9

Because you have two records that have unique third numbers (records 1 and 2 both have unique third numbers).

You also cannot have the following input list.

1-2-3
4-1-6
4-2-6
4-3-6
7-1-9
7-2-9
7-3-9

Even though you have only one record with a unique third number (record 1 is the only record with a unique third number), you still have a problem with this input data because you have two sets of numbers that have the same first and third numbers (records 2, 3, and 4 in one set and records 5, 6, and 7 in the other set).

The way you worded your question and the example you gave does not make it clear how we are to attempt to handle these types of cases.  So, I can only assume that you are assuring us that such cases can never happen.  If that is true then I can solve this problem (provided you give me a better example).

Actually, I suppose that since you have the limtation that the result of the subtraction of the first numbers must be between -6 and 6 (inclusively) you probably could have a set that looks like this.

1-2-3
4-1-6
4-2-6
4-3-6
7-1-9
7-2-9
7-3-9

But I still need to be assured that there is always only 1 record that has a unique third digit.  Can you assure me that this is the case?

Or maybe you want me to go ahead and find every combination of records that have unique third digits and interact them with every set of numbers that have common first and third numbers.  That seems possible as well, but I don't want to solve this much harder problem if the question you are asking is not that complex.  I'll need another example to tell.

Oh, and one more quick question.  Do you want me to ignore duplicates records altogether?  For instance, you have in your original example two occurances of 19-3-721.  Do you want to just treat that as one occurance?

If your answer is yes, then how should be treat the following example.

1-2-3
4-5-6
4-5-6
7-1-9
7-2-9
7-3-9

Should I start by removing the repeat of 4-5-6 giving this array.

1-2-3
4-5-6
7-1-9
7-2-9
7-3-9

And then search through for the stuff we are looking for (unique 3rd number and sets where the first and thrid numbers are the same)?

Another way to interpret what the alogirthm is to find the first unique record and use it in combination with the first set found.  Then, repeat the process with the next unique record and set, repeating until no more unique records are found.  We should be able to tell what records have been processed already since the fourth column will have a value in it.

lynnton, your "algorithms" are getting quite complex.  I wonder if you should be moving your data to some kind of database system where this kind of information can be queried for using SQL statements.  You are looking for unique values and creating relationships between records...both things that database systems do well.

I realize you have put quite a bit of work in to get to this stage in your app and probably don't want to start over.  What you are asking for is definitely possible to do using arrays but later down the line it is going to be a nightmare trying to change and modify this code.  Someone else (even possibly yourself) looking at these algorithms in the future is going to have a really hard time understanding what is going on.  =)

One possibility is to create a class to hold the data instead.  Then you can add these instances to a collection using a key for fast retrieval.  It is even possible to make one class point to another (think Linked Lists) to represent relationships.

Ok, lets start with this code.  I did it quickly so it probably is not exactly what you want, but it might give us some idea of what we need to do to answer your question.  I simply tossed items from your list into multiple collections (actually I just put the index into a collection though if I made it a class I could have tossed the structure into the collction).  Each collection represents unique sets of records.  All sets that contain only one record is considered a test set to test against the other sets that contain more then one item.  Just take a peak and then tell me what I did wrong so I can understand your problem better.  Here you go:

http://www.enlade.com/Samples/MiscTest1-a.zip

Enjoy.

Please remember that we can rebuild the output array as an array from the outSet collection.  So, it doesn't really matter that I am using collections.  For instance, instead of outputing the information to the lstOutput listbox you could do the following instead.

Replace this code in frmMiscTest:

  For i = 1 To OutSet.Count
    lstOutput.AddItem GlobInData(OutSet.Item(i)).c1 & "-" & GlobInData(OutSet.Item(i)).c2 & "-" & GlobInData(OutSet.Item(i)).c3
  Next i

with this code:

  For i = 1 To nGlobInData
    GlobInData(i).c4 = 0
  Next i
 
  For i = 1 To OutSet.Count
    GlobInData(OutSet.Item(i)).c4 = 1
  Next i
 
  For i = 1 To nGlobInData
    lstOutput.AddItem GlobInData(i).c1 & "-" & GlobInData(i).c2 & "-" & GlobInData(i).c3 & "-" & GlobInData(i).c4
  Next i

There is probably a more elegant solution to this problem and there are still a lot of unanswered questions that will effect this code a bit more, but it seems to work (if I understand your problem correctly).

From your question you seemed to indicate that you also wanted to include all of the unique records (sets with one record in them) in your output as well (or rather mark them with a 1 in the forth column as well).  This is not hard to do, you simple add all of those sets that only have one record to the outSet collection prior to exiting from the BreakUp function.  I can make that change very easilly if that is what you want to have happen.  Just tell me if you want me to do that.

Also, notice that my input records contain two records that are identical (1-2-3 occurs 2 times exactly).  I am not sure how you want me to handle that case.  I mean, am I to consider that 1-2-3 is a single unique item that needs to be tested against all of the other sets that have more then 1 record?  Or do I treat it as a special case that all true unique records need to be tested against it?  I don't know if I'm making myself clear, but this is a strange instance of input data that needs to be considered.

Basically you have two major groupings.  You have all the records that are unique and you have all the groups of records that are similar.  My question is simply how am I to interpret sets of records that are all exactly the same (like in my example with 1-2-3).  Do they fall into the group of records that are unique or do they fall into the group of records that are similar even though they are treated as a single record in the end?

Mind you there is another open question when such records end up as a part of a legitimate group of similar records.  For instance, in your example above you have two occurrences of 19-3-721; however, since you have other similar records then just those two then the entire group of records belong to a set of similar records (not to be treated as a unique record).  Still, on your output list you only added a 1 next to the first of these two records.  That seems strange to me unless you were simply trying to say that only one occurrence of each unique record should be outputted to the screen and that was just your way of skipping duplicates.

In any case, these two areas of confusion need to be better defined.  The changes to the code are simple enough, but since I don't quite understand your problem I cannot make that choice.

Let me give you some examples of the problem I am trying to describe above.  I talked above about how we might handle duplicates in the input data.  There are two problems that occur due to duplicates that I tried to explain above.  Let’s look at an example of the first problem of duplicates.  This is when all you have is duplicates and there are no other similar records to the duplicates.  Here is an example input.

1-2-3
55-1-2
55-1-2
50-1-8
50-2-8
50-3-8

There are two possible ways to interpret this input data.  I could treat the duplicates of 55-1-2 as a unique item and thus I would get the following output.

1-2-3-1
55-1-2-1
55-1-2-0
50-1-8-1
50-2-8-1
50-3-8-1

Or I could treat 55-1-2 as a set of similar records (not as a unique item) and thus I would get the following output.

1-2-3-1
55-1-2-0
55-1-2-0
50-1-8-0
50-2-8-0
50-3-8-0

Now let’s look at the second problem of duplicates.  The second problem occurs in the above example as well.  It is simply a question of whether you want to put a 0 in the forth column for all of the duplicates except for the first one (which gets a 1).  To illustrate this further lets look at how duplicates seem to be handled within a greater set of similar records.  For instance,

52-2-3
55-1-2
55-1-2
55-2-2
50-1-8
50-2-8
50-3-8

In this case I still have a duplicate 55-1-2; however, I also now have a similar record that is not a duplicate (that is, 55-2-2).  From your example you seem to be saying that the output from the above should be:

52-2-3-1
55-1-2-1
55-1-2-0
55-2-2-1
50-1-8-1
50-2-8-1
50-3-8-1

This seemed a little strange to me, but maybe you are doing this simply to be able to walk through the list and ignore duplicates without having to test for them as you go along.  That is fine, but I need to know if that is really what you wanted.

Here, I have changed the input data in the code to further illustrate this problem.  Also, I added the unique (single item set) records to the outSet so that they end up with 1's next to them as well (in the forth field).  Oh, and I forgot to mention that I used a type structure instead of multidimensional array.  That is not a big deal since you could just as easily use multidimensional arrays (or classes even--which I might consider doing if this was my problem).  Its just that I don't normally use multidimensional arrays unless it is required by the nature of the problem so my mind just created a structure.  It just dawned on me that you wanted multidimensional arrays, but it doesn't really make a difference.  The algorithm is the same either way.  Anyway, here is the link to the final code (until you ask for something more).  I could change it to use multidimensional arrays if you want.  It's not a big deal.

http://www.enlade.com/Samples/MiscTest1-b.zip

Enjoy.

I rewrote the code so that it used a multidemension array.  Let me test it and then post a new link.  Here is the main function for anyone that doesn't want to download the full source.

Public Sub BreakUp(ByRef iData() As Long, ByVal niData As Long)
  Dim i As Long
  Dim j As Long
  Dim k As Long
 
  Dim bFound As Boolean
  Dim bValid As Boolean
  Dim tempVal As Double

  bFound = True
  j = 1
  While (bFound)
   
    bFound = False
    While (j <= niData) And Not (bFound)
      If (iData(j, 4) = 0) Then
        bFound = True
      Else
        j = j + 1
      End If
    Wend
   
    If (bFound) Then
      iData(j, 4) = 2
     
      For i = j + 1 To niData
        If (iData(i, 1) = iData(j, 1)) And (iData(i, 3) = iData(j, 3)) Then
          If (iData(i, 2) = iData(j, 2)) Then
            iData(i, 4) = 4   'duplicate
          Else
            iData(i, 4) = -j   'similar

            iData(j, 4) = 3
          End If
        End If
      Next i
    End If
  Wend
 
  For i = 1 To niData
    If (iData(i, 4) = 2) Then
      For j = 1 To niData
        If (iData(j, 4) = 3) Then
          tempVal = iData(i, 1) - iData(j, 1)
          If (tempVal >= -6) And (tempVal <= 6) Then
            For k = 1 To niData
              If (iData(k, 4) = -j) Then
                iData(k, 4) = 1
              End If
            Next k
           
            iData(j, 4) = 1
          End If
        End If
      Next j
     
      iData(i, 4) = 1
    End If
  Next i
       
  For i = 1 To niData
    If Not ((iData(i, 4) = 0) Or (iData(i, 4) = 1)) Then
      iData(i, 4) = 0
    End If
  Next i
 
End Sub

Here is the link to the code using an array without collections.  There is probably a better way to use collections to achieve the same results, but I don't want to think too hard.  Here is the code you wanted (if I understood your question properly).

http://www.enlade.com/Samples/MiscTest2-a.zip

Mind you there are ways to speed up this function.  For instance, instead of only processing when we find a unique record we could also process when we find a similar root record.  That would eliminate the number of items that we need to work on.  Better yet, if we go back to using collections then we reduce the size of the sets that we are working on.  Still, unless you are processing massive amounts of data then I don't think we should worry about the BigO of this algorithm.

The original array had 100,000 items in it.  If you have multiple nested loops then yes, speed improvements may be noticeable.  =)

yep, I didn't notice that array declaration.  I think that using the collections might be faster though even that code could be optimized a bit more.  I'll wait to see if he needs it optimized.  Hopefully he was just declaring a static array size that he thought would be large enouth (though I don't think you can declare a static array of that size in VB so I am probably just being optimistic).

My system let me declare the array that big and ran with no problems.

Enlade,

My deepest apology for not replying back quickly.

I was dead tired and fallen a sleep.

I'll post a reply after reading up.

Thanks.

Enlade,

Sorry for not explaining everything clearly and for those bad samples.

here's a better understanding.

the data we are creating relations are called schedules.  Schedules are 9 hours long (work schedules for people)

first column is time (00:00, 00:30, 01:00,....23:30)  so values are 1 upto 48, one every half-hour (i've used numbers to represent them)

second column is day (monday,tuesday,wednesday...sunday)  so values are 1 upto 7 (i've used numbers to represent them)

third column is the ID of the actual schedule (i have a database that contains an ID and schedules)

fourth is the algorithm that we will need to create relations/group them together.

so from binaryIDArr we can tell what time and day a particular schedule will start.

________________________________________________________________________________

the binardyIDArr contains pieces of schedules (one schedule) per record.

we need to group/relate them together to create a shift.

a shift is 5 working days (this means we need to relate/group 5 records)

constrains...

now I'm looking for the best approach to mix and match the whole thing. because after we run the algorithm there will be left overs (peices that has no relation to other schedules).

I've thought of starting with those unique then matching it up with four similar schedules (this is what we call split schedules where in 1 shift will have two different schedules). This is what we are doing presently.
i.e.
raw data
19-1-1221-1   (19 is 9:00) (1 is monday)  (1221 is the actual schedule)
19-2-1221-1
23-5-1428-1
23-6-1428-1
23-7-1428-1

on monday and tuesday you come-in at 9:00
but on friday, saturday,and sunday you comin at 11:00

now this is where between 6 and -6 comes in. we should follow this rules since we need the time for that person to rest :-)

then later on we can search for two records that have similar first and third column (actual schedules) but different in second column (day) and then group/relate with three records similar on first and third column but different in second column.

-the fourth column is an auto number to indicate how many we already created.

hope this clears up everything.

Enlade,

BinaryIDArr was declaired 100,000, but i redim this at the end to get the actual rows.

it's only 1500++ presently, not sure how it large it will become. but one thing is for sure, 100,000 is way to large.

i know it's wrong way ofr reDiming, Please don't comment on this part :-)

Idle_Mind,

Sir, you are correct, placing this in a database will be a snap, same goes for the algorithm.

Sadly, it's on access database and it's really slow, a person here at EE showed me "we can place ur present database raw
 
data and put it in an array and do what ever we like and place it back after wards" which turns out to be the fastest i've seen.

hope you could give guidance on this one too (algorithm).

Thanks.

Well, if it is only 1500 then using the my second approuch (multiD array) should work fine.  Still, if you want to optimize it you can use collections like in my first approuch.  The collections are simply treated as subsets that you organize the records into.  You don't actually put the record into the set, but rather just the index of the record that exists in your original multiD array.  Placing items into the appropriate subsets will take one pass through the list and multiple passes through some of the subsets to prevent duplicates (though it is hopeful that the subsets are small and thus faster then traversing the superset (full array of input data)).

The code I wrote wasn't really optimized.  At least, I think that there could be modifications to that code to speed it up.  Even in the second method that I used I think there are some things that you can do to speed things up.  I suggest that you try out the second example first and see if it runs fast enough for your needs.  If not then we can work on optimizing.

Keep in mind that I was assuming that your input array was in the form (1 to 100000, 1 to 4).  If you already have an input array in the form (0 to 3, 0 to 100000) then you will need to modify that function I created (or modify your array format of your input data).

I think that I still need you to give me some input data and then show me exactly what you want output given that input data.  This, along with your explanation above, will help me figure out what you want.  Just make up a few example like I did in my messages above, but be really careful not to make any mistakes in what you want it to output.  Thanks.

Enlade,

Which part are you having doubts with?

Thanks.

Here, lest start with this.  Let this be your entire input array.  What do you want to output given this input array.

27-1-1111
2-1-1234
19-1-1221
19-2-1221
23-5-1428
23-6-1428
23-7-1428
1-1-1000
1-2-1000

Do you want to output this:

27-1-1111-1
2-1-1234-1
19-1-1221-0
19-2-1221-0
23-5-1428-1
23-6-1428-1
23-7-1428-1
1-1-1000-1
1-2-1000-1

Enlade,

raw:
45-4-3  <---unique
48-1-2  <--duplicate
48-1-2  <--duplicate
48-7-8
48-2-8
48-3-8

output:
45-4-3-1  <---remember we need the difference from the first column of the four records to be between 6 and -6 (48-45=3)
48-1-2-1  <-----tag the first duplicate found.
48-1-2   <-----leave the others
48-7-8-1 <--first and third columns on four records are the same but the second column are unique to each other.
48-2-8-1
48-3-8-1

look at the second column that has a 1 on the fourth column, it's unique.
4
1
7
2
3   <-------we need the second column to be also unique from one another for the group.

remember second column is for day ( monday, tuesday, wednesday, ...sunday) we can't have one person come-in on same day :-)


then loop (search for another unique record)

Enlade,

Please disregard the sample i've posted earlier...my apology


raw:
45-4-3  <---unique
48-1-8  <--duplicate
48-1-8  <--duplicate
48-7-8
48-2-8
48-3-8

output:
45-4-3-1  <---remember we need the difference from the first column of the four records to be between 6 and -6 (48-45=3)
48-1-8-1  <-----tag the first duplicate found.
48-1-8   <-----leave the others
48-7-8-1 <--first and third columns on four records are the same but the second column are unique to each other.
48-2-8-1
48-3-8-1

look at the second column that has a 1 on the fourth column, it's unique.
4
1
7
2
3   <-------we need the second column to be also unique from one another for the group.

remember second column is for day ( monday, tuesday, wednesday, ...sunday) we can't have one person come-in on same day :-)


then loop (search for another unique record)

Ok, then the code I wrote seems to do that.  Take a peak at it and see if it does what you want.

Is it the case that you want to list out every combination?  Maybe that is what I'm confused about.  For instance, if you have the following input data.

27-1-1111
2-1-1234
19-1-1221
19-2-1221
23-5-1428
23-6-1428
23-7-1428
1-1-1000
1-2-1000

Do you want two output because there are two unique records (records 1 and 2)?  Such that the output would be.

27-1-1111-1
2-1-1234-0
19-1-1221-0
19-2-1221-0
23-5-1428-1
23-6-1428-1
23-7-1428-1
1-1-1000-0
1-2-1000-0

and also,

27-1-1111-0
2-1-1234-1
19-1-1221-0
19-2-1221-0
23-5-1428-0
23-6-1428-0
23-7-1428-0
1-1-1000-1
1-2-1000-1

So you get two output lists?  Is that what you want?

What about the two records that have no related unique record (that is, what about 19-1-1221 and 19-2-1221)?  What do you want to do with those?

Enlade,

wanted to know if you saw this post...


Enlade,

Sorry for not explaining everything clearly and for those bad samples.

here's a better understanding.

the data we are creating relations are called schedules.  Schedules are 9 hours long (work schedules for people)

first column is time (00:00, 00:30, 01:00,....23:30)  so values are 1 upto 48, one every half-hour (i've used numbers to represent them)

second column is day (monday,tuesday,wednesday...sunday)  so values are 1 upto 7 (i've used numbers to represent them)

third column is the ID of the actual schedule (i have a database that contains an ID and schedules)

fourth is the algorithm that we will need to create relations/group them together.

so from binaryIDArr we can tell what time and day a particular schedule will start.

________________________________________________________________________________

the binardyIDArr contains pieces of schedules (one schedule) per record.

we need to group/relate them together to create a shift.

a shift is 5 working days (this means we need to relate/group 5 records)

constrains...

now I'm looking for the best approach to mix and match the whole thing. because after we run the algorithm there will be left overs (peices that has no relation to other schedules).

I've thought of starting with those unique then matching it up with four similar schedules (this is what we call split schedules where in 1 shift will have two different schedules). This is what we are doing presently.
i.e.
raw data
19-1-1221-1   (19 is 9:00) (1 is monday)  (1221 is the actual schedule)
19-2-1221-1
23-5-1428-1
23-6-1428-1
23-7-1428-1

on monday and tuesday you come-in at 9:00
but on friday, saturday,and sunday you comin at 11:00

now this is where between 6 and -6 comes in. we should follow this rules since we need the time for that person to rest :-)

then later on we can search for two records that have similar first and third column (actual schedules) but different in second column (day) and then group/relate with three records similar on first and third column but different in second column.

-the fourth column is an auto number to indicate how many we already created.

hope this clears up everything.

Enlade,

I think i'm really a guy who loves to make mistakes. sorry for this.

i.e.
raw data
19-1-1221-1   (19 is 9:00) (1 is monday)  (1221 is the actual schedule)
23-2-1221-1    <--------------------------the first column should be 23 (i've change it from 19 to 23)*************
23-5-1428-1
23-6-1428-1
23-7-1428-1

Enlade,

Gees, here I go again, i'm so pist at my self now.

i.e.
raw data
19-1-1221-1   (19 is 9:00) (1 is monday)  (1221 is the actual schedule)
23-2-1428-1    <--------------------------the first column should be 23 (i've change it from 19 to 23)*************
23-5-1428-1          *********also change 1221 to 1428
23-6-1428-1
23-7-1428-1

Yes, but that just helps me understand some of the overall intent of your problem.  You seemed to be implying that you already have a solution but you are just having trouble implementing that solution in code.  I'm simply trusting that your solution is a good one and then trying to code your solution (just easier for me).  It is easier for me to code your solution by looking at a few examples of input/output that you could give me.  In any case, even if I was to attempt to come up with a different solution I would still like to get some idea of how your data is input into the system and how the system is to respond (output) to that input data.

I understand how the data is getting into your system (that is the format of it).  I just want to get a better understand of exactly what you want the system to spit back out at you after it looks at your input data.  The code I wrote already will basically spit back out exactly what you seem to be discribing in your solution, but in looking at your explaination above it seems like that might not be what you are looking for.

Just need to see some output or rather to see what you would like to get as output given some predefined input data.

Enlade,

Gotcha, hold on let me drink coffee, i'm so angry at myself ...

Thanks.

Lets start over.  Just give me the output for the following two input samples:

Input Sample 1
27-1-1111
2-1-1234
19-1-1221
19-2-1221
23-5-1428
23-6-1428
23-7-1428
1-1-1000
1-2-1000

Input Sample 2
24-1-1111
16-1-1234
19-1-1221
19-2-1221
23-5-1428
23-6-1428
23-7-1428
12-1-1000
12-2-1000

Just give me the output that you want the function I am writing to give you for both of these samples.

Enlade,

Input Sample 1  ----- no change
27-1-1111
2-1-1234
19-1-1221
19-2-1221
23-5-1428
23-6-1428
23-7-1428
1-1-1000
1-2-1000

process algorithm...
27-1-1111 <----------------------this is the first unique record we found (third column is unique)
now search for 4 records
no results found

23-5-1428  <----------------this could have been a good candidate since 23-27=4  and 4 is between 6 and -6
23-6-1428     <-------------------------problem is it's only 3 records ( we need four)
23-7-1428

Ok, I'm strarting to understand.  Let me work out another input sample that will help me understand....hold up a bit..

Ok, lets start with a simple one.  What would be the output for this sample input:

Input Sample 1
24-1-1111
16-1-1234
19-1-1221
19-2-1221
19-3-1221
19-4-1221
23-1-1428
23-2-1428
23-3-1428
23-4-1428

Notice that I made the two unique records (records 1 and 2) be capable of validating both similar sets.  So I'm looking for some understand of how you choose to select which similar set for which unique record.  I'm also looking to see if you end up with two output lists rather then just one.

What I am expecting is two lists that result for that sample input.  They might look like this:

Output List 1:
24-1-1111-1
16-1-1234-0
19-1-1221-0
19-2-1221-0
19-3-1221-0
19-4-1221-0
23-1-1428-1
23-2-1428-1
23-3-1428-1
23-4-1428-1

Output List 2:
24-1-1111-0
16-1-1234-1
19-1-1221-1
19-2-1221-1
19-3-1221-1
19-4-1221-1
23-1-1428-0
23-2-1428-0
23-3-1428-0
23-4-1428-0

Though you could have decided to associate the Unique records inversely to the similar record sets.  I am assuming it is arbitrary.  You simply want to find the first combination of 5 records you can find.  Is that correct?

Or maybe you use that 4th column as a grouping flag so that you end up with this single list as an output:

Output List:
24-1-1111-1
16-1-1234-2
19-1-1221-2
19-2-1221-2
19-3-1221-2
19-4-1221-2
23-1-1428-1
23-2-1428-1
23-3-1428-1
23-4-1428-1

Is that what you want?

Though this list would also be valid:

Output List:
24-1-1111-2
16-1-1234-1
19-1-1221-2
19-2-1221-2
19-3-1221-2
19-4-1221-2
23-1-1428-1
23-2-1428-1
23-3-1428-1
23-4-1428-1

I think I covered all the possiblities that I can think of.  I'll just wait for you to tell me what the real output should be.

Of course this would be valid too.

Output List:
24-1-1111-1
16-1-1234-2
19-1-1221-1
19-2-1221-1
19-3-1221-1
19-4-1221-1
23-1-1428-2
23-2-1428-2
23-3-1428-2
23-4-1428-2

Just a bunch of ways of saying the same thing.

You know it bothers me that we are looking for records that are between -6 and 6 (or rather within 3 hours of each other).  It would seem that you would want to make sure that the unique record was not within 3 hours of any of the records in the similar set that you are associating it with (though I think you said it should be 6 hours difference which means it should be -12 to 12).  Are you sure we are looking for records that are within 3 (or 6) hours?  For example, if you look at my above example I am attempting to assocate 24-1-111 with 19-1-1221, but doesn't that mean that the individual would be overlaping his schedule start time?

In fact, if a schedule corrisponds to 9 hours then should I be looking for related schedules that are greater then 15 hours difference (giving 6 hours of rest between schedules)?

Gotta get some lunch....be back later...

Enlade,

Input Sample 1 - no change - since the second column has a problem
24-1-1111  <-----------the second value is 1
16-1-1234
19-1-1221
19-2-1221
19-3-1221
19-4-1221
23-1-1428 <---------------this could have been a good match but the second value is not unique
23-2-1428
23-3-1428
23-4-1428


I've change the Input sample 1 to create a relation

24-5-1111
16-7-1234
19-1-1221
19-2-1221
19-3-1221
19-4-1221
23-1-1428
23-2-1428
23-3-1428
23-4-1428

output:
24-5-1111-1
16-7-1234 <----this wasn't touch since 23-16 =7   7 is not between 6 and -6
19-1-1221-1
19-2-1221-1
19-3-1221-1
19-4-1221-1
23-1-1428
23-2-1428
23-3-1428
23-4-1428

process...
find the first unique value for the whole third column
24-5-1111 <-------------found one


now the first one 24-6-1111 <----we will call it as Uni-a
search for records that has same values for first and third column but different from one another on the second field
19-1-1221  <-----------found two SETs
19-2-1221  <-----------second column are 1,2,3,4
19-3-1221  
19-4-1221
23-1-1428  <-----------second column are 1,2,3,4
23-2-1428
23-3-1428
23-4-1428

subtract the first column of the set to Uni-a (19-24=5)  5 is between 6 and -6
is the second column on the set different from what Uni-a has?  1,2,3,4     Uni-A is 6   answer is yes

now everything is good, populate the auto number on the fourth column. start at 1
24-5-1111-1
23-1-1428-1
23-2-1428-1
23-3-1428-1
23-4-1428-1

repeating the process....


now on to the second Unique
16-7-1234 <--------------we will call this uni-b

search for records that has same values for first and third column but different from one another on the second field
23-1-1428 <----------found only one set
23-2-1428
23-3-1428
23-4-1428

subtract the first column of the set to Uni-b (23-16=7)  7 is not between 6 and -6 ************************
drop everything.
search for another set of records.....until we find one or until there are no more.

Ok...sorry about that....lunch turned into a meeting that ran late.

Let me give you one last sample input and then I'll go code something.  What would you want the program to output if your input sample looked like this:

Input Sample:
24-5-1111
18-5-1234
19-1-1221
19-2-1221
19-3-1221
19-4-1221
23-1-1428
23-2-1428
23-3-1428
23-4-1428

That should do it for me.

Ok, lets start working on this code now.  I am now createing collections of collections and my output is actually a collection of collections of indexes into the original multiD array that contains the input data.  I am thinking that keeping them in collections of collections is probably better then adding a grouping flag to the forth element of your multiD array.  However, if you find that collections of collections is not helpful to your application then it is easy enough to reconstruct the multiD array with the extra grouping flag in as the forth element.  In any case, take a look at this code and see if it does something close to what you want.

http://www.enlade.com/Samples/MiscTest3-a.zip

Oh, and you probably would also like to know which records were not placed at all.  I can add all unplaced records to a seperate global collection if you want that information to be accessable outside of the function.  But lets make sure I'm on the right path first.  How does that code look to you?

Here, I added the output of all the records that were not placed as well.  And I also output the index at the beginning of each item in the listbox's so that it makes it easy to see that everything is being processed.  Lets work from this code.

http://www.enlade.com/Samples/MiscTest3-b.zip

I also moved the input data out of the code and into a text file called "Data.txt".  So you can now simply modify "Data.txt" to test it against other intput data samples.  I posted this change under the same filename so if you don't see it then try downloading it from the link above again.  Give it a try and tell me if there is anything else that I need to consider.  Be sure to test for duplicate items.  Make sure the code handles duplicates properly.  Remember there are three special cases involving duplicates.

1.  Everything in a possible set is a duplicate which means that all but one item is ignored (giving you a set with one item.
2.  Some items in a set are duplicates but not all.  This gives you a set that has at least 2 items in it, but no duplicates.  This results in two cases that we need to consider.
  a.  The case when duplicates are removed and there are now 4 items that can be matched with our single item set.
  b.  The case when there was 4 items but when duplicates are removed there are no longer 4 items (there are 3 or 2 items left).

The way my code handles each case is as follows.

1.  Duplicates are removed and if that leaves us with 1 item in the set then it is considered a unique item that can then be matched with another set of 4 items.
2a.  The resulting set now has 4 items so it is considered a 4 item set that can now be matched with a 1 item set.
2b.  The resulting set now has less then 4 items and therefore it is ignored and put into the NotPlaced set.

If that is what you wanted then the code should be doing that for you.

One more thing that you might want to consider.  If you look at my sample data in Data.txt you will see:

15
25,5,1111,0
18,5,1234,0
19,1,1221,0
19,2,1221,0
19,3,1221,0
23,1,1428,0
23,2,1428,0
23,3,1428,0
23,4,1428,0
19,4,1221,0
1,1,1010,0
1,2,1010,0
2,1,1110,0
2,1,1110,0
2,2,1110,0

When you run the code it will match record 1 with records 3, 4, 5, and 10.  And it will match record 2 with records 6, 7, 8, and 9.  However, if you chanced record 2 so that it was "16,5,1234,0" and ran the program you would get a less then optimal result.  In this case it would only match record 1 with records 3, 4, 5, and 10.  Optimally I think it would have been better to match record 2 with 3, 4, 5, and 10 so that we can also match record 1 with records 6, 7, 8, and 9.  The problem is that it matches records in the order that they traverse through the list.

One possible solution (though it will most likely slow down your runtime) is to match each single item set with a 4 item set that maximizes the difference in start times.  If we always try to match the highest difference in start time (within our limits of -6 to 6) then there will be a better chance for subsiquent records to be matched.  Just something to think about.  Go ahead and change the 18 to a 16 in record 2 to illistrate what I mean.

Actually, now that I think about it it doesn't really matter that we maximize the difference.  Sometimes it is good that we maximize, but sometimes it is bad.  It just turns on in this case that it was better that we maximized, but in other cases we will find that it would have been better to minimize the difference in start time.  It would be nice if we could figure out which case was better proir to testing for it.  If we can predict which is better then we can't really consider that optimization.  I'll give it a little thought, maybe we could make an educated guess by finding the mean of the single item start times and depending on which side of the mean our individual case falls we could maximize or minimize the difference in start times.  It might not be worth it so I won't work to hard on such an idea.  Let's see if the results from the current code are acceptable first.

"If we can predict which is better then we can't really consider that optimization"

should have read...

"If we CAN'T predict which is better then we can't really consider that optimization"

Enlade,

This is so awsome. looks very nice.

Just a few tweaks..
______________________________i've place this in the text file   (basically i've copy and paste the original)
30
23,3,1428,0
23,4,1428,0
19,4,1221,0
1,1,1010,0
1,2,1010,0
2,1,1110,0
2,1,1110,0  
2,2,1110,0
25,5,1111,0
18,5,1234,0
19,1,1221,0
19,2,1221,0
19,3,1221,0
23,1,1428,0
23,2,1428,0
23,3,1428,0
23,4,1428,0
19,4,1221,0
1,1,1010,0
1,2,1010,0
2,1,1110,0
2,1,1110,0  
2,2,1110,0
25,5,1111,0
18,5,1234,0
19,1,1221,0
19,2,1221,0
19,3,1221,0
23,1,1428,0
23,2,1428,0

output data should be..

no change..Since there are no unique data on the third column

no change is we are not going to place the auto number on the fourth column.

By the way the fourth column is the one we need ( we are placing auto numbers to know how many we have related and where they are located)

i.e. of a proper output for BinaryIDArr

18,5,1234,1
17,5,1234,2
19,4,1221,2
23,3,1428,1
23,4,1428,1
19,1,1221,2
19,2,1221,2
19,3,1221,2
23,1,1428,1
23,2,1428,1

so the next set would have 3 then 4 then 5 ....auto increment number for the fourth column. (it's acting as an identifier on which records are related)

Thanks.

Enlade,

I get it now, we are having problems with duplicates on unique records, how do we handle them...

My apology for not understanding it clearly earlier.

Here the examples below are duplicates..

30
1,1,1010,0
1,1,1010,0
1,2,1010,0
1,2,1010,0
2,1,1110,0
2,1,1110,0  
2,2,1110,0
2,2,1110,0
18,5,1234,0
18,5,1234,0
19,1,1221,0
19,1,1221,0
19,2,1221,0
19,2,1221,0
19,3,1221,0
19,3,1221,0
19,4,1221,0
19,4,1221,0
23,1,1428,0
23,1,1428,0
23,2,1428,0
23,2,1428,0
23,3,1428,0
23,3,1428,0
23,4,1428,0
23,4,1428,0
25,5,1111,0
25,5,1111,0

Output should be as follows:
1,1,1010,0
1,1,1010,0
1,2,1010,0
1,2,1010,0
2,1,1110,0
2,1,1110,0  
2,2,1110,0
2,2,1110,0
18,5,1234,1  <----first unique record found
18,5,1234,2   <-----second  unique record found
19,1,1221,1
19,1,1221,2
19,2,1221,1
19,2,1221,2
19,3,1221,1
19,3,1221,2
19,4,1221,1
19,4,1221,2
23,1,1428,3
23,1,1428,4
23,2,1428,3
23,2,1428,4
23,3,1428,3
23,3,1428,4
23,4,1428,3
23,4,1428,4
25,5,1111,3  <--------third unique record found
25,5,1111,4<--------fourth unique record found

we should not only check the third column for unique values but we also have to consider duplicates (duplicate records on unique values)
i.e.
18,5,1234  <-------------unique in the list but the next record is a duplicate so this means it's not unique anymore.
18,5,1234

We need to renew what i've mention on finding the unique in third column since this won't work.
any idea how we can create the output above ?

Ok, two questions.

First, Do you think that using the 4th column (3rd index) as a grouping flag is the way you want to do this?  The program already groups everything into collections so you might be able to simply use the groups in the collection to generate your report rather then modify the 4th (3rd index) element of your input array.  Its not hard to modify the input array from the collections, but if all you are doing is generating a report from the new array then you might be better off just generating the report directly from the groups in the collections.  Just a thought.

Second, As far as duplicates.  Lets go back to the two main cases of duplicates and you discribe for me what you want to happen in each case.

1.  There is a group that only has duplicates and no other similar items.  For example,

10-1-1111
10-1-1111
10-1-1111
10-1-1111

2.  There is a group that has both duplicates and other similar items.  For example,

10-1-1111
10-1-1111
10-1-1111
10-2-1111
10-3-1111
10-4-1111

Now depending on how you choose to handle the second case there can be a number of other special cases to consider.  For instance, if you decide to simply ignore duplicates completely then the case arrises where duplicate removal results in a new set of 4 items and the case when duplicate removal results in a set that does not have 4 items (but maybe with duplicates it did have 4 items before the duplicates were removed).

I reread your previous message and I think I get enough from that to be able to handle duplicates properly.  If you can think of anything else from what I said in my previous message then go ahead and elaborate, but for now I will go ahead and change the code.  Hold up a bit.

Ok, give this a try.  Remember to answer my first question above about using collections instead of recreating the array with the grouping flags.

http://www.enlade.com/Samples/MiscTest4-a.zip

How about this as a possible solution to the overall problem.  If we list out all the possible combinations of groups that give 5 days and we organize them by priority.  For instance, this might be a good priority for the groupings:

#Items In Group
1     2     3     4
---------------------
1     N     N     1
2     N     1     N
1     2     N     N
3     1     N     0
N     1     1     N
5     N     N     N

Right now the code is only grouping in the first way (1  N  N  1), but I would think that you still need to place people on the other unplaced schedules.  So, you might want to consider the other 5 possible groupings.  Just a thought.

Or maybe this would be better:

#Items In Group
1     2     3     4
---------------------
1     N     N     1
2     N     1     N
1     2     N     N
N     1     1     N
3     1     N     N
5     N     N     N

Yea, that seems more preferable.

Enlade,

I've run the code, it's amazing.

I'm not sure how to handle the flaging/collection or if i'm doing it right, planed to relate those records using the fourth column.
I could easily transfer data (array) to the database.

the database have columns for...

Mon Tue Wed Thu Fri Sat Sun Relation Schedule Others......

as you can see i can place the 3rd index on to the Relation column. Kindly give guidance on how to do this properly.
__________________________________________________________________________________________

WOW, that Item in group is a great idea!!!

but how does it work?
what is N ?
why are there only 4 items?

I'll stay up until 2:00AM here, i think you're on EST (1:00PM)

Thanks.

Enlade,

I've created an excel file that has a very neat look base on the array we are solving; once you've taken a look at this you'll surely know how to attack this problem where i'm no hope with (been stuck for 2 months).

http://www.geocities.com/eeforupload/arraydetailed.xls

Thanks.

Well, when you run my function it basically gives you two resulting data sets.

1.  A set (collection) of sets (collections) that contain groups of indexes (into the original array) that consist of 5 separate days where 4 of the days are on one schedule and the 5th day is on a different schedule.
2.  A set of indexes (into the original array) that consists of all of the schedule days that could not be matched.

So to walk through the first data set you would do something like this:

‘This loop simply walks through each Set within the OutSets collection
For i = 1 To OutSets.Count

  ‘This loop simply walks through each element of the Set that is referenced
  ‘from the above loop (i)
  For j = 1 To OutSets.Item(i).Count

    ‘tempIndex represents an item within the Set that was selected from OutSets
    ‘collection using (i) and (j).  Remember that all that we store in these sets
    'is the indexes into the input array (in my case GlobInData).  So tempIndex
    'is ultimitly just an index that you use to referece the real data that is located
    'in GlobInData (see next comment for more explaination).
    tempIndex = OutSets.Item(i).Item(j)

    ‘Now all you do is use tempIndex to output any of the data that you want that
    ‘exists in the input array.  You reference the data using tempIndex as the
    ‘index into the array.  For example, if you wanted to reference the day
    ‘you would use the reference GlobInData(1, tempIndex) and if you wanted
    ‘to reference the Schedule you would reference it with GlobInData(2, tempIndex)

  Next j
Next i

To walk through the second data set is simpler since it is not a Set of Sets like the first, but rather it is just a simple set.  This only involves one loop.

For i = 1 To NotPlaced.Count
  tempIndex = NotPlaced.Item(i)

  ‘Again, you now use tempIndex to reference the item data in the GlobInData array
  ‘just like you did above.  For example, GlobInData(0, tempIndex) is the time that
  ‘the schedule starts.  Remember this set contains the indexes of all the records
  'that we did not place.
Next i

Ok, so you want this to be formatted similar to the way that you have in your Excel spreadsheet?  Is it your intention to store this data exactly as you have it in the spreadsheet?  I mean, do you want to simply output this data as a comma delimited text file and then you can read it into Excel?  If so, then why bother with Excel at all?  Why not just generate your report directly from your VB program?  I am not recommending that you do or do not use Excel or even Access.  I simply don't know what is best yet.  It all depends on what you plan to do with this data once your VB program creates it.  If all you are going to do is generate a report that people will look at in order to figure out their work week then I think I would just generate the report directly from my VB program.  However, if it is the case that you manipulate this data either by reloading it periodically into this same VB program (as more schedules are added) or you manipulate it in some other way using some other program then it would make sense to store it either in a text file or in Excel or a database or elsewhere.  I can't answer that for sure because I don't know what happens to this data once the program generates it.  I'm simple working on the generating part at this time.  This is just more for you to think about.

Just so you can see an example of walking through those sets like I mentioned above.  Let me write a little code that adds sets up that forth column using the sets.  Basically, I'll walk through the sets just like I described above, but instead of outputting anything I'll just set that forth item to some auto-increment number like you wanted.

‘This loop simply walks through each Set within the OutSets collection
For i = 1 To OutSets.Count

  ‘This loop simply walks through each element of the Set that is referenced
  ‘from the above loop (i)
  For j = 1 To OutSets.Item(i).Count

    ‘tempIndex represents an item within the Set that was selected from OutSets
    ‘collection using (i) and (j).  Remember that all that we store in these sets
    'is the indexes into the input array (in my case GlobInData).  So tempIndex
    'is ultimitly just an index that you use to referece the real data that is located
    'in GlobInData (see next comment for more explaination).
    tempIndex = OutSets.Item(i).Item(j)

    ‘Now all you do is use tempIndex to output any of the data that you want that
    ‘exists in the input array.  You reference the data using tempIndex as the
    ‘index into the array.  For example, if you wanted to reference the day
    ‘you would use the reference GlobInData(1, tempIndex) and if you wanted
    ‘to reference the Schedule you would reference it with GlobInData(2, tempIndex)

    ‘But instead of outputting anything I will set that forth item like you wanted.  Since,
    ‘each set is already indexed I will just use the set index (i) for the auto-increment
    GlobInData(3, tempIndex) = i    

  Next j
Next i

And I am assuming that you want to set the 4th column (3rd index) to 0 for the unplaced items.  That is easy enough.

For i = 1 To NotPlaced.Count
  tempIndex = NotPlaced.Item(i)

  ‘Again, you now use tempIndex to reference the item data in the GlobInData array
  ‘just like you did above.  For example, GlobInData(0, tempIndex) is the time that
  ‘the schedule starts.  Remember this set contains the indexes of all the records
  'that we did not place.

  ‘All you do is assign a 0 and that is it.
  GlobInData(3, tempIndex) = 0

Next i

Remember, I could have just as easilly output that information to a text file or stored it into a database or sent it to the printer or whatever.  Its just that in this case you wanted to see how you might change the input array to store the groupings in the 4th column (3rd index).  Clearly, if you are writting this to a comma delimited text file so that you could read it into Excel you would not bother modifying the intput array.  You would simply write out the grouping number (i) in whatever column you want it to show up in Excel.  So, the above code is probably not at all what you will use even if you did want to save the grouping information.  Still, it does illistrate how you would walk through the sets in order to accoplish some real task.

Oh, let me also explain my little priority chart.  This thing:

#Items In Group
1     2     3     4
---------------------
1     N     N     1
2     N     1     N
1     2     N     N
N     1     1     N
3     1     N     N
5     N     N     N

First off there are only 4 columns because of the way you described the problem.  Personally I think there should be 5 since there are 5 days.  But again, I'm not familiar with the problem enough to know for sure what is best.  Remember that the way my program works is that it finds sets of similar records and groups them.  After it groups everything that it can group you will have sets that contain 1, 2, 3, and 4 items (again, I don't know why you don't allow 5 item groupings, but that is the way you limited the problem).  So that is what the 1, 2, 3, and 4 stands for.

Now, the rest of the rows describe all of the combinations of these groups that allow you to have 5 days of non-overlapping schedules.  For example, you can have 1 set of 1 item along with 1 set of 4 items and that would give you 5 items (providing all 5 items meet our restrictions like they do not have the same day and the do not differ in start time by more then 3 hours).  Additionally, if we had 3 sets of 1 item along with 1 set of 2 items then that would also give you 5 items (again they must all meet our restrictions).

The "N" simple means "None", but you can replace it with 0 if it helps.  It just means that 0 sets of that type are included for that row.

Notice that every possible combination of set groupings that would give you 5 days (meeting all of our restrictions) is found in that chart except for N, N, N, N, 1.  This would mean that you have 1 set of 5 items.  This is because you limited the groupings to 4 items.

It is important to note that the priority of the rows at the top of the list are higher then those at the bottom.  This means that the first thing we find is 1, N, N, 1 groupings (which is all that we currently do), but after we find all of those groupings we then look for 2, N, 1, N groupings, and then after they are all marked as placed we then go on to look for 1, 2, N, N groupings, etc.  Until we have exhausted our search and whatever is left over was not placeable (and must be considered manually).

Most importantly, notice that the only grouping that we are currently considering is 1, N, N, 1.  This is to say that our algorithm currently only does the following chart:

#Items In Group
1     2     3     4
---------------------
1     N     N     1

Which is simply saying that you are matching 1 group of 1 item with 1 group of 4 items (again, meeting all restrictions).  As I said, I think you need to consider this chart instead (to include 1 group of 5 items).  But I can't say whether this will work for you or if we are better of with some other priority.

#Items In Group
1     2     3     4     5
--------------------------
N     N     N     N     1
1     N     N     1     N
2     N     1     N     N
1     2     N     N     N
N     1     1     N     N
3     1     N     N     N
5     N     N     N     N

I just don't know if this is better or worse.  That is up to you to decide.

Here, let me try to explain each column to further clarify what I am trying to describe by that chart.

#Items In Group
1  2  3  4  5
---------------
N  N  N  N  1   Person starts at the same time for all 5 days.
1  N  N  1  N   Person starts 1 day at one time and 4 days at a different time.
2  N  1  N  N   Person starts 1 day at one time another day at another time and the remaining 3 days at another time.
1  2  N  N  N   Person starts 1 day at one time another 2 days at another time and a further 2 days at another time.
N  1  1  N  N   Person starts 2 days at one time and another 3 days at a different time.
3  1  N  N  N   Person starts 1 day at one time another day at another time...etc.
5  N  N  N  N   Person starts 1 day at one time another day at another time another day at another time...etc.

Hope that helps.

Let me zoom in on one row to give an even better description.  Lets look at:

1  2  N  N  N

This simply means that the person is working on three different schedules.  I'm not really sure if that means that it is different times, but it could be.  However, it does mean that the difference in any two start times of any schedules in this group is less then 3 hours (between -6 and 6).  It also means that each day of the 5 days in this grouping are different (they include monday through friday).

For example, the following is a group that fits this catagory.

1-1-1000
2-2-1111
2-3-1111
3-4-2222
3-5-2222

What I am not sure is whether this could occure:

1-1-1000
1-2-1111
1-3-1111
1-4-2222
1-5-2222

But if it can occure then the above grouping (1, 2, N, N, N) will match these records.  Actually, I don't even know if this could occur:

1-1-1000
1-2-1111
1-3-1111
2-4-1111
2-5-1111

In this case you still have a match on this grouping (1, 2, N, N, N), but you see that 4 days have the same schedule number even though the start time is different.  So, maybe it isn't correct what I said above about this grouping (1, 2, N, N, N) giving the person 3 schedules.  In this case you would have 2 schedules but you would still have 3 groupings of similar records (one with 1 item and 2 with 2 items).  You will have to think about all this and come up with a plan to cover all of these cases.

I hope that makes it clear.

Two Quick question

Does every record that has the same schedule number also have the same start time?  For instance, is this an impossible situation:

1-1-1000
2-2-1000


Does every start time have only one specific schedule number?  For instance, is this an impossible situation:

1-1-1000
1-2-1111


I'm guessing it is "yes, it is impossible" on the first question and "no, that is possible" on the second question, but I just want to make sure.

Enlade,

You've nailed!!! That's how we could do it.

The array i've created will be use for a report (same format as the excel file i've posted) but this time it will look alot better, since we will add records with 5 working days.

so it will have 5 "Y" instead of one in the excel. And some split one's.  (only 4 "Y", 3 "Y", 2 "Y" etc) and populating the relate column to tell that these two records are combined.

only two possible combinations of schedules(5 working days).

1. The person has same schedules for the whole week.  
i.e.  monday up to friday he comes in at 9:00
-combination-
Any five days that have similar schedules (third index in the array)


2. The person has two different schedules.
i.e. on monday he comes in at 9:00 but on tuesday, wednesday, thursday, friday he comes in at 10:00
-combination-
Any one or two or three or four days that have similar schedules but different on the remaining days (5 total)

______________________two quick questions
Does every record that has the same schedule number also have the same start time?  For instance, is this an impossible situation:

1-1-1000
2-2-1000

-Yes this is impossible.  

Here are a sample of possible same schedule number.
1-7-1000
1-6-1000
1-5-1000
1-4-1000
1-1-1000

* the schedule number is base on the start time (unique sets of schedule number per start time -half-hour-)
there are 40 unique schedules per start time - so total of 1,920 schedule numbers.
(start time * 40) -39 to get the first record of the schedule number for that specific start time.

third column - contains numbers from 1 upto 1,920

-how can we tell that the combining those split schedules first will give us more sets of schedules rather than starting with 5 similar once?
-can we run both then see which has more sets? scoring system?

Thanks.

Enlade,

Please follow this link, contains raw data of binaryIdArr
http://www.geocities.com/eeforupload/BinaryIdArr.xls

Thanks.

What about the second quick question?  Is this possible:

Does every start time have only one specific schedule number?  For instance, is this an impossible situation:

1-1-1000
1-2-1111

I think the answer is that it is possible.  Just want to make sure.

Enlade,

Good morning.

Does every start time have only one specific schedule number?  For instance, is this an impossible situation:

1-1-1000
1-2-1111

no, every start time doesn't have only one specific schedule number.

it rotates on the 40 schedules per start time
i.e.
1-x-1000 up to 1040

this can happen (already discuss eralier duplicates)
1-x-1000
1-x-1000

Thanks.

Here is what I am hearing you say.  I'm hearing you say that you want to implement this priority.

#Items In Group
1     2     3     4     5
--------------------------
N     N     N     N     1
1     N     N     1     N
2     N     1     N     N
1     2     N     N     N
N     1     1     N     N
3     1     N     N     N
5     N     N     N     N

However, I think I hear you saying that you have one additional limitation.  Currently we limit the above grouping rows by saying:

1.  Every item in the grouping must occur on a different day.
2.  Every item in the grouping must only differ by 3 hours (-6 to 6) in start time.

Now I am hearing you say that you want to add the following additional limitation:

3.  Any specific employee can have either 1 set of start times (ie. start at 9am all 5 days) or they can have 2 sets of start times (ie. start at 9am on some days and at 10am on the others).  This means that you don't want to allow cases where the employee has to start at more the 2 different times during the week (ie start at 9am on some days, 10am on other days, and 11am on the remaining days is not allowed).

For example, this would not be a valid grouping:

1-1-1111
2-2-2222
2-3-2222
3-4-3333
3-5-3333

Even though it meets the first two limitations this group does not meet the third.

Is this what you are saying you want to do?

Ignore the fact that my schedules are not in the format that they should be.  From what you are saying it seems like I should have used examples like this:

1-1-1001
2-2-2002
2-3-2002
3-4-3003
3-5-3003

or maybe it should be like this:

1-1-1000
2-2-2001
2-3-2001
3-4-3002
3-5-3002

But for now lets not focus on the incorrectness of my schedule numbers.  So when I ask if this is possible:

1-1-1111
2-2-2222
2-3-2222
3-4-3333
3-5-3333

Don't say "No, because the schedule numbers are wrong".  Instead, say "No, because an employee can only start at 2 different times during the week" (if that is the case).  I just want to avoid letting that interfer with our progress at this time.  I'll try to use a valid schedule number in the future though.

So, just to clearify the schedule so that I can try to get them right.  Does it start at 0 or 1?  For instance, is it:

0-1-1000
1-2-1001
2-3-1002
etc.

or is it

1-1-1000
2-2-1001
3-3-1002
etc.

I think it is the later since you said that your start time went from 1 to 48 in your original message.

Oh, I guess it could also be:

1-1-1001
2-2-1002
3-3-1003

Yea, that is probably what it is suppose to be.  Right?

Enlade,

My apology for the confusion.

Yes, the start time begins at 1 and goes upto 48  (every half hour)

Yes, we don't want to have three different start times or three different schedule (3rd index). the employee would get mad at us :-)

There are only two combinations for relating records.

one is full set - this means everyday a person comes in at 9:00. (5 days total)
i.e.
1-1-1111   <----notice the day part is the only one changing    
1-2-1111
1-3-1111
1-4-1111
1-5-1111

4-7-2222
4-6-2222
4-3-2222
4-2-2222
4-1-2222

two is split set - this means one or two or three or four days that have similar schedules but different on the remaining days (5 days total)

i.e.
1-1-1111    <----two same schedule     (this is called split schedules)
1-2-1111    
2-3-4444       <-------three same schedule
2-4-4444
2-5-4444


3-1-2222   <-----one schedule     (this is called split schedule)
4-2-1111    <-----four schedules  
4-3-1111
4-4-1111
4-5-1111

Using your item grouping we can come-up with a scoring system on grading which approach to try first so that the end result would give us more set of schedules. (or maybe try them both and find out ?)

I mean, if we search for split schedules first would this generate more set of schedules? or relating those "ideal" one's first?

Thanks.

Ok, I almost understand.  Just need to clearfy a bit more.  You said,

"Yes, we don't want to have three different start times or three different schedule (3rd index)."

Did you really mean to say "three different schedule(s)" in that sentance?

For instance, would this not be a valid grouping?

1-1-1000
1-2-2000
1-3-2000
2-4-3001
2-5-3001

In this case you have 2 different start times during the week; however, you have 3 different schedule numbers.  From what you said above (earlier) such an instance is possible.  Would this not be an acceptable grouping since the employee is not starting at more then 2 different start times during the week?

Enlade,

Yes, that is correct.

We don't want to have three different start times or three different schedule(s) (3rd index).

This is not a valid grouping.
1-1-1000   <------------this is a no-no (1000)   should be 2000     :-)
1-2-2000
1-3-2000
2-4-3001    
2-5-3001    

Thanks.

Ok, so this is my final description of the problem.  Just give it your mark of approval and we are good to go.

First, we can describe the priority of the groupings in the following way.  The grouping at the top of the list is performed first and then subsequent groupings are selected in the order that they fall in the list (from top to bottom).

#Items In Group
1     2     3     4     5
--------------------------
N     N     N     N     1
1     N     N     1     N
N     1     1     N     N

I think that the above consists of all the possible combinations of groupings that will assure that we can follow the grouping rules.

The following 5 rules are used to perform the grouping:

1.  Sets are selected whose grouped members number 5 (1 for each day).
2.  Every item in the grouping must occur on a different day (1 for each day).
3.  Every item in the grouping must only differ by 3 hours (-6 to 6) in start time.
4.  Any specific employee can have either 1 start time for every day of the week or they can have 2 start times for different days of the week.
5.  Any specific employee can have either 1 schedule number for every day of the week or they can have 2 different schedules numbers for different days of the week.

How does that sound?  Did I leave anything out?

Actually, I could get rid of rule 4 since rule 5 assures that rule 4 will occure, but I left it in anyways (you can tell from my messages that I like to be verbose....hee hee).

By the way, this is very nice:

#Items In Group
1     2     3     4     5
--------------------------
N     N     N     N     1
1     N     N     1     N
N     1     1     N     N


You see how none of these groupings overlap.  So we can solve for them all at one time.  This means that there isn't really any priority like we mentioned earlier.  Everything can be solved at the same time (less loops, less work).  So, I'm hopeing that that is going to be a good solution for you.

Hmmmmm....I just noticed that you allow for 7 days with the same schedule number.  That is to say that this is possible:

1-1-1000
1-2-1000
1-3-1000
1-4-1000
1-5-1000
1-6-1000
1-7-1000

That is going to be a little problem.  Just thought I would mention it.  Let me think about it more and see if I can come up with something useful.

The quickest solution would be to simply break 6 item groups into a 5 item group and a 1 item group and to also break 7 item groups into a 5 item group and a 2 item group.  This will not give you the best solution every time, but it will give you a reasonable solution.  Keep in mind that there is definitly some area of optimization that can be done in relation to handling 6 and 7 item groups, but how about we try breaking them up for now?

Ok, here are some areas of optimization that you need to consider:

1.  We need to work out some preference on how I should break up 6 and 7 item groups.  For instance, lets look at a 7 item group.  Do you want me to break up the weekdays (1 through 5) from the weekends (6 and 7).  This would be good if you think that it is easier to match up unplaced weekends then it would be to match up unplaced weekdays.  If you think it would be harder to match up weekends then maybe we should break it up as 1-2 and 3-7.  That way the weekends are automatically placed in a group of 5 and all we need to do is place a monday and tuesday grouping.  Then again, this all depends on whether employee's prefer working on weekends verses working on weekdays.  If given the choice they might like to work 1-5 rather then 3-7.  You see what I mean by preferance.  This all depends on what outcomes would would tend to prefer (given your employees).

2.  If a grouping of 4 or a grouping of 3 or a grouping of 2 is not placeable then there is an oppertunity to also break up those groupings such that their subgroupings might be placeable.  For instance, if we have the following:

1-1-1000
1-2-1000
2-2-1001
2-3-1001
2-4-1001
2-5-1001

This would result in a set of 2 items and a set of 4 items.  When we run the program on this data it will result in no groupings.  However, if the program can realize that there are no groupings for the set of 2 items and it was smart enough to break up that set into 2 sets of 1 item.  Then the program could find this grouping.

1-1-1000 - 1
1-2-1000 - 0
2-2-1001 - 1
2-3-1001 - 1
2-4-1001 - 1
2-5-1001 - 1

If that is a good idea then the question remains:

"How should be break up decide to break up groups such that the order maximizes the overal groupings?"

This is again an optimization that relates to the preferences of your company and its employees.

That should read:

"How should we decide to break up groups such that the order maximizes the overal groupings?"

By the way, this is an np-complete problem.  So you will not be able to find the perfect solution.  This is to say that no algorithm you write will be able to always give you the maximum number of groupings that are possible from your input set.  However, that doesn't mean that you can't write a function that will give you a reasonable solution.  This is what we are trying to do now.  We can already write a function that will give us a solution; however, we want to see if there are any areas that we can tweak to give us even better solutions.  Still, always keep in mind that you will never be able to write a function that gives you the absolute best solution.

Opps, I missunderstood how you format the Schedule number.  I thought you just put the start time in the second two digits of the number.

12,1,1012

But that isn't want you do at all.  Is there some way that you can calculate the start time from the schedule number.  What I mean to ask is, can you tell simply by looking at the schedule number what the start time is (without looking it up or anything)?  For instance, what is the start time for:

1012

And how did you calculate that start time (or can you even calculate it at all)?  Or is it arbitrarilly set by someone?

Ok, lets now start working from this code.  I think it does most of what you want.  All we need to do now is to figure out what tweaks we can do to make it give you a better and better solution.

http://www.enlade.com/Samples/MiscTest5-a.zip

Better still, I have put your actual data into the Data.txt file so you can see it work on your data.  Check this code out instead of the above link:

http://www.enlade.com/Samples/MiscTest5-b.zip

We have two further objectives.

1.  We need to reduce the number of items that end up in the NotPlaced list.
2.  We need to improve the quality of selection that the program makes based on tweaking the program in such a way that it tends to give results that are more preferable by your company and your employees.

Some of the volumns of type that I have given you above will help you to think about how you might improve on both of these topics.

Nope let me restate that.  We actually have 4 objectives.

1.  We need to reduce the number of items that end up in the NotPlaced list.
2.  We need to improve the quality of selection that the program makes based on tweaking the program in such a way that it tends to give results that are more preferable by your company and your employees.
3.  Improve on the runtime of the code so that it can handle larger sets of data.
4.  Cause Experts-Exchange to crash due to the enormous amount of text that we are putting in this thread.

Mind you, with the sample data you gave me there is no way to directly reduce the NotPlaced list any further.  All that is left in NotPlaced are sets of 1 items and sets of 2 items.  So it would require you to create a grouping that had more then 2 schedules (because you can't make 5 days from sets of 1 items and sets of 2 items without having more then 2 schedules in the grouping).  Having more then 2 schedules in a grouping would break one of our rules.  So there is no further direct reduction that can take place on the NotPlaced list for the data you gave me.

Of course, you might be able to achieve a reduction by better selecting the groupings from the beginning.  So, improving the quality of selection by tweaking the program might also give us a reduction in the NotPlaced, but then again, it could just as well give us an increase in the NotPlaced (the old Quantity vs Quality theme in action).

I made a few minor changes to the program so if you already downloaded it then redownload it again from here and use this.

http://www.enlade.com/Samples/MiscTest5-b.zip

Enlade,

Sad to say i wasn't able to downlaod the zip file, it said 1 byte missing when running winzip (this is for all MiscTest5-x.zip).

_____________________________using your examples now
Hmmmmm....I just noticed that you allow for 7 days with the same schedule number.  That is to say that this is possible:

1-1-1000
1-2-1000
1-3-1000
1-4-1000
1-5-1000
1-6-1000
1-7-1000

That is going to be a little problem.  Just thought I would mention it.  Let me think about it more and see if I can come up with something useful.

-nope, this is not a possbile set since it's a group of 7 records but if we get only 5 records then it is a good set.

By the way, second column - contains numbers from 1 upto 7 (this is a representation of monday upto sunday)

we are grouping sets of 5.

i.e.
1-7-1000   <--------since the day are different from each record, this is a good set.
1-5-1000
1-1-1000
1-3-1000
2-4-2000


Thanks.

Oh....strange.  Let me post that again.  Try it now:

http://www.enlade.com/Samples/MiscTest5-b.zip

Win $1 million dollars (mooohaaaa haa haa haaaaaa).

http://www.claymath.org/millennium/P_vs_NP/

Some interesting reading.  Its relatable, but really just an aside.

Enlade,

My apology for the late reply, the results where excellent.
Sadly the mix and match were disapointing, seems there's no way around this.

I give up and going back to think of a new approach.

Thanks so much for yout time and patience.