Mappatura compatta da un set involuto

Question

Permettere $ S $ essere un set (diciamo numeri interi positivi $ leq $ N) e $ f $ Un involuzione ($ f $ è bijective, $ f CDOT f = id $, per esempio xor con una costante). $ g $ è una mappatura idempotente che sceglie un elemento rappresentativo arbitrario in ciascuno $ f $ coppie mappate. Per esempio $ g (x) = min (x, f (x)) $ $$ g: s destrorrow tilde s sottoseteq s $$

Voglio costruire una tabella di ricerca compatta da $ g $Codomain $ tilde s $ a qualsiasi dati problematico, prendendo $ | tilde s | leq | s | $ celle in memoria. Idealmente, desidero costruire una mappatura del bijective $ tilde s destrarrow a sinistra [0, | tilde s | giusto [$.

Può essere fatto in modo efficiente in generale (senza hash mappa o scansione)? Quali proprietà dell'involuzione $ f $ potrebbe aiutare con questo?

Modificare: Ho formulato il problema nel più generale/formalizzato, sperando in una soluzione generica. Seguendo il commento di DW, darò un'applicazione concreta:

Lavoro con le parole del DNA di $ k $ basi di nucleotidi chiamate $ k $-mers. Dal momento che ci sono quattro basi, $ k $-mer sono rappresentati come elementi di $ S = [0,2^{2k} [$

Tuttavia, il DNA può essere letto su entrambi i fili, con orientamenti opposti e basi complementari ($ A leftrighrow t $, $ G leftrighrow c $). Passare da un filo all'altro può essere rappresentato da questo involuzione (completamento inverso, qui per 5-mers): $$ f (x) = text {reverse} _2 (x) oplus 0 text b101010101010 $$ $$ dove $ text {reverse} _2 (abcdefghij) = ijghefcdab $ inverso l'ordine di blocchi a 2 bit e $ oplus $ è l'XOR BIT.

Dal momento che molte applicazioni non distinguono tra a $ k $-mers e il suo completamento inverso, un canonico $ k $-mer viene scelto con $ g (x) = min (x, f (x)) $. La cardinalità di $ g $Il co-dominio è: $$ Left | tilde {s} destro | = inizio {casi} 2^{2k-1} & text {if} k text {is odsh 2^{k-1} Left )

In pratica, salvare meno di un bit di indirizzamento non vale una soluzione complessa. Ma la località della cache è una buona cosa da avere. $ g $ può essere scelto in modo diverso se aiuta in questo.