# comp sci ranking question. which group is most selective?

Page 1 of 1

## 11 Replies - 1685 Views - Last Post: 12 March 2012 - 01:11 AM

### #1 romil797

Reputation: 2
• Posts: 50
• Joined: 24-April 11

# comp sci ranking question. which group is most selective?

Posted 03 March 2012 - 05:41 PM

This is not homework; this is for part of a project I thought of starting... will not give details.
There are four groups ( sort of like jobs or colleges ): A, B, C, and D. In the project, there will be many more, but for now let's assume four. People can apply to any number those groups, and the groups can reject or admit them. Person 1 got in to A, B, C, D. Person 2 got into A, B, C, but not D. Person 3 got into A, B, but not C, D. Person 4 got into A, but not B, C, D, E. Obviously, A is least selective, followed by B, C, and lastly D. How does a computer figure this out when there are any number of groups, and any number of people who applied to any number of groups?

Is This A Good Question/Topic? 0

## Replies To: comp sci ranking question. which group is most selective?

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12305
• Posts: 45,401
• Joined: 27-December 08

## Re: comp sci ranking question. which group is most selective?

Posted 03 March 2012 - 06:31 PM

An easy way to do this is to look at the ratio of accepted/totalApplied. The higher the percentage, the lower the exclusivity.

### #3 romil797

Reputation: 2
• Posts: 50
• Joined: 24-April 11

## Re: comp sci ranking question. which group is most selective?

Posted 08 March 2012 - 05:22 PM

macosxnerd101, on 03 March 2012 - 06:31 PM, said:

An easy way to do this is to look at the ratio of accepted/totalApplied. The higher the percentage, the lower the exclusivity.

But I don't want a percentage. I want it relative to the other groups.

### #4 jon.kiparsky

• Beginner

Reputation: 11041
• Posts: 18,857
• Joined: 19-March 11

## Re: comp sci ranking question. which group is most selective?

Posted 09 March 2012 - 09:55 AM

One of the features of numbers is that they have a natural sort order. Percentages are numbers.

You could probably do this a few ways, but the ones that come to mind seem like transparent proxies for comparing percentages in this way.

You could probably do some set theory stuff if you wanted - is that the sort of thing you're looking for?

### #5 romil797

Reputation: 2
• Posts: 50
• Joined: 24-April 11

## Re: comp sci ranking question. which group is most selective?

Posted 09 March 2012 - 05:56 PM

set theory would work just fine!
percentages aren't relative.
do you have an algorithm you could share for the set theory idea? or any pointers? or anything at all?

### #6 GetSet

• D.I.C Regular

Reputation: 44
• Posts: 411
• Joined: 08-February 11

## Re: comp sci ranking question. which group is most selective?

Posted 09 March 2012 - 07:27 PM

romil797, on 09 March 2012 - 05:56 PM, said:

This is not homework; this is for part of a project I thought of starting... will not give details.

(It sure does sound like homework. Discrete mathematics class, extra credit?)

After gathering all the input, solve each permutation in turn but in nested fashion, so that each successive solution limits the next.

This post has been edited by GetSet: 09 March 2012 - 07:32 PM

### #7 jon.kiparsky

• Beginner

Reputation: 11041
• Posts: 18,857
• Joined: 19-March 11

## Re: comp sci ranking question. which group is most selective?

Posted 09 March 2012 - 08:26 PM

romil797, on 09 March 2012 - 07:56 PM, said:

set theory would work just fine!
percentages aren't relative.

They're not? I'd like to hear a little more about what you're looking for, then. I would have thought that the whole point of percentages was to normalize ratios so they could be easily related to each other. I might not be understanding you correctly, though.

Quote

do you have an algorithm you could share for the set theory idea? or any pointers? or anything at all?

No, no ideas as yet, not concrete ones anyway. In a sense, I think you're going to have to work out your definitions in mathematical terms, and set theory might be one language for doing that, but there may be others. At the moment, I'm not really sure I know what you mean by "more exclusive". Suppose there are candidates A..Z for membership into groups 1, 2, 3, and 4. Must we suppose that all candidates are candidates for all groups in order to make this work? Or can we have A..F contending for group 1, G..L for group 2, and so forth. If there is no overlap, can we still compare exclusivity? Suppose then that there's a partial overlap, A..G vying for group 1, E..M for group 2, etc. Can we compare, and if so on what basis? Then suppose that there's an uneven partial overlap, where I no longer carefully distribute candidates evenly among the groups. This case seems to steer us perilously close to the percentages, or else you have to establish a complementary notion of "desirability" of a group.

Then, we might want to wonder about the candidates for a moment? Do we want to consider the "promiscuity" of candidates? Does it matter how many groups a candidate goes out for? How about their "eligibility"? Does it matter how many groups accept a given candidate?

All of this goes to the question: what is it you're trying to learn here? What is it you're trying to capture with your notion of "exclusivity"? And more particularly, what is it about that notion that isn't correctly captured by a simple calculation of the ratio of applications to acceptances? Surely a naive intuition would suggest that a group which accepts 90% of its applicants is less exclusive than a group which accepts 10%. This disregards many factors. What of those factors are the interesting ones for you?

### #8 GetSet

• D.I.C Regular

Reputation: 44
• Posts: 411
• Joined: 08-February 11

## Re: comp sci ranking question. which group is most selective?

Posted 09 March 2012 - 08:49 PM

jon.kiparsky, on 09 March 2012 - 08:26 PM, said:

In a sense, I think you're going to have to work out your definitions in mathematical terms, and set theory might be one language for doing that, but there may be others.

The OP is referring to r-permutations. I suppose it could be done through r-combinations as well, just more work.

In a sense he's also combining mathematical induction into the mix as well, through "there are any number of groups, and any number of people who applied to any number of group" though the program need not deal with induction because it would have to work with a finite set (the finite input to be processed).

This post has been edited by GetSet: 09 March 2012 - 08:49 PM

### #9 romil797

Reputation: 2
• Posts: 50
• Joined: 24-April 11

## Re: comp sci ranking question. which group is most selective?

Posted 11 March 2012 - 11:37 AM

if there is no overlap, we cannot compare exclusivity. it doesnt mattter how many groups accept a given candidate, more of which groups. the factors it disregards are irrelevant because i don't want to use a percentage.
i understand permutations and combinations, but am completely confused.
Help! You guys are losing me.

### #10 jon.kiparsky

• Beginner

Reputation: 11041
• Posts: 18,857
• Joined: 19-March 11

## Re: comp sci ranking question. which group is most selective?

Posted 11 March 2012 - 07:36 PM

Quote

the factors it disregards are irrelevant because i don't want to use a percentage.

If you don't want to use a percentage, it's because there is some factor in the problem which is elided by the use of a percentage. What is it that you're trying to keep hold of?

Okay, so if a, b, c, and d apply to group 1 and all are accepted, and e..z apply to group 2 and exactly 1 is accepted, we can't compare?

But if a, b, c, and d apply to group 1 and a..z apply to group 2, selectivity is determined by comparing the acceptance of the common applicants a..d?

If so, then you can take the intersection of the applicant pools, call that set CA (common applicants) then rank group G's acceptiness by counting the members of the intersection of G's applicants with set CA. Selectivity is the other end of the scale from acceptiness: a selectivity of 0 is, I guess, perfectly selective. So group 2 is more selective than group 1 iff it accepts fewer members of the set {a, b, c, d} than group 1 does. It doesn't matter how many it accepts from {e..z}, since they didn't apply to group 1.

Notice that this means that if group G accepts only applicants which apply to G exclusively, and rejects applicants who apply to any other group, then G can score perfectly selective and still admit as many students as apply under that condition. That is, they need no criteria other than "Applicant applied exclusively to G". So it's not a very strict criterion by any means, but maybe it suits your purposes.

### #11 romil797

Reputation: 2
• Posts: 50
• Joined: 24-April 11

## Re: comp sci ranking question. which group is most selective?

Posted 11 March 2012 - 08:38 PM

yes, in that scenario we cant compare.
yes, that would be how selectivity is determined.
oh my god! thank you; you are sooooo helpful. i understand now. ( not comp-sci related, but where can i store the data of which groups were applied to by which applicant and where they got in??????????? )
but say it is determined with this algo that, with groups A, B, and C:
A > B
A > C
B < C.
how do i sort the final output????

### #12 jon.kiparsky

• Beginner

Reputation: 11041
• Posts: 18,857
• Joined: 19-March 11

## Re: comp sci ranking question. which group is most selective?

Posted 12 March 2012 - 01:11 AM

You've got a numeric score, so that shouldn't be hard to sort.

As for storing the data of the groups, I guess it depends on what paradigm you're working in. It seems like a natural in an OO language - Groups and Applicants are objects, Groups have applicantPools and acceptedApplicants, which are sets of Applicants. Existing implementations of Set in java will have useful methods (retainAll(), for example) so you have a lot of the work done for you if you choose java, but sets aren't conceptually difficult to program, so you shouldn't find it very hard in any language. I really think you can do a lot of the figuring out if you put your mind to it.