difficulty with permutations, please help!
 

Hi there

I have a two-dimensional array with 53 "rows" and 11 "columns". The array
values are either "1" or "0", indicating whether a person is working ("1")
or not-working ("0") during each of 11 hourly shifts in a day. The 53 rows
represent different ways in which a person could work. For instance,
concatenating one row of the array yields a string of "01111000000", which
indicates that a person is scheduled to work 4 consecutive hours (ie. the 4
"1"s) from the second hour of the day (ie. the position of the first "1", in
this case 9am). The 53 permutations are not complete: some have been
excluded since they don't represent a realistic work pattern. For example,
the string "01010101010" represents too uneven a pattern of work, while the
string "01000000010" presents too big a stretch between the person's two
shifts.

Two questions arise:

Firstly, how can I use a VBA procedure to generate all possible permutations
for two, three, four and more people? (Am I right to say that the total
number of permutations for n people is 53^n? If so, then the number of
permutations expands rapidly: 53; 2,809; 148,877; 7,890,481; and so on.
Nonetheless I need to write the different permutations out.)

Secondly, how do I generate only the distinct permutations? For instance, in
the case n=2, there are 2,809 (=53^2) permutations but there are only 1,481
(=53+52+51+50+...+1) distinct permutations. If I'm right, to get only the
distinct permutations, I add the values in each "row" of the original array
(ie. case n=1) to each row in the array for case n=k, omitting the case k=n.

Any suggestions would be gratefully appreciated!

Best regards
Loane

difficulty with permutations, please help!
 

If there are 53 feasible work patterns and you want to see how many unique
ways you can pair two of them (two workers), then

=combin(53,2) = 1378
this assumes that they can not work an identical shift. If they can, then
there would be 53 more combinations.

likewise for 3 people

=combin(53,3) = 23,426

4 =combin(53,4) = 292,825

and so forth.

You say you want to generate them, so where do you want to put the output
and in what format?

do you want 1,2 to indicate array item 1 (work pattern 1) paired with array
item 2 (work pattern 2) as an output.

Or do you want 11 cells times 2 rows written to a worksheet.

--
Regards,
Tom Ogilvy


"Loane Sharp" wrote in message
...
Hi there

I have a two-dimensional array with 53 "rows" and 11 "columns". The array
values are either "1" or "0", indicating whether a person is working ("1")
or not-working ("0") during each of 11 hourly shifts in a day. The 53 rows
represent different ways in which a person could work. For instance,
concatenating one row of the array yields a string of "01111000000", which
indicates that a person is scheduled to work 4 consecutive hours (ie. the
4
"1"s) from the second hour of the day (ie. the position of the first "1",
in
this case 9am). The 53 permutations are not complete: some have been
excluded since they don't represent a realistic work pattern. For example,
the string "01010101010" represents too uneven a pattern of work, while
the
string "01000000010" presents too big a stretch between the person's two
shifts.

Two questions arise:

Firstly, how can I use a VBA procedure to generate all possible
permutations
for two, three, four and more people? (Am I right to say that the total
number of permutations for n people is 53^n? If so, then the number of
permutations expands rapidly: 53; 2,809; 148,877; 7,890,481; and so on.
Nonetheless I need to write the different permutations out.)

Secondly, how do I generate only the distinct permutations? For instance,
in
the case n=2, there are 2,809 (=53^2) permutations but there are only
1,481
(=53+52+51+50+...+1) distinct permutations. If I'm right, to get only the
distinct permutations, I add the values in each "row" of the original
array
(ie. case n=1) to each row in the array for case n=k, omitting the case
k=n.

Any suggestions would be gratefully appreciated!

Best regards
Loane

difficulty with permutations, please help!
 

This would be a start. You can continue the pattern (and implement
utilizing additional sheets): [ it does look like it is 53^n for the way
you are doing it].

Sub AA()
'for n = 2
Application.Calculation = xlCalculationManual
a = 54
b = 1
For i = 2 To 54
For j = 2 To 54
a = a + 1
If a 65536 Then
a = 2
b = b + 12
Cells(1, b).Resize(1, 11).Value = _
Cells(1, 1).Resize(1, 11).Value
End If
Cells(a, b) = 2
Cells(a, b + 1).Resize(1, 10).Formula = "=B" & i & "+B" & j
Next j
Next i

' for n = 3
For i = 2 To 54
For j = 2 To 54
For k = 2 To 54
a = a + 1
If a 65536 Then
a = 2
b = b + 12
If b + 10 256 Then GoTo Cleanup
Cells(1, b).Resize(1, 11).Value = _
Cells(1, 1).Resize(1, 11).Value
End If
Cells(a, b) = 3
Cells(a, b + 1).Resize(1, 10).Formula = "=B" & i & _
"+B" & j & "+B" & k
Next k
Next j
Next i

' for n = 4
For i = 2 To 54
For j = 2 To 54
For k = 2 To 54
For l = 2 To 54
a = a + 1
If a 65536 Then
a = 2
b = b + 12
If b + 11 256 Then GoTo Cleanup
Cells(1, b).Resize(1, 11).Value = _
Cells(1, 1).Resize(1, 11).Value
End If
Cells(a, b) = 3
Cells(a, b + 1).Resize(1, 10).Formula = "=B" & i & _
"+B" & j & "+B" & k & "+B" & l
Next l
Next k
Next j
Next i

Cleanup:
Application.Calculation = xlCalculationAutomatic
End Sub


--
Regards,
Tom Ogilvy


"Loane Sharp" wrote in message
...
Hi Tom

Thank you very much for your reply.

You say you want to generate them, so where do you want to put the
output

Am I right in saying that I'm going to run into problems, either way:
ultimately memory problems (if I write many of these permutations to an
array) or more rapidly the 65,536 row limit (if I write the permutations
to
a worksheet)? I'm thinking of storing the values to an array and then,
row-by-row or in batches, transferring them to a SQL Server table using
ADO.
(It took me forever to crack the ADO nut, so I'm keen to get good use out
of
it anyway!) Probably writing the permutations to an array will deliver the
best performance.

and in what format?

I would like the SQL Server table to have 12 columns: the first column
should indicate "n" (1, 2, 3, ... ~ as 53^n) and the 2nd through 12th
columns should indicate the pattern of use in each of the 11 time slots
("t1", "t2", ..., "t11" ~ as "0", "1", "1", ...). I have attached an Excel
spreadsheet to show the format I've been trying to work with (is that
allowed?), hopefully you will receive it. (I used WinRAR for maximum
compression, but if you have problems extracting this I can send a regular
WinZip file).

Best regards
Loane