Conséquence la plus courante

Une chaîne a $2^n$ séquences, mais elles ne sont généralement pas toutes distinctes. Quelle est la complexité de trouver la fréquence maximale d'une sous-séquence?

Par exemple, la chaîne "sous-séquence" contient 7 copies de la sous-séquence "sue" et c'est le maximum.

Exemple de code de force brute sur http://ideone.com/UIp3t

Existe-t-il des théorèmes structurels connexes? Les deux s'avèrent faux :

la plus longue des sous-séquences de fréquence maximale est unique
la fréquence maximale de toute sous- séquence de longueur $k$ est unimodale en $k$

Liens éventuellement liés:

Compter # sous-séquences distinctes $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Problème de concours connexe pour plusieurs sources http://www.spoj.pl/problems/CSUBSEQS/
Document connexe http://dx.doi.org/10.1016/j.tcs.2008.08.035

Modifier 10 jours plus tard: merci d'avoir regardé! Je m'étais demandé si cela poserait un joli problème de concours de programmation résoluble en temps polynomial. Je suppose que non, mais j'espère y repenser plus tard.

ds.algorithms string-search daveagp
la source

Une première question peut-être naïve: est-il clair que ce problème est même en NP ? C'est-à-dire: pour le problème de déterminer s'il existe une sous-séquence avec au moins k occurrences dans une chaîne de n caractères, à quoi ressemblerait un certificat? Par exemple, répertorier tous les tuples d'indices indiquant les instances d'une sous-séquence donnée ne serait pas de taille polynomiale pour la chaîne aaa ... aa (qui, bien qu'une entrée ennuyeuse, a néanmoins une sous-chaîne avec environ

n C (n / 2)

$n \mathbf C (n/2)$ occurrences).

Niel de Beaudrap

@Niel de Beaudrap: Je pense que l'on peut compter le nombre d'occurrences comme sous-séquences en temps polynomial par programmation dynamique, permettant d'utiliser la sous-séquence elle-même comme certificat.

Tsuyoshi Ito

Je suis un peu confus: la question "est-elle donnée une chaîne s, trouver la sous-séquence qui se produit le nombre maximum de fois?"

Suresh Venkat

@SureshVenkat: Oui, c'est ma compréhension. Par exemple, étant donné une séquence de

X en entrée, la bonne réponse serait une séquence de

n

$n$

n / 2

$n/2$

Jeffε

@ marzio-de-biasi: la question à laquelle vous avez lié est différente (et beaucoup plus facile): là vous est donnée la sous-séquence.

david

Réponses:

à partir d'une recherche, voici un article avec quelques recherches et résultats pour la recherche de niveau universitaire mais (mise en garde) aucune référence. il contient des heuristiques, des estimations, des résultats empiriques et des commentaires sur le problème et quelques idées pour prouver sa complexité (approximative), etc.

Identification des conséquences les plus fréquentes
CSE 549 Projet de biologie computationnelle Rapport final
Mikhail Bautin 2006

(Bien qu'il existe des problèmes de sous-séquence standard qui soient quelque peu similaires et étudiés, par exemple dans l'article d'Elzinga et al, est-il possible que ce problème de sous-séquence particulier n'ait pas été trop étudié?)

vzn
la source

Je ne comprends pas pourquoi cela a été rejeté. Ce n'est peut-être pas un document très approfondi, mais il semble être directement sur le sujet.

David Eppstein

fyi / addendum Bautin dit également à la fin du papier qu'il a 5K lignes de code C ++ & Python sur le problème / papier pour toute personne intéressée

vzn

@ David, je ne pense pas que le downvote soit à cause du papier lié, c'est probablement plus à voir avec le fait que cette réponse ressemble (essentiellement) à une réponse de lien d'une ligne (sans expliquer comment le papier est lié à la question et y répond). Cela aurait peut-être été plus approprié en tant que commentaire.

Kaveh

ok kaveh, alors, énoncé: le document semble révéler (à moins que quiconque puisse trouver une meilleure référence ou trouver lui-même la preuve de ce problème difficile) que la complexité exacte du problème soit jusqu'à présent inconnue / ouverte (autre que l'évidence PSpace / ExpTime) et peut contenir les analyses / approches les plus connues pour le résoudre à ce jour

vzn

J'ai déjà trouvé ce document avant et je m'excuse de ne pas y avoir lié ci-dessus, car je ne pensais pas qu'il fournissait beaucoup d'informations concrètes. J'ai envoyé à l'auteur un e-mail il y a quelque temps pour lui demander s'il pouvait en dire plus sur tout ce qui s'était passé depuis sa rédaction, mais je n'ai pas encore reçu de réponse.

daveagp

Pas une réponse, juste un lemme.

${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
la source