0
$\begingroup$

Given the options of:

  • Red
  • Orange
  • Yellow
  • Green
  • Blue
  • Violet

You want to find your favorite color by comparing all pairs to each other, like so: Red vs...

  • Red vs Orange = Orange
  • Red vs Yellow = Red
  • Red vs Green = Red
  • Red vs Blue = Red
  • Red vs Violet = Red

Orange vs...

  • Orange vs Yellow = Orange
  • Orange vs Green = Orange
  • Orange vs Blue = Orange
  • Orange vs Violet = Orange

Yellow vs...

  • Yellow vs Green = Green
  • Yellow vs Blue = Yellow
  • Yellow vs Violet = Yellow

Green vs...

  • Green vs Blue = Green
  • Green vs Violet = Green

Blue vs...

  • Blue vs Violet = Violet

In the end you'll find your "most preferred". Not sure if you get a full order of preference.

What's the name of this...thing?

Also as D.W. described, I believe it's solved by which color won most often. So in the example above:

  • Orange = 5
  • Red = 4
  • Green = 3
  • Yellow = 2
  • Violet = 1
  • Blue = 0
$\endgroup$
3
  • $\begingroup$ (Where's the procedure, the well-defined steps that define an abstract solution, the algorithm?) $\endgroup$ – greybeard Dec 4 '20 at 8:28
  • $\begingroup$ I don't know the "well-defined steps"; that's why I'm trying to find the name of this thing. $\endgroup$ – Byran Zaugg Dec 5 '20 at 0:50
  • 1
    $\begingroup$ What you present is a relation, looks a partial order. Per title and tag, you refer to an algorithm using a definite article - I still miss any trace of it. A partial order may be "simple/total", but, e.g., not if represented as a graph, there is more than one node with an in-degree of zero; same for out-degree. It still may be embeddable in a total order. $\endgroup$ – greybeard Dec 5 '20 at 6:22
1
$\begingroup$

If we can assume that there is a total order on all colors: to find the largest element, there is a straightforward $O(n)$-time algorithm to find it: you scan through all colors, keep tracking of the largest element seen so far:

  • Set $m$ to the first color.
  • For each other color $c$:
    • Set $m := \max(m,c)$.

(Here $\max$ refers to the larger of the two colors, i.e., whichever is more preferred.) There is no need to "sort" all of the colors to find the largest (most favorite) color.

Alternative, suppose we cannot assume the colors are totally ordered, and the order is a partial order. Then you'd need to specify what is meant by "most favorite" color. One possible definition is a maximal color, i.e., one where no other color is more preferred. (Note that there may be multiple such colors.) If so, you can again find it via the same linear scan (if two elements are incomparable, you stick with the current element).

$\endgroup$
2
  • $\begingroup$ Thank you, the "largest" (I read as 'which color won most often') helps a lot. I believe this is how it's solved. I believe either Total Order or Partial Order could be used. $\endgroup$ – Byran Zaugg Dec 5 '20 at 0:55
  • 1
    $\begingroup$ @ByranZaugg, I'm glad it was helpful. A word of warning: if the colors are a partial order but aren't promised to necessarily be totally ordered, the algorithm in the last paragraph of my answer isn't guaranteed to find the color that would win most often if we compared all pairs of colors. If that's what you wanted to find, you might want to ask a new question stating that as the goal. But it looks from your example like maybe the colors are totally ordered, so maybe this won't be an issue. $\endgroup$ – D.W. Dec 5 '20 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.