# Assignement of positions

This topic is 2140 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everybody

I am facing a problem implementing an "algorithm"

I have a list of priority queue (each letter can appear only once per queue, 3 times in total. The priority can be 1, 2 or 3, nothing else), like

First|  1:{X,V,Y} 2:{U}     3:{W}

Second| 1:{Z,U}   2:{V}     3:{}

Third|  1: {}     2:{X}     3:{V}

Fourth| 1:{}      2:{Y,W,Z} 3:{X}

Fifth|  1:{W}     2: {}     3:{U,Y}

Each queue represent a preference toward a position (for example, X has as first preference First, as second preference Third and as third preference Fourth)

But there are some constraints:

• To each letter can be assigned only one position
• To each position can be assigned no more than N letters (N is an argument of the function). If less then N letters have a preference for that position, all the letters get placed in that position or a higher preferred one.
• If in a queue for a position a letter A have an higher priority of a letter B, and B is assigned to that position, then A is assigned to that position too or in a position where A have an higher preference (example: if X is assigned to Fourth, then Y,W,Z are assigned to Fourth too OR  Y,W,Z are placed in a position where they have an higher preference than 2)

Two possible solutions are (with 5 position, the preferences listed as above, and 2 places for each position)

First: [X(1), U(2)]
Second: [Z(1), V(2)]
Third: []
Fourth: [Y(2)]
Fifth: [W(1)]


or

First: [X(1), V(1)]
Second: [Z(1), U(1)]
Third: []
Fourth: [Y(2)]
Fifth: [W(1)]

Between the parenthesis there is which preference have been used to pick that letter

While a wrong one is

First: [X(1), U(2)]
Second: [Z(1), V(2)]
Third: []
Fourth: [Y(2),W(2)]
Fifth: []

because W would like to be placed Fifth, but even if there is space it is placed in a position less preferable.
Note: it is possible that a letter can not be assigned (for example if X, Y, and Z have as only preference First, only 2 can be assigned there.)
I am not sure how to write this algorithm..

Do you have some hints? When I try doing it by hands i end up making lots of comparisons, but i fear cyclic dependency if i implement it like that..

Edited by Makers_F

• 21
• 12
• 9
• 17
• 13