difficulty with permutations, please help!

[Loane Sharp]

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

 

[Tom Ogilvy]

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.

 

[Tom Ogilvy]

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