Maths/programming: How can I create a list of combinations of a subset of people?

esuhl

Okay, apologies for the possibly incomprehensible title - it's probably easier if I explain what I'm trying to do:

I'm trying to create a shift rosta generator in Visual Basic 6. For a given day of the week there are a number of shifts (e.g. 8am-4pm, 9am-5pm, etc.). For each shift, a number of people will be required to work out of a pool of available people (there might be 3 people needed to cover the shift, and 6 people who are available to work).

I'd like to be able to list all possible combinations of people, and store this info in an 2D array.

So, for example, if there are six people available to work the shift (numbered 1 to 6), and three people required, I can work out the possible combinations by hand like this:

123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456

...but how could I generate a list of this kind in Visual Basic 6 (or any kind of pseudocode/algorithm), where the number of people available and the number of people required are variables?

Any help, suggestions, or pointers-in-the-right-direction would be REALLY, REALLY, REALLY appreciated!!! :-)

albertross_2

Thinking off the top of my head, it might be easier to do it in binary

so if you have six people, you need a binary number such as

Decimal 44, binary 101100 person 1 on shift, 2 off, 3+4 on, 5 and 6 off.

or 0100110011 for a shift of 5 staff from 10 people.

then all you need is a routine to convert from decimal to binary, which is a divide by 2, check remainder loop, or you could use a convert to string, and substr loop.

http://www.dreamincode.net/code/snippet223.htm

http://www.developerfusion.co.uk/show/3282/

You could have another if statement that ignored any combinations with more than three (or y the number on shift) binary 1's in it.

The number of unique decimal numbers (i.e possible combinations) would be 2^x where x is the number of staff to choose from, so all you would have to store in the array would be sequential decimal numbers to cover the number of combinations, and then strip out or ignore any combinations with more than y staff in it.

Alternatively, you can use decimal, with 0's for not on shift, but the numbers may get a little big, and possibly overflow.

irnbru_2

esuhl wrote: »

Any help, suggestions, or pointers-in-the-right-direction would be REALLY, REALLY, REALLY appreciated!!! :-)

for(k=1;k<7;k++) !!
  for(j=k+1;j<7;j++) !!
    for(i=j+1;i<7;i++) !!
      // do shift stuff
    }
  }
}

!! is actually a closing curly brace.

tr3mor

irnbru wrote: »

for(k=1;k<7;k++) !!
  for(j=k+1;j<7;j++) !!
    for(i=j+1;i<7;i++) !!
      // do shift stuff
    }
  }
}

!! is actually a closing curly brace.

This would give you combinations like 111, 222, etc. Make sure you put some "if not already working this shift" type thing in there.

albertross_2

Wouldn't that solution mean that they would need a for loop for each digit, as the OP doesn't know how many digits are required, it would be difficult to do it programatically, unless some sort of recursion is used.

Sobraon

http://www.xtremevbtalk.com/showthread.php?t=129902 maybe?

irnbru_2

tr3mor wrote: »

This would give you combinations like 111, 222, etc. Make sure you put some "if not already working this shift" type thing in there.

?

k=1
j = k+1
i = j+1

i != j, j != k

irnbru_2

albertross wrote: »

Wouldn't that solution mean that they would need a for loop for each digit

It would - who has more than 3 shift rotas :rolleyes:

irnbru_2

albertross wrote: »

Wouldn't that solution mean that they would need a for loop for each digit, as the OP doesn't know how many digits are required, it would be difficult to do it programatically, unless some sort of recursion is used.

Recursive and non-recursive solutions.

Chippy_Minton

Based on the algorithm at http://home.att.net/~srschmitt/script_combinations.html

    Private Sub combinations(ByVal k As Integer, ByVal n As Integer)

        'Algorithm to generate combinations of k objects from a set of n objects.
        'First combination is: 1 2 3 ... k.

        Dim i, j, a(n - 1) As Integer
        Dim sComb As String

        For i = 0 To k - 1
            a(i) = i + 1
        Next

        Do
            'Output the combination
            sComb = ""
            For i = 0 To k - 1
                sComb += CStr(a(i))
            Next
            Debug.WriteLine(sComb)

            i = k - 1

            While a(i) = n - k + i + 1          'find next item to increment
                i -= 1
                If i < 0 Then Exit Sub 'all done
            End While

            a(i) += 1                           'increment
            For j = i + 1 To k - 1              'reset elements to the right
                a(j) = a(i) + j - i
            Next

        Loop Until i < 0

    End Sub

Call it using:
combinations(3, 6)

esuhl

Wow - thanks so much for everyone's help! Albertross, you're spot on - thinking in binary makes this a *lot* easier.

I've written a function that inputs n (number of people available) and r (number of people required). It loops through each binary permutation with n digits (i.e. from 00000 to 11111 for five people available), each time checking that r number of bits are set. If they are, the number is added to an array.

I'll definitely run through your example this afternoon, Chippy_Minton -
it looks like that would do the job too.

Thanks again everyone!!!