how to solve this allocation problem

[chan_chenyanj]

suppose i have a table with three columns

first one denotes the sequence of items to pick each person allowed to pick (here only two and same seq, the front ones will have higher dollar reward) whenever available, rewards is the dollar amount corresponding the sequence of items to pick and column three is whether they allow to pick

since person 1 can pick item 0 which has 300 as he is allowed to pick. then second person cannot pick item 0 as each item for the amount of reward is unique. so he has to skip 1 and second element is 1 which he is allowed to pick then he picks item 1.

The question is if i have a table and row 1 correspond to first person and so on, how can i output the item number each person pick?

pickSeq: (0;1;2);(0;1;2)

rewards:(300;200;100);(300;200;100)

allowToPick:(true;true;true);(true;true;true)

[davidcrossey · Accepted solution]

If you had the following scenario, you could sort the reward desending, sort the pickSeq ascending and use indices to solve for your problem:

q)n:10
q)people:([]pickSeq:0+til n;person:`$"person",/:string 1+til n;allowedToPick:n?01b)
q)people
pickSeq person   allowedToPick
------------------------------
0       person1  1
1       person2  1
2       person3  1
3       person4  1
4       person5  0
5       person6  0
6       person7  0
7       person8  1
8       person9  0
9       person10 0
q)rewards:([]prize:(1+til 10)*100)
q)rewards
prize
-----
100
200
300
400
500
600
700
800
900
1000
q)(update ind:i from xdesc[`prize;rewards]) lj `ind xkey update ind:i from select person from xasc[`pickSeq;people] where allowedToPick
prize ind person
-----------------
1000  0   person1
900   1   person2
800   2   person3
700   3   person4
600   4   person8
500   5
400   6
300   7
200   8
100   9

 You could also extract the person and their prize as follows:

q){if[1=count x;x:enlist x]; if[1=count y;y:enlist y]; y!x iasc y}[exec desc prize from rewards;] exec person from xasc[`pickSeq;people] where allowedToPick
person1| 1000
person2| 900
person3| 800
person4| 700
person8| 600

[SJT]

q)show people:([]pickSeq:neg[n]?n;person:`$"person",/:string 1+til n;allowedToPick:n?01b)
pickSeq person   allowedToPick
------------------------------
1       person1  0
8       person2  1
5       person3  0
7       person4  1
0       person5  0
3       person6  1
6       person7  0
4       person8  0
2       person9  1
9       person10 0
q)show prize:100*1+til 8
100 200 300 400 500 600 700 800

The winners in order:

q)`pickSeq xasc select from people where allowedToPick
pickSeq person  allowedToPick
-----------------------------
2       person9 1
3       person6 1
7       person4 1
8       person2 1

And their rewards:

q){select person,reward:count[x]#desc prize from x}`pickSeq xasc people where people`allowedToPick
person  reward
--------------
person9 800
person6 700
person4 600
person2 500

Or in vector form:

q){x!count[x]#desc prize}{x iasc y}. flip people[where people`allowedToPick;`person`pickSeq]
person9| 800
person6| 700
person4| 600
person2| 500

Above, where people`allowedToPick finds the winners; and {x iasc y}. sorts the winners’ names by pick order. The vector form has less work to do:

q)\ts:1000 {select person,reward:count[x]#desc prize from x}`pickSeq xasc people where people`allowedToPick
12 3184
q)\ts:1000 {x!count[x]#desc prize}{x iasc y}. flip people[where people`allowedToPick;`person`pickSeq]
3 3312