Mémoïsation

1. C’est un problème de dénombrement.

2. On génère toutes les écritures binaires sur \(n\) bits (\(2^{n}\) écritures possibles) et pour chaque écriture on cherche s’il y a deux 0 consécutifs en \(\O(n)\). On incrémente un compteur à chaque fois qu’il n’y en a pas.

   Voici un code possible.

      def deuxzeros(ecriture) : # $\O(n)$
          for i in range(len(ecriture)-1) :
              if ecriture[i] == 0 and ecriture[i+1] == 0 :
                  return True
          return False
        
      def E(n) :
          if n == 1 :
              return [[]]
          E_prec = E(n-1)
          return [ x + [1] for x in E_prec ] + [ x + [0] for x in E_prec ]
        
      def P(n) :
          p = 0
          for ecriture in E(n) :
              if not deuxzeros(ecriture) :
                  p += 1
          return p
   

   La complexité de E pourrait être améliorée mais dans tous les cas la complexité finale est donc en \(\mathrm O(n\,2^n)\).

3. \(P(0) = 1\), \(P(1) = 2\), \(P(2) = 3\) et \(P(n) = P(n-1) + P(n-2)\), il s’agit de la suite de fibonacci décalée d’un terme. En effet on peut séparer les écritures sur \(n+2\) bits en 3 groupes :

   1. Les écritures qui ont 1 comme bit de poids fort.

      Dans ce groupe, les écritures ont deux 0 consécutifs, ssi l’écriture sur \(n-1\) bits obtenu en sortant le 1 ont deux 0 consécutifs. L’ensemble des entiers de \(E_{n}\) de ce groupe est exactement l’ensemble \(\{ 2^{n-1} + k, k \in E_{n-1}\}\).

   2. Les écritures qui ont 01 comme bits de poids fort.

      Dans ce groupe, les écritures ont deux 0 consécutifs, ssi l’écriture sur \(n-2\) bits obtenu en sortant le 01 ont deux 0 consécutifs. L’ensemble des entiers de \(E_{n}\) de ce groupe est exactement l’ensemble \(\{ 2^{n-2} + k, k \in E_{n-2}\}\).

   3. Les écritures qui ont 00 comme bits de poids fort.

      Dans ce groupe, les écritures ont toutes deux 0 consécutifs.

   En conclusion, \(E_n = \{ 2^{n-1} + k, k \in E_{n-1}\} \uplus \{ 2^{n-2} + k, k \in E_{n-2}\}\) avec \(\uplus\) l’union disjointe. Ce qui signifie bien que \(P(n) = P(n-1) + P(n-2)\).

1. Problème de décision.

2. On génère tous les sous-ensembles de l, on calcule leur somme et on renvoie True dès qu’on trouve un sous-ensemble dont la somme est k. Si on en trouve pas on renvoie False. On peut construire les sous-ensembles de l[:i+1] à partir de ceux de l[:i] en les dupliquant puis en ajoutant l[i] à l’un des deux seulement. Puis pour chaque sous-ensemble on peut calculer sa somme en $\O$(len(l)) et faire une recherche linéaire d’un ensemble dont la somme vaut k dans l’ensemble des sous-ensembles de l.

   Voici un code possible.

      def somme_egale(sousliste, k) : # $\O(n)$
          s = 0
          for x in sousliste :
              s += x
          return s == k
        
      def souslistes(l,i) : # Calcul les sous listes de l[:i]
          if i == 0 :
              return [[]]
          E_prec = souslistes(i-1)
          return [ e + [l[i-1]] for e in E_prec ] + [ e for e in E_prec ]
        
      def P(k,l) :
          for sousliste in souslistes(l,len(l)) :
              if somme_egale(sousliste, k) :
                  return True
          return False
   

   La génération des sous-listes peut-être rendue plus efficace, mais dans tous les cas la complexité est de \(\O(n\,2^{n})\).

3. P(0,l,i) = True, la liste vide marche. Pour \(k < 0\), P(k,l,i) = False, car les entiers de l sont positifs. Enfin P(k,l,0) = False si \(k > 0\) car le seul sous-ensemble de l[:0] est la liste vide de somme nulle.
4. P(k,l,i+1) = P(k,l,i) or P(k-l[i],l,i). La disjonction consiste aux deux choix possible pour la construction de chaque sous-ensembles de l[:i+1], comme effectué dans la recherche exhaustive :
   1. l[i] est dans le sous ensemble, on se ramène à P(k-l[i],l,i+1),
   2. l[i] n’est pas dans le sous-ensemble, on se ramène à P(k,l,i).

On mémoïse uniquement les entrées (k,i), l n’est pas variable.

def subset_sum_dict_rec(k,l,i,memo) :
    if (k,i) in memo :
        return memo[(k,i)]
    if k == 0 :
        memo[(k,i)] = True
        return memo[(k,i)]
    if i == 0 or k < 0 :
        memo[(k,i)] = False
        return memo[(k,i)]
    memo[(k,i)] = ( subset_sum_dict_rec(k,l,i-1,memo)
                    or subset_sum_dict_rec(k-l[i-1],l,i-1,memo) )
    return memo[(k,i)]
 
def subset_sum_dict(k,l) :
    return subset_sum_dict_rec(k,l,len(l),{})

Dans les sous-problèmes utilisés, la valeur de k diminue tout le temps. Il est difficile de savoir exactement les quels en fonction de l. Si on ne mémoïse pas les valeurs de k négatives, ce qui n’est pas gênant vu que c’est un cas de base qui se calcule en \(\O(1)\), on peut se contenter des sous-problèmes P(s,l,i) avec 0 <= s <= k et 0 <= i <= len(l).

Une matrice (len(l)+1) $\times$ (k+1) suffira pour mémoïser toutes les valeurs.

import numpy as np

def subset_sum_mont(k,l) :
    sp = np.full((len(l)+1,k+1), True)
    for i in range(1,len(l)+1) :
        for s in range(l[i-1]) :
            sp[i][s] = sp[i-1][s]
        for s in range(l[i-1],k+1) :
            sp[i][s] = sp[i-1][s] or sp[i-1][s-l[i-1]]
    return sp[len(l)][k]

En reprenant le raisonnement précédant, une matrice (len(l)+1) $\times$ (k+1) suffira pour mémoïser toutes les valeurs.

Les matrices numpy doivent toujours contenirs le même type d’objets. On ne peut pas avoir à la fois None, True et False. On peut faire une matrice par liste de liste à la place.

Je présente ici une manière de s’en sortir avec trois valeurs entière. -1 pour None, 0 pour True et 1 pour False. Le or se simule avec une multiplication.

def subset_sum_mat_rec(k,l,i,memo) :
    if memo[k][i] < 0 :
        return memo[k][i]
    if k == 0 :
        memo[k][i] = 0
        return memo[k][i]
    if i == 0 or k < 0 :
        memo[k][i] = 1
        return memo[k][i]
    memo[k][i] = ( subset_sum_dict_rec(k,l,i-1,memo)
                    * subset_sum_dict_rec(k-l[i-1],l,i-1,memo) )
    return memo[k][i]
 
def subset_sum_mat(k,l) :
    memo = np.full((k+1,len(l)+1),-1)
    return subset_sum_mat_rec(k,l,len(l),memo) == 0