C++ Programm die Anzahl der Strings w der Länge zu berechnen, n über {a, b, c}

Question

Ich versuche alle Strings von Länge zu erzeugen n, so daß jede Teilkette der Länge 4 Schnur w alle drei Buchstaben a, b, c auftreten . Zum Beispiel sollte abbcaabca gedruckt werden, wenn n = 9, aber aabbcabac sollte nicht enthalten sein.

Im Moment drucke ich nur alle Permutationen, aber ich weiß nicht, wie man nur die für diese Sprache druckt.

void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int l, int r) 
{ 

    int i; 
    if (l == r) 
    printf("%s\n", a); 

    else 
    { 
     for (i = l; i <= r; i++) 
     { 
      swap((a+l), (a+i)); 
      permute(a, l+1, r); 
      swap((a+l), (a+i));            
     } 
    } 
} 

int main(){ 
    int n; 
    cout << "Enter n: " << endl; 
    cin >> n; 
    char str[] = "abc"; 
    int x = n % 3; 
    if (x != 0){ 
    for (int i = 0; i < x; i++) 
     *str = *str + str[i]; 
    } 
    permute(str, 0, n - 1); 
    return 0; 
} 

Answer 1

Was ist mit dieser Lösung?

#include <set> 
#include <string> 
#include <iostream> 

void genStrList (std::set<std::string> & setStr, 
       std::size_t const  len, 
       std::string const  & nowStr, 
       std::string const  & poolCh) 
{ 
    int i; 

    std::set<char> noLast3; 

    std::string::const_reverse_iterator cri; 
    std::string::const_iterator   ci; 

    if (2U < nowStr.size()) 
    { 
     for (ci = poolCh.begin() ; ci != poolCh.end() ; ++ci) 
     noLast3.insert(*ci); 

     for (cri = nowStr.rbegin(), i = 0 ; i < 3 ; ++cri, ++i) 
     noLast3.erase(*cri); 
    } 

    if (2U > noLast3.size()) 
    { 
     for (ci = poolCh.begin() ; ci != poolCh.end() ; ++ci) 
     if (noLast3.empty() || (noLast3.end() != noLast3.find(*ci))) 
      { 
      if (nowStr.size() + 1U == len) 
       setStr.insert(nowStr+(*ci)); 
      else 
       genStrList(setStr, len, nowStr+(*ci), poolCh); 
     } 
    } 
} 


int main() 
{ 
    std::size_t n; 

    std::cout << "Enter n: " << std::endl; 
    std::cin >> n; 

    std::set<std::string> setStr; 

    genStrList(setStr, n, "", "abc"); 

    std::set<std::string>::const_iterator ci; 

    for (ci = setStr.begin() ; ci != setStr.end() ; ++ci) 
     std::cout << "- " << (*ci) << '\n'; 

    return 0; 
} 

Answer 2

Eine offensichtliche Lösung wäre, den Block

/* ... */ 
    if (l == r) 
    printf("%s\n", a); 
/* ... */ 

so zu erweitern, dass sie, ob die Zeichenfolge prüft a die Bedingung erfüllt ist, dh ob für jeden Index 3 <= i < n in den letzten vier Zeichen (a[i-3], ..., a[i]) Jeder der Buchstaben a, b und c tritt auf. Dies geschieht leicht in der Zeit O(n) (wobei n ist die Länge der Zeichenfolge a). Die Gesamtlaufzeit erhöht sich von O(n!) auf O(n!*n).

Eine "cleverere" Lösung wäre es, eine Buchhaltung auszuführen --- eine globale Variable, die Sie in jedem rekursiven Aufruf ändern ---, so dass Sie die schlechten Zweige früh abschneiden können (dh Sie machen keine weiteren rekursiven Operationen) ruft auf, wenn der Anfang der Zeichenfolge die Bedingung verletzt). Die Laufzeit wäre in diesem Fall o(n!) (d.h. asymptotisch schneller als n!; siehe little-o notation).