all possible combinations for scheduling pattern

[jenkins]

Hi all,

I need to write some php code to choose all possible combinations to schedule classes based on a pre-set pattern.

For example, if I want to schedule a 3-hour course in the highlighted times in the timetable attached using one 2-hour block and one 1-hour block there are 40 possible combinations.

Monday from 7:30 to 9:30 is the 2-hour block plus 1-hour from either of the 8 hours from the other 4 days gives 8 possibilities. Do this 5 times and there are 40 combinations.

I've researched a lot and have read that brute-force is the best method. Others say use Recursive functions/Multi Dimensional Array Combinations, yet others say use the permutations formula.

Does anyone have any experience with such code?

 

Ideally I would like the output to be as follows for 3 hrs = 1x2hr + 1x1hr (as described above) :

1 | Monday | 7:30 | 2 hours

1 | Tuesday | 9:30 | 1 hour

2 | Monday | 7:30 | 2 hours

2 | Tuesday | 10:30 | 1 hour

3 | Monday | 7:30 | 2 hours

3 | Wednesday | 7:30 | 1 hour

4 | Monday | 7:30 | 2 hours

4 | Wednesday | 8:30 | 1 hour

..... and so on ......

 

Any help/feedback/sample code would be greatly appreciated.

 

[requinix]

If you want everything then you may as well just brute-force it. Whether that involves recursion or a multi-dimensional array or something else depends: recursion isn't the best for this because there's only two "layers" to process (first is the 2-hour block, second is the 1-hour block), while a 2D array is okay because the output will be small enough that you don't have to worry about memory usage.

 

Basically,

$blocks = array();
foreach ($twohourblocks as $thb) {
    foreach ($onehourblocks as $ohb) {
        if ($ohb not contained in the $thb) {
            $blocks[] = array($thb, $ohb);
        }
    }
}

[jenkins]

requinix, thanks for your help. You've put me on the right track.

 

I've set it up like so (the arrays will not be hardcoded; the info will come from a db) However, the output does show the one-hour-blocks at the same time as the two-hour-blocks.

I did work on this when it was late, so I could be missing something simple here.

 

My other challenge is I need this to be as dynamic as possible. I may need to schedule a 5-hour course as 5 hrs = 2x2hr + 1x1hr or a 4-hour course as 4hrs = 2x2hr or 4hrs = 1x2hr + 2x1hr

 

Any words of wisdom?

 

 

$onehourblocks = array('M-7:30','M-8:30','T-9:30','T-10:30','W-7:30','W-8:30','Th-9:30','Th-10:30','F-7:30','F-8:30');
$twohourblocks = array('M-7:30','T-9:30','W-7:30','T-9:30','F-7:30');

$blocks = array();
foreach ($twohourblocks as $thb) {
foreach ($onehourblocks as $ohb) {
if (!in_array($ohb, $thb)) {
		$blocks[] = array($thb, $ohb);
	}
}
}

 

OUTPUT:

 

Array
(
[0] => Array
	(
		[0] => M-7:30
		[1] => M-7:30
	)

[1] => Array
	(
		[0] => M-7:30
		[1] => M-8:30
	)

[2] => Array
	(
		[0] => M-7:30
		[1] => T-9:30
	)

[3] => Array
	(
		[0] => M-7:30
		[1] => T-10:30
	)

[4] => Array
	(
		[0] => M-7:30
		[1] => W-7:30
	)

..... and so on ......

[Psycho]

If the data is in a database do a simple JOIN query to get all the combinations.

 

SELECT time1.day, time1.hour, time2.day, time2.hour
FROM timeBlocks AS time1
JOIN timeBlocks as time2
WHERE time1.length = 2
AND time2.length = 1

 

EDIT: After rereading the post I think you want it so the 2hour and 1hour blocks are not on the same day, so you would use this

 

SELECT time1.day, time1.hour, time2.day, time2.hour
FROM timeBlocks AS time1
JOIN timeBlocks AS time2
WHERE time1.length = 2
AND time2.length = 1
AND time1.day <> time2.day

Edited January 31, 2013 by Psycho

[jenkins]

Thank you Psycho. This did the trick for 3 hrs = 1x2hr + 1x1hr.

Do you think it is possible to do a similar select from the db for the pattern 4hrs = 1x2hr + 2x1hr ?

I think it will be even more complicated to do a 5-hour pattern like: 5 hrs = 2x2hr + 1x1hr or 5 hrs = 1x2hr + 3x1hr.

I'll need a few loops, right...?

Thanks again.

[Psycho]

Umm . . . I based my proposed solution on the example you posted in your original post. If the requirements are more complicated than that it would have been nice that you at least stated as much. I don't have my test table to verify, but I think you can do this for other conditions - but the query would get more complicated.

 

For a 4 hour class (2 + 1 + 1) I think this should work:

SELECT time1.day, time1.hour,
   time2.day, time2.hour,
   time3.day, time3.hour

FROM timeBlocks AS time1
JOIN timeBlocks AS time2
JOIN timeBlocks AS time3

WHERE time1.length = 2
 AND time2.length = 1
 AND time3.length = 1

 AND time1.day <> time2.day
 AND time1.day <> time3.day
 AND time2.day <> time3.day

 

For a 5-hour pattern (2 + 2 + 1), I think this would work

SELECT time1.day, time1.hour,
   time2.day, time2.hour,
   time3.day, time3.hour

FROM timeBlocks AS time1
JOIN timeBlocks AS time2
JOIN timeBlocks AS time3

WHERE time1.length = 2
 AND time2.length = 2
 AND time3.length = 1

 AND time1.day <> time2.day
 AND time1.day <> time3.day
 AND time2.day <> time3.day

[jenkins]

Psycho, you're a great help! Thank you so much.

The code you provided for the 4 and 5 hour patterns is working but it is returning duplicates; it displays each possibly twice

 

For example: 4hrs = 1x2hr + 2x1hr which is 2 + 1 + 1

 

First it displays:

Monday - 9:30 for 2 hours

Tuesday - 7:30 for 1 hour

Thursday - 7:30 for 1 hour

 

Then it will display:

Monday - 9:30 for 2 hours

Thursday - 7:30 for 1 hour

Tuesday - 7:30 for 1 hour

 

It repeats the pattern and swaps the 1-hour blocks assigned to Tuesday and Thursday. I tried selecting distinct/unique but I don't think it is as simple as that.

 

Any thoughts...?

 

Thanks again...!!!

[Psycho]

Any thoughts...?

 

Yes, I think all the time.

[Psycho]

I tested these somewhat and they appear to produce the correct results

 

For a 4 hour class (2 + 1 + 1) - 120 total combinations.

SELECT time1.day, time1.hour,
	 time2.day, time2.hour,
	 time3.day, time3.hour

FROM timeBlocks AS time1
JOIN timeBlocks AS time2
   ON time1.day <> time2.day
JOIN timeBlocks AS time3
   ON time1.day <> time3.day
   AND STRCMP(time2.day, time3.day) < 0

WHERE time1.length = 2
   AND time2.length = 1
   AND time3.length = 1

 

For a 5-hour pattern (2 + 2 + 1) - 60 total combinations.

SELECT time1.day, time1.hour,
 time2.day, time2.hour,
 time3.day, time3.hour

FROM timeBlocks AS time1
JOIN timeBlocks AS time2
   ON time1.day <> time2.day
   AND STRCMP(time1.day, time2.day) < 0
JOIN timeBlocks AS time3
   ON time1.day <> time3.day
   AND time2.day <> time3.day

WHERE time1.length = 2
   AND time2.length = 2
   AND time3.length = 1

Edited February 1, 2013 by Psycho

[jenkins]

Psycho, you are a genius...!

 

Thank you so much...!!!

[jenkins]

Psycho, I am trying to find a pattern for 5hr = 5x1hr ( 1 + 1 + 1 + 1 + 1 )

Do I now need to use STRCMP for the day and the hour?

On paper I calculated a total of 32 combinations.

[Psycho]

Instead of just providing the answer, let me give you a review of the analysis I went through. You should be able to get the solution yourself and it will help you to think critically. After the previous issue identified, I made the following analysis:

 

The duplications was, as you identified, due to days of similar lengths being swapped. Why was this? Well, the 4 hour query was looking for one day of 2-hours and 2 days of 1-hour. Obviously there is no problem with the single 2-hour day being duplicated since it is only looking for one. So, the problem was just the two 1-hour days. In the query I had a condition to ensure that the two 1-hour days would not fall on the same day

 AND time2.day <> time3.day

 

That worked, but did not prevent the days from being swapped and creating results that were, logically, the same result. The solution that came to me was to only pull results where the 1st 1-hour day was before the 2nd 1-hour day. That prevents the swapping.

 

At first I was going to create some additional fields so Mon = 1, Tue = 2, etc. and then do a comparison where day1 < day2. But, I realized it really didn't matter which day cam before another - so I just used STRCMP on the day names.

 

So, the logical conclusion is that when creating a query where you need classes on multiple days of different lengths:

 

1. To ensure no two classes fall on the same day, you need to have conditions such as

time1.day <> time2.day

But, for each additional class these conditions need to expand. So, for day three you need two conditions to ensure it doesn't fall on the same day #1 or day #2. For a fourth class day you would need three conditions, etc.

 

2. Additionally, if you have multiple class days of the same length you need to create a condition such that they days are not swapped - which would create a duplicate. For this you would use STRCMP. This is only needed for days of the same length.

 

So, for a 5hour class that you want over 5, 1-hour days I think the query could look like this (not tested)

SELECT time1.day, time1.hour,
   time2.day, time2.hour,
   time3.day, time3.hour,
   time4.day, time4.hour,
   time5.day, time5.hour

FROM timeBlocks AS time1

JOIN timeBlocks AS time2
 ON time2.day <> time1.day
AND STRCMP(time1.day, time2.day) < 0

JOIN timeBlocks AS time3
 ON time3.day <> time1.day
AND time3.day <> time2.day
AND STRCMP(time2.day, time3.day) < 0

JOIN timeBlocks AS time4
 ON time4.day <> time1.day
AND time4.day <> time2.day
AND time4.day <> time3.day
AND STRCMP(time3.day, time4.day) < 0

JOIN timeBlocks AS time5
 ON time5.day <> time1.day
AND time5.day <> time2.day
AND time5.day <> time3.day
AND time5.day <> time4.day
AND STRCMP(time4.day, time5.day) < 0

WHERE time1.length = 1
 AND time2.length = 1
 AND time3.length = 1
 AND time4.length = 1
 AND time5.length = 1

 

EDIT: OK, I've tested it and there are 32 combinations returned.

Edited February 1, 2013 by Psycho

[jenkins]

Psycho you've been a great help. Thanks for taking the time to explain the process/code.

I created a total of 12 deliveries that can be applied to 5 course patterns.

Thanks again.

Have a fabulous day!

[jenkins]

Hi Psycho,

I am requesting your help once again.

I have the following problem:

Currently there is a class on Monday, Tuesday and Thursday from 11:30 to 12:30 each day.

While trying to schedule 5hrs = 1x1hr + 2x2hr (2 + 2 + 1), the analysis previously given does not work because there can be a 2 hour or 1 hour class on either day. So duplicates are displayed.

There should be a total of 6 combinations.

Can you please provide some direction on how to solve this provlem?

Thank you so much!

[jenkins]

Hi Psycho.

I think I solved it.

Thanks again for your help.