空間効率と時間効率に優れた、2 つの型の間の有限全単射を表す関数データ構造を探しています。
たとえば、サイズ n の全単射 f を考えると、次のようになれば幸いです。
- 新しい要素のペアで f を拡張すると、複雑さが O(ln n) になります。
- f(x) または f^-1(x) のクエリの複雑さ O(ln n)
- f の内部表現は、2 つの有限マップ (f とその逆を表す) を持つよりも空間効率が良い
この論文のように順列の効率的な表現を認識していますが、それは私の問題を解決していないようです。