1

Topic: To arrange players on commands

Is N players. It is necessary to arrange them on M commands, on K to the player in each command (for convenience, N shares on M without residual, i.e. M*K = N) For each player its level which is defined by number (we tell, from 0 to 1000) is known. Command level is defined as the total of levels of players of it. The task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier.

2

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> Is N players. It is necessary to arrange them on M commands, on K to the player in each command (for convenience, N shares on M without residual, i.e. M*K = N) RNS> For each player its level which is defined by number (we tell, from 0 to 1000) is known. Command level is defined as the total of levels of players of it. RNS> the task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier. If the most optimal decision - that the full search of variants, differently - different "greedy" algorithms is necessary. Like so.

3

Re: To arrange players on commands

Hello, Qulac, you wrote: Q> If the most optimal decision - that the full search of variants is necessary, Search does not quit, there factorial complexity. Number of possible allocations - N! / (M! * K!) . If at us 100 persons and 10 commands, search does not turn out any more. Q> differently - different "greedy" algorithms. Like so. What? I think, here not so much greedy  it is better, how many iterated optimization (to take a casual variant, and it is iterated it to refine, yet do not rest against a local minimum). Then it is possible to take other casual start configuration, and to repeat process, finding new local minima. Then as result to take the least local minimum. If process we will repeat infinitely  we find a global minimum, but we can stop process at any moment and use the result known at that point in time. A question then that we should do during each iteration that  to go to a local minimum (i.e. to reduce the maximum distance from  values).

4

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> Hello, Qulac, you wrote: Q>> If the most optimal decision - that the full search of variants is necessary, RNS> Search does not quit, there factorial complexity. Number of possible allocations - N! / (M! * K!) . If at us 100 persons and 10 commands, search does not turn out any more. It we in course. Q>> differently - different "greedy" algorithms. Like so. RNS> What? I think, here not so much greedy  it is better, how many iterated optimization (to take a casual variant, and it is iterated it to refine, yet do not rest against a local minimum). Then it is possible to take other casual start configuration, and to repeat process, finding new local minima. Then as result to take the least local minimum. If process we will repeat infinitely  we find a global minimum, but we can stop process at any moment and use the result known at that point in time. RNS> a question then that we should do during each iteration that  to go to a local minimum (i.e. to reduce the maximum distance from  values). Here the decision of the similar task on stones different methods: https://petrsu.ru/files/document/uploads/algol.pdf

5

Re: To arrange players on commands

Hello, Qulac, you wrote: RNS>> What? I think, here not so much greedy  it is better, how many iterated optimization (to take a casual variant, and it is iterated it to refine, yet do not rest against a local minimum). Then it is possible to take other casual start configuration, and to repeat process, finding new local minima. Then as result to take the least local minimum. If process we will repeat infinitely  we find a global minimum, but we can stop process at any moment and use the result known at that point in time. RNS>> a question then that we should do during each iteration that  to go to a local minimum (i.e. to reduce the maximum distance from  values). Q> Here the decision of the similar task on stones different methods: https://petrsu.ru/files/document/uploads/algol.pdf There search test all  changeovers and check, whether they refine the decision. In our case it is possible even is easier - since We try to reduce a difference for a command which is as much as possible remote from mean value, we should consider only changeovers with involvement of players from this command. Search K * (N-K), with check turns out, whether the maximum distance from mean value decreases. Whether it is possible to accelerate this iteration? That was at all O (K^2), and O (K)?

6

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> In our case it is possible even is easier - since we try to reduce a difference for a command which is as much as possible remote from mean value, we should consider only changeovers with involvement of players from this command. Search K * (N-K), with check turns out, whether the maximum distance from mean value decreases. Whether it is possible to accelerate this iteration? That was at all O (K^2), and O (K)? It does not give the optimal decision, only the quasioptimal.

7

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> the Task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier. Well you know, to that this "middle tier" is equal. Here also adjust to it.

8

Re: To arrange players on commands

Hello, gandjustas, you wrote: G> Hello, RiNSpy, you wrote: RNS>> In our case it is possible even is easier - since we try to reduce a difference for a command which is as much as possible remote from mean value, we should consider only changeovers with involvement of players from this command. Search K * (N-K), with check turns out, whether the maximum distance from mean value decreases. Whether it is possible to accelerate this iteration? That was at all O (K^2), and O (K)? G> It does not give the optimal decision, only the quasioptimal. In sense? Yes, we will stick in local minima but if to begin from various casual configurations we should, at an amount of attempts aspiring to infinity, to find the optimal decision. In practice, should come nearer to it quickly enough. But a main point - how to lead iterations that they were O (K)?

9

Re: To arrange players on commands

Hello, RiNSpy, you wrote: G>> It does not give the optimal decision, only the quasioptimal. RNS> in sense? Yes, we will stick in local minima but if to begin from various casual configurations we should, at an amount of attempts aspiring to infinity, to find the optimal decision. In practice, should come nearer to it quickly enough. An amount of the attempts aspiring to infinity do not guarantee an optimality. But the set of decisions countable, therefore at enough of attempts we is simple all variants we sort out.

10

Re: To arrange players on commands

Hello, gandjustas, you wrote: G> the Amount of the attempts aspiring to infinity do not guarantee an optimality. G> but the set of decisions countable, therefore at enough of attempts we is simple all variants we sort out. Well that is means all the same guarantees? In practice, I think we should come to the optimal decision much earlier, and to good enough decision - absolutely quickly. But depends on the initial data.

11

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> Is N players. It is necessary to arrange them on M commands, on K to the player in each command (for convenience, N shares on M without residual, i.e. M*K = N) RNS> For each player its level which is defined by number (we tell, from 0 to 1000) is known. Command level is defined as the total of levels of players of it. RNS> the task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier. Generally, search here works. Sharing of 100 persons at 10 commands becomes very quickly. Complexities begin on 3-5. Well and if to take a reality, instead of the abstract tasks there begin  different game nuances.

12

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> Is N players. It is necessary to arrange them on M commands, on K to the player in each command (for convenience, N shares on M without residual, i.e. M*K = N) RNS> For each player its level which is defined by number (we tell, from 0 to 1000) is known. Command level is defined as the total of levels of players of it. RNS> the task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier. We sort players by level decrease. Further, we take the first M players (i.e. with the greatest level) and it is assigned them in commands from 1 to M. On . Iterations we take following M of players and it is assigned them in commands already from M to 1. On . Iterations again from 1 to M. I.e. a command on before. Iterations getting the player with the least level, on leaked. Level receives the player with the greatest. Somehow so...

13

Re: To arrange players on commands

Hello, Sharov, you wrote: S> we Sort players by level decrease. Further, we take the first M players (i.e. with the greatest level) and it is assigned them in commands from 1 to M. On . Iterations we take following M of players and it is assigned them in commands already from M to 1. On . Iterations again from 1 to M. I.e. a command on before. Iterations getting the player with the least level, on leaked. Level receives the player with the greatest. And after that  conjugate swaps.

14

Re: To arrange players on commands

Hello, Kernighan, you wrote: K> Hello, Sharov, you wrote: S>> we Sort players by level decrease. Further, we take the first M players (i.e. with the greatest level) and it is assigned them in commands from 1 to M. On . Iterations we take following M of players and it is assigned them in commands already from M to 1. On . Iterations again from 1 to M. I.e. a command on before. Iterations getting the player with the least level, on leaked. Level receives the player with the greatest. K> and after that  conjugate swaps. What for?

15

Re: To arrange players on commands

Hello, Kernighan, you wrote: K> Hello, Sharov, you wrote: S>> we Sort players by level decrease. Further, we take the first M players (i.e. with the greatest level) and it is assigned them in commands from 1 to M. On . Iterations we take following M of players and it is assigned them in commands already from M to 1. On . Iterations again from 1 to M. I.e. a command on before. Iterations getting the player with the least level, on leaked. Level receives the player with the greatest. K> and after that  conjugate swaps. Whether it is possible to find necessary conjugate swap for result improving, without search of all possible swaps? I.e. during O (K)? It is possible to consider that players in commands are already sorted by decrease.

16

Re: To arrange players on commands

Hello, Sharov, you wrote: S> Hello, Kernighan, you wrote: K>> Hello, Sharov, you wrote: S>>> we Sort players by level decrease... K>> And after that  conjugate swaps. S> what for? When we sort players by decrease, in some places big "steps" turn out. To smooth these steps at the second-third pass happens it is necessary to take not following player from the list, and the player far away.

17

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> Hello, Kernighan, you wrote: K>> Hello, Sharov, you wrote: S>>> we Sort players by level decrease. Further, we take the first M players (i.e. with the greatest level) and it is assigned them in commands from 1 to M. On . Iterations we take following M of players and it is assigned them in commands already from M to 1. On . Iterations again from 1 to M. I.e. a command on before. Iterations getting the player with the least level, on leaked. Level receives the player with the greatest. K>> and after that  conjugate swaps. Whether RNS> it is possible to find necessary conjugate swap for result improving, without search of all possible swaps? I.e. during O (K)? It is possible to consider that players in commands are already sorted by decrease. For the given pair of commands, obviously, it is possible to find the best swap of pair players for O (K ln (K)). However, for it is required search of all pairs commands O ((M/K) ^2 K ln (K)) =O (M^2 ln (K)/K) that is better than O (M^2) (the full search of pairs players), but not on many. For K=10, possibly, it is not necessary to be wrapped. If to begin with pair of commands, for which the probability to find swap is maximum, (the best + the worst commands), and to be restricted first found swap on average time will be even less. Considering that the minimum but only "good enough decision", sometimes a leveling cycle stop if refining swaps are not present among between the best and worst commands more is necessary not.

18

Re: To arrange players on commands

Hello, Chorkov, you wrote: K>>> And after that  conjugate swaps. Whether RNS>> it is possible to find necessary conjugate swap for result improving, without search of all possible swaps? I.e. during O (K)? It is possible to consider that players in commands are already sorted by decrease. A C> For the given pair of commands, obviously, it is possible to find the best swap of pair players for O (K ln (K)). And why O (K ln (K))? It is the most interesting part. The C> However, for search of all pairs commands is required O ((M/K) ^2 K ln (K)) =O (M^2 ln (K)/K) that is better than O (M^2) (the full search of pairs players), but not on many. For K=10, possibly, it is not necessary to be wrapped. A C> If to begin with pair of commands, for which the probability to find swap is maximum, (the best + the worst commands) and to be restricted to the first found swap on average time will be even less. C> Considering that the minimum but only "good enough decision", sometimes a leveling cycle stop if refining swaps are not present among between the best and worst commands more is necessary not. And in remaining yes, it  the right answer / the best.

19

Re: To arrange players on commands

Hello, Kernighan, you wrote: K> Hello, Sharov, you wrote: S>> Hello, Kernighan, you wrote: K>>> Hello, Sharov, you wrote: S>>>> we Sort players by level decrease... K>>> And after that  conjugate swaps. S>> what for? K> When we sort players by decrease, in some places big "steps" turn out. K> to smooth these steps at the second-third pass happens it is necessary to take not following player from the list, and the player far away. Well here in the the decision above I took the players sorted by a rating and arranged on commands from 1 to M, in . Iterations on the contrary from M to 1, it is literally. I so understood that for more effective allocation, a command before allocation of players it is necessary to sort by already received points. It is correct?

20

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> And why O (K ln (K))? It is the most interesting part. Let S1, S2 - the totals for the first and second group. Let S1> S2, (to consider it is twice less than cases). Then for reduction of entropy we need to find such pair a_i, a_j to minimize f (i, j) = | (S1-a_i+a_j) - (S2-a_j+a_i) | on set of pairs i, j from the given groups. We designate D (i, j) =a_i-a_j, then: f (i, j) = | (S1-S2) - 2 D (i, j) | I.e. an optimal difference between elements D = (S1-S2)/2 (it equilibrates groups), but will suit us 0 <D <(S1-S2) I.e. having set a_i, we will have restriction on a_j: a_i <a_j <a_i + (S1-S2). Optimal value a_j_opt = a_i + (S1-S2)/2. Algorithm: 1) for a cycle on all a_i (from the first group) O (K) {2) segment Division in halves we search minimum a_j, such that a_j> = a_i + (S1-S2)/2 (we designate it as a_j_u) complexity O (ln (K)) 3) we take the previous element, we designate as a_j_l, it will be maximum an element, such that a_j <a_i + (S1-S2)/2 complexity O (1 4) we look what of elements better (a_j_l or a_j_u), and whether it satisfies to a condition. Complexity O (1)}

21

Re: To arrange players on commands

Hello, Chorkov, you wrote: a C> Hello, RiNSpy, you wrote: RNS>> And why O (K ln (K))? It is the most interesting part. A C> [...] it is excellent! , it is the right answer (together with your previous post).

22

Re: To arrange players on commands

Hello, RiNSpy, you wrote: RNS> the Task - to arrange players on commands so that all commands were as more as possible identical. I.e. it is necessary to minimize the maximum deviation from middle tier. 1) a part after " ." It is a part of a statement of the problem? Then what for what was to? 2) If it any more the condition, and your interpretation a condition "are as more as possible identical" can to express on a miscellaneous. For example as the total of squares of deviations. If the metrics "the maximum deviation" a part of a statement of the problem it seems to me that it is possible to build commands in process of them  for alignment. But it is any artificial enough approach. The general method here, IMHO to apply something like differential evolution. All question how to produce transposition. At DYE for transposition we take 3 individuals: A, B, a C, we calculate a difference In and With, somehow it casually we scale, and we apply to And. In this case it is possible to arrive, for example, so. On In and With we define what set of players it is yet precisely anchored to commands, and we try them to rearrange casually somehow, with saving  commands further. Can be will better if we take only such swaps which refine the outsider.