Number combination with groups and the smallest repetition possible

Question

I need to create a equation to assign a number of phrases (variable A) to a a defined number of groups (variable B) and repeat these assignment each day, and repeat this operation along of time with the smallest (or most distant) repetition possible.

Some info: the start date is 01/01/1970. The language is PHP, but the question is the mathematical formula.

The big problem is when the phrases number is not a multiple of groups.

Example of results to 5 phrases to 3 groups. (remember that the groups and phrases is a variable)

|date     |G1 |G2 |G3 |
|:-------:|:-:|:-:|:-:|
|22/01/14 | 1 | 2 | 3
|23/01/14 | 4 | 5 | 1
|24/01/14 | 2 | 3 | 4
|25/01/14 | 5 | 1 | 2
|26/01/14 | 3 | 4 | 5
|27/01/14 | 1 | 2 | 3
|28/01/14 | 4 | 5 | 1
|29/01/14 | 2 | 3 | 4
|30/01/14 | 5 | 1 | 2
|31/01/14 | 3 | 4 | 5

Example of results to 8 phrases to 3 groups.

|date     |G1 |G2 |G3 |
|:-------:|:-:|:-:|:-:|
|22/01/14 | 1 | 2 | 3
|23/01/14 | 4 | 5 | 6
|24/01/14 | 7 | 8 | 1
|25/01/14 | 2 | 3 | 4
|26/01/14 | 5 | 6 | 7
|27/01/14 | 8 | 1 | 2
|28/01/14 | 3 | 4 | 5
|29/01/14 | 6 | 7 | 8
|30/01/14 | 1 | 2 | 3
|31/01/14 | 4 | 5 | 6
|01/02/14 | 7 | 8 | 1
|02/02/14 | 2 | 3 | 4
|03/02/14 | 5 | 6 | 7
|04/02/14 | 8 | 1 | 2
|05/02/14 | 3 | 4 | 5
|06/02/14 | 6 | 7 | 8

Example of results to 6 phrases to 2 groups.

|date     |G1 |G2 |
|:-------:|:-:|:-:|
|22/01/14 | 1 | 2
|23/01/14 | 3 | 4
|24/01/14 | 5 | 6
|22/01/14 | 2 | 3
|23/01/14 | 4 | 5
|24/01/14 | 6 | 1

Example of results to 5 phrases to 2 groups.

|date     |G1 |G2 |
|:-------:|:-:|:-:|
|22/01/14 | 1 | 2
|23/01/14 | 3 | 4
|24/01/14 | 5 | 1
|22/01/14 | 2 | 3
|23/01/14 | 4 | 5
|24/01/14 | 1 | 2
|25/01/14 | 3 | 4
|26/01/14 | 5 | 1
|27/01/14 | 2 | 3
|28/01/14 | 4 | 5

Answer 1

You need to define what you mean by repetition. If you mean reuse of a phrase between groups, you are doing fine. If there are $p$ phrases and $g$ groups, each phrase comes back on average after $\frac pg-1$ cycles. Note that your assignments repeat every $g$ days. Is that acceptable? It gets harder if (in the first example) you don't want to repeat all three assignments on $27/01/14$ There are a total of $60$ assignments in this case and you only run through $5$ of them.

If you want a formula for which phrase a group gets on a given day, let us count the first day as day zero. Then on day $d$ group 1 gets phrase $gd+1 \pmod p$ and group $n$ gets phrase $gd+n \pmod p$

Seeing the update to $p=6, g=2$ and assuming the next day starts with $3$, you can do this. If $g$ divides evenly into $p$ you have a bump every $\frac pg$ days so the relation will be that group $n$ gets phrase $gd + n + \lfloor \frac {ng}p \rfloor \pmod p$

Answer 2

Be aware that your example with $6$ phrase and $2$ groups do exact that. (But I see what you want to avoid)

Also, I know that you mentioned that both $A$ and $B$ are variables, but you didn't mention if you can access/modify this parameter before or during the use of the function (pointers for example).

Because of that, I will try both alternatives.

My first suggestion (and the easiest solution) to work around the problem would be to decline multiple (or to convert them into non multiples)

You could do this by adding some kind of control outside the function like:

IF (numphrases%numgroups == 0)

    numphrases +=;

Or

IF (numphrases%numgroups == 0 AND numgroups > 1)

    numgroups -=;

However, since I don't know much about the project, it is possible that you don't have this option.

In this case, there is a problem with this "shift" in circular permutations that will repeat every $k \equiv 1 \; \textrm{mod} \; \frac{p}{g}$ by $k$ meaning the position.

Examples:

               2 groups 4 phrases                 3 groups 9 phrases

Position 1            1   2                             1  2  3

Position 2            3   4                             4  5  6

Position 3            4   1 <-Need shift (p/g+1)        7  8  9

Position 4            2   3                             8  9  1 <-Shift (p/g+1)

Position 5            ?   ? <-Need shift (p/g+1)        2  3  4

Position 6            ?   ?                             5  6  7

Position 7            ?   ?                             ?  ?  ? <-Shift (p/g+1)

It doesn't matter if the "shift" is done forward or backward.

However, the maximum number of "shift's" allowed before we repeat the circle is $g-1$ and the number of "shift's" done at a given position $k$ will be the integer result of $\frac{\textrm{days passed}}{\textrm{numgroups}}$.

Since every $g-1$ the circle repeat, we can define the "shift's" as $s_{1}, s_{2}, \dots, s_{g-1}$ where $s_{i}$ means we shifted the circle by $i$ positions.

In this case, without knowing nothing about the range of possible values of $A$ and $B$, my suggestion (that need to be tested) is:

int RETURNPHRASE(day, numberofgroups, group, numphrases)

    int numshifts, dayspassed;

    numshifts = 0;

    dayspassed = day - STARTDAY;

    /* Need to implement a GCD function that returns the Greatest common

    *  divisor between two numbers */

    if((numphrases%numberofgroups !=0) && (GCD(numphrases,numgroups) !=0))
    {   
        I = day - startday #number of days that had passed

        F = (I * numberofgroups)%numphrases

        return (F+group-1)%numphrases
    }

    if(GCD(numphrases,numgroups) !=0)

    {

        numshifts = dayspassed / numgroups;

        numshifts %= (numgroups - 1);

        F = ((I * numberofgroups)%numphrases)+numshifts)%numphases

        return (F+group-1)%numphrases

    }

    /* Need to implement a lcm (Least common multiple) also */

    numshifts = dayspassed / (LCM(numgroups,numphrases)/numgroups

    numshifts %= (numgroups - 1)

    F = ((I * numberofgroups)%numphrases)+numshifts)%numphases

    return (F+group-1)%numphrases

I think that will handle the shifts. However, if you could give more details about the range of possible values of $A$ and $B$ maybe there is a better solution.

I adjusted the function to get the problems you mentioned. (Unfortunately couldn't look the adjusts you made yet)

However, you will need a gcd and lcm functions in the code which I only called without concerns about the implementation.

Answer 3

I will assume that the phrases are not allowed to repeat itself in the same day. (Ex. |22/01/14 | 1 | 1 | 1 is not possible).

Also, I will assume that you can establish a relation between the variable $A$ and the first $n$ phrases.

So, let $g_{i}$ be the result of $i$th group in a given day, $p$ the number of phrases and $n$ the number of groups.

The minimum value for $\sum_{i=1}^{n} g_{i}=\dfrac{(n+1) \cdot n}{2}$ where $n$ is the number of groups.

On the other hand, the maximum value for $\sum_{i=r-n+1}^{r} g_{i}=\dfrac{(2r-n+1) \cdot n}{2}$

To use your first example, considering that repetition are not allowed, the minimum value of $g_{1}+g_{2}+g_{3}=1+2+3=6$ and the maximum value are $g_{1}+g_{2}+g_{3}=3+4+5=12$.

With that in mind, you can use recursion to make the following:

I) Permute all the possible non-negative values of the diophantine equation: $$ g_{1}+g_{2}+\dots +g_{g}=k $$

Where $k = \dfrac{(n+1) \cdot n}{2}$.

That will give you with $\dbinom{k-1}{g-1}$ minus the values where we possible had repeated values.

In the example:

|22/01/14 | 1 | 2 | 3

|23/01/14 | 1 | 3 | 2

|24/01/14 | 2 | 1 | 3

|25/01/14 | 2 | 3 | 1

|26/01/14 | 3 | 1 | 2

|27/01/14 | 3 | 2 | 1

Note that by the formula you had $\dbinom{5}{2}=10$ and we only got $6$ because we had to remove $\left\{ (2,2,2);(1,1,4);(1,4,1);(4,1,1) \right\}$

II) Increment $k$ by 1 and repeat the process.

III) Do that while $k \leq \dfrac{(2r-n+1) \cdot n}{2}$

Following this algorithm you will be able to get all possible values without repeat.

However, for (I) you will had to implement a function that find the possible results of a diophantine equation.

Edit:

Since you just want to reproduce your example, note that what are you doing is a circular permutation. Let $P(\textrm{days passed})$ denote the first element that start your sequence.

Suppose that you had $g$ groups and $p$ phrases. Then, let 01/01/1970 be defined as day $1$:

$$ \begin{matrix} P(1) = 1; \\ P(2) = P(1) + g \; \textrm{mod} \; p = g+1 \; \textrm{mod} \; p;\\ P(3) = P(2) + g \; \textrm{mod} \; p = 2g+1 \; \textrm{mod} \; p;\\ \vdots \\ P(n) = (n-1)g+1 \; \textrm{mod} \; p \end{matrix} $$

So, in order to get the phrase number in the sequence you had to do:

int RETURNPHRASE(day, numberofgroups, group, numphrases)

I = day - startday #number of days that had passed

F = (I * numberofgroups)%numphrases

return (F+group-1)%numphrases

From F you can get any $g_{i}$ since it is the first one in the sequence.

You need to adjust the algorithm for PHP but I think the main idea is there.