Sous-séquences uniques pour un tableau binaire

Question

Existe-t-il un moyen efficace de calculer le nombre de sous-séquences possibles d'un tableau de bits?

Le tableau est lu de gauche à droite, en omettant éventuellement certains éléments. Les sous-séquences en double ne sont pas autorisées.

Le forçage de la brute à travers toutes les sous-séquences possibles prend beaucoup de temps lorsque la taille de la matrice augmente.

Answer 1

Cet algorithme linéaire simple est tiré de "Algorithms for subsequence combinatorics" by Cees Elzinga et al. (2008), légèrement modifié car les mathématiques tendent à être indexées à 1, mais Python est indexé à 0. Il fonctionnera pour toute séquence s, non seulement des séquences binaires:

def count_unique_subsequences(s): 
    """Returns the number of unique subsequences of the sequence s""" 
    L = {} 
    N = [] 
    count = 1 
    for c in s: 
     N.append(count) 
     count *= 2 
     if c in L: 
      count -= N[L[c] - 1] 
     L[c] = len(N) 
    return count 

C'est une solution de programmation dynamique, qui calcule itérativement le nombre de séquences uniques de chaque préfixe de la chaîne en cours. Toutes ces sous-séquences sont toujours des sous-séquences du préfixe suivant, et en plus nous pouvons ajouter n'importe quelle sous-séquence étendue au caractère suivant à l'exception des sous-séquences qui n'ont pas été étendues la dernière fois que nous avons rencontré le même caractère. (Parce qu'à ce point, nous avons compté toutes les sous-séquences étendues avec le caractère.) Dans cet algorithme, le vecteur N maintient le nombre de sous-séquences uniques pour chaque préfixe successif de s (indexé par la longueur du préfixe), tandis que L conserve la trace de l'indice de la dernière occurrence de chaque caractère. Après réflexion sur ce code, j'ai réalisé que N est vraiment redondant; la seule raison pour laquelle nous en avons besoin est de pouvoir rechercher le compte de sous-séquence correspondant au caractère courant. Mais nous pourrions simplement stocker ce nombre directement dans L au lieu de stocker l'index pour une deuxième table de recherche. Cela ne change pas la complexité temporelle de l'algorithme (bien qu'il l'accélère légèrement) mais réduit la complexité de l'espace à O (| Σ |), où Σ est l'alphabet. Pour les séquences binaires, cela rend l'algorithme linéaire-temps/constant-espace. Voici l'algorithme modifié:

def count_unique_subsequences(s): 
    """Returns the number of unique subsequences of the sequence s""" 
    L = {} 
    count = 1 
    for c in s: 
     adds = count - L.get(c, 0) 
     L[c] = count 
     count += adds 
    return count 

Comme présenté, la fonction compte le vide qui ne séquence apparaît pas dans votre énumération, de sorte que vous pourriez vouloir soustraire un du résultat final.

Parmi de nombreux autres résultats intéressants, l'article d'Elzinga considère également le nombre maximum de sous-séquences uniques pour un alphabet d'une taille donnée, démontrant que le nombre maximum est une séquence de Fibonacci généralisée. Pour la taille de l'alphabet 2, le nombre maximal peut être calculé comme suit:

max_count(0) = 1 
max_count(1) = 2 
max_count(n) = max_count(n - 2) + max_count(n - 1) + 1 

qui est fibonacci(n+2)-1.

La chaîne qui génère le motif maximum consiste en une répétition cyclique de l'alphabet.

En fait, énumérer toutes les sous-séquences uniques doit donc prendre un temps exponentiel, puisqu'il existe (potentiellement) un nombre exponentiel de telles séquences. Cependant, l'exposant (pour les séquences binaires) est φ, ce qui est inférieur à 2.