Discussion :

[Feroce14]

Bonjour,

Je dois faire un petit code en haskell mais par faute de temps je ne peux le faire.
Il s'agit de traduire une petite fonction de C++ en Haskell.
Il s'agit de la suite deBruijn

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void first_test_algo(unsigned int t,
              unsigned int p,
              const unsigned int k,
              const unsigned int n,
              unsigned int* a,
              std::function<void (unsigned int *, unsigned int *)> callback)
{
  if (t > n) {
    // we want only necklaces, not pre-necklaces or Lyndon words                                        
    if (n % p == 0) {
      callback(a+1, a+p+1);
    }
  }
  else {
    a[t] = a[t-p];
 
    first_test_algo(t+1, p, k, n, a, callback);
 
    for (unsigned int j = a[t-p]+1; j < k; ++j) {
      a[t] = j;
      first_test_algo(t+1, t, k, n, a, callback);
    }
  }
}

La chose majeur à changer est la partie Callback dans la condition if t > n;
Je n'ai pas à utiliser le callback dans mon programme en Haskell.

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
struct seq_printer {
  const std::vector<char>& _alpha;
 
  seq_printer(const std::vector<char>& alpha) : _alpha(alpha) {}
 
  void operator() (unsigned int* a, unsigned int* a_end) const {
    for (unsigned int* i = a; i < a_end; ++i) {
      std::cout << _alpha[*i];
    }
  }
};

Cette struct me print ma sequence si t > n.
Voila, merci d'avance pour votre aide

[Jedai]

L'objectif est-il de générer une suite de De Bruijn (k=?) ou y a-t-il une obligation sur l'algo ou les performances ?

Parce qu'une solution simple serait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
deBruijn :: Int -> [Int]
deBruijn n = iterate step (replicate n 0) !! (2^n - n) 
  where 
    step ds = if take n (1:ds) `isInfixOf` ds then (0:ds) else (1:ds)

(algo "prefer 1", k=2, performances assez mauvaise vu l'usage de listes)
Sinon il va nous falloir des détails, on ne va pas traduire directement ton code en Haskell, les langages sont trop différents, le résultat serait d'une laideur suprême.

--
Jedaï