2

I'm looking for some direction on building an algorithm that will maximize the number of pairwise comparisons of objects in a set using transitivity.

To explain in detail:

Suppose there are x number of objects to be compared. Then there are x[(x-1)/2] possible comparisons of these objects. A constraint is that only subsets of x can be evaluated for comparisons and there is always one most and one least preferred object as defined by a user. These subsets have a constant number of y objects in them.

For example, suppose there are 7 numbered objects (1, 2, 3, 4, 5, 6, 7), 4 objects per subset, which form the matrix below: 

1   4   6   7
2   3   4   6
2   4   5   7
1   2   5   6
1   3   4   5
3   5   6   7
1   2   3   7

Suppose also that a user is randomly given the first row to evaluate by choosing a most desired and least desired object, and has no knowledge of the layout of the above matrix. The first row 1 contains 1, 4, 6, 7 (Note that there are 21 possible pairwise comparisons ) and the user chooses 1 as most preferred and 7 as least preferred. 5 pairwise comparisons are generated (1>4, 1>6, 1>7, 4>7, and 6>7). What would be the next best row to show the user to maximize the number of comparisons by taking advantage of transitivity. Then the next best row to show based on the users most and least preferred choices in the second iteration an so on. The aim is to minimize the number of subsets/rows of the matrix to be shown that will reveal the maximum x[(x-1)/2] possible comparisons.

I envision a second matrix that would keep track of the comparisons by placing a 1 in the off diagonals of the matrix if a object was more desired. For example, if the hypothetical object comparisons for the first subset/row are used (i.e. 1>4, 1>6, 1>7, 4>7, and 6>7):

    1   2   3   4   5   6   7
1   0   0   0   0   0   0   0
2   0   0   0   0   0   0   0
3   0   0   0   0   0   0   0
4   1   0   0   0   0   0   0
5   0   0   0   0   0   0   0
6   1   0   0   0   0   0   0
7   1   0   0   1   0   1   0

The algorithm could use the information in this matrix to choose the next best row/subset to show while taking into account the possible row/subsets in the first matrix.

Update: After further inquiry, I've figured out that solving the for the elements (i.e. the pairwise comparisons) in the diagonals just off the main diagonal in the second matrix would maximize the number of paired comparisons produced from transitivity. This can be done by showing sets of x that have consecutive numbers in them.

Improve this question
6
  • 1
    I don't understand your description. Why do you need such an algorithm? Commented Sep 16, 2015 at 2:24
  • 1
    Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question. Commented Sep 16, 2015 at 4:40
  • I can't understand the "only subsets of x can be evaluated for comparisons" part either. The attempt at an example makes it sound like you're only sorting subsets instead of the entire set, which doesn't require anything special. Commented Sep 16, 2015 at 11:00
  • 1
    Post-edit this now looks perfectly clear and answerable to me. Voting to reopen. Commented Sep 18, 2015 at 22:28
  • @Ixrec are there any steps I can take to get this reopened? Can I re-ask the question? Commented Sep 21, 2015 at 15:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.