

たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...)

つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。

[code]

    # 例えば、 pandas を用いてキャラクター能力値を表現する
    chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3})
    chara2 = pd.Series({'power': 2, 'speed': 1, 'magic': 2})
    
[/code]

今、キャラクター A とキャラクター B がいたとき、もし、 A の能力値がすべて B のそれと同等かそれ以上である場合、キャラクター A はキャラクター
B の上位互換であるとします。

### 質問

キャラクターが N 体いたときに、上位互換が存在しないキャラクターの集合を求めたいです。どのように計算するのが効率的ですか？

(数学的な言い換え)
ベクトル値の集合に対して、その上下関係を、「すべての要素について同等かそれ以上であって、かつ、少なくとも一つの要素が上回っている場合、そのベクトル値は、比較対象より上位であるとする」と定義した半順序集合に対して、その極大集合を効率的に求める方法は何でしょうか？


CC BY-SA 4.0
2019-04-15T01:43:14.123
54162
2019-04-15T01:43:14.123
754
question
アルゴリズム 計算量
ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい