Algorithmus drucken alle Buchstaben des Strings in lexikographische Ordnung

Habe ich versucht den code zu generieren, der alle möglichen Kombination der gegebenen Zeichenfolge in der lexikographischen Reihenfolge:

Den code, den ich geschrieben habe ist:

void get(char *n)
 {
    int l=strlen(n); 
    sort(n,n+l);
    int k=0,m,i,j,z;

    while(k<l)
    {
        m=k;

        for(i=k;i<l;i++)
        {
            for(j=k;j<=i;j++)
                cout<<n[j];

            cout<<"\n";
        }

        for(z=m+2;z<l;z++)
            cout<<n[m]<<n[z]<<"\n";  

        k++;
    }
 }


int main() 
 {
    char n[100];
    cin>>n;
    get(n);
    return 0;
 }

Angenommen, der string ist : abcde

Mein code ist nicht die Erzeugung Kombinationen wie:

abd
abe

Den Ausgang bin ich immer für die Zeichenfolge "abcde" sind:

a 
ab
abc 
abcd 
abcde 
ac 
ad
ae 
b 
bc 
bcd 
bcde 
bd 
be 
c 
cd 
cde 
ce 
d 
de 
e

Meiner Ausgabe nicht enthalten Zeichenfolgen wie : abd abe

Hoffe, das macht die Frage klar

How zu generieren, die alle diese Kombinationen mit Hilfe eines effizienten Algorithmus

Welchen output bekommen Sie? Es kann helfen bei der Aufzucht der Fehler, ohne uns tatsächlich zu kompilieren und führen Sie das Programm.
Es ist l ,ich bin Sortieren Sie die Zeichenfolge zu finden, die lexikographisch kleinste Zeichenkette, kann sein erreicht durch den angegebenen string und dann fortfahren

InformationsquelleAutor sac | 2015-03-15

  1. 2

    Dies ist eine einfache rekursive Ansatz:

    #include <string>
#include <iostream>
using namespace std;

void get( string str, string res ) {

   cout << res << endl;

   for( int i = 0; i < str.length(); i++ )
      get( string(str).erase(i,1), res + str[i] );
}

int main( int argc, char **argv) {

   string str = "abcde";
   get( str, "" );  
   return 0;
}

    Vielleicht nicht der effizienteste Weg, es zu tun, aber eine kurze und einfache. Beachten Sie, dass die Aufzählung aller Kombinationen hat eine Komplexität von O(2n) sowieso. So gibt es keinen effizienten Algorithmus überhaupt.

    Diese codes werden nicht gedruckt Kombinationen der Streicher, aber Permutationen, die strings (in allen Größen). Die Frage fragt nach Kombinationen.

    InformationsquelleAutor user0815

  2. 2

    Kann Folgendes helfen:

    bool increase(std::vector<bool>& bs)
{
    for (std::size_t i = 0; i != bs.size(); ++i) {
        bs[i] = !bs[i];
        if (bs[i] == true) {
            return true;
        }
    }
    return false; //overflow
}

template <typename T>
void PowerSet(const std::vector<T>& v)
{
    std::vector<bool> bitset(v.size());

    do {
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (increase(bitset));
}

    Live-Beispiel

    InformationsquelleAutor Jarod42

Schreibe einen Kommentar