Come generare tutte le varianti con ripetizioni di una stringa?

Question

voglio generare tutte le varianti con ripetizioni di una stringa in C ++ e mi piacerebbe molto preferisce un algoritmo non ricorsivo. Mi è venuta in mente un algoritmo ricorsivo in passato, ma a causa della complessità (r ^ n) Mi piacerebbe vedere un approccio iterativo.

Sono abbastanza sorpreso che non ero in grado di trovare una soluzione a questo problema ovunque sul web o su StackOverflow.

mi è venuta in con uno script Python che fa quello che voglio così:

import itertools

variations = itertools.product('ab', repeat=4)
for variations in variations:
        variation_string = ""
        for letter in variations:
                variation_string += letter
        print variation_string

Output:

  

AAAA   AAAB   aaba   AABB   ABAA   abab   abba   ABBB   baaa   Baab   baba   Babb   BBAA   BBAB   bbba   bbbb

Idealmente mi piacerebbe un programma C ++ che può produrre l'output esatto, prendendo le esatte stessi parametri.

Questa è solo a scopo di apprendimento, non è a casa. Vorrei che il mio lavoro era così.

Answer 1

Si potrebbe pensare ad esso come il conteggio, in una radice uguale al numero di caratteri dell'alfabeto (prestando particolare attenzione di più caratteri uguali in alfabeto se questo è un possibile ingresso). L'esempio aaaa aaab aaba ... per esempio, è in realtà la rappresentazione binaria dei numeri 0-15.

Basta fare una ricerca sulle trasformazioni radix, implementare una mappatura da ogni "cifre" per corrispondenti carattere, e poi semplicemente fare un ciclo for da 0 a word_length ^{alphabet_size}

Tale algoritmo dovrebbe funzionare in tempo linearmente proporzionale al numero di stringhe che deve essere prodotta utilizzando costante quantità di memoria.

Manifestazione a Java

public class Test {
    public static void main(String... args) {

        // Limit imposed by Integer.toString(int i, int radix) which is used
        // for the purpose of this demo.
        final String chars = "0123456789abcdefghijklmnopqrstuvwxyz";

        int wordLength = 3;
        char[] alphabet = { 'a', 'b', 'c' };

        for (int i = 0; i < Math.pow(wordLength, alphabet.length); i++) {

            String str = Integer.toString(i, alphabet.length);

            String result = "";
            while (result.length() + str.length() < wordLength)
                result += alphabet[0];

            for (char c : str.toCharArray())
                result += alphabet[chars.indexOf(c)];

            System.out.println(result);
        }
    }
}

uscita:

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

Answer 2

qui è la ricetta generale, non C ++ specifica per implementare prodotto:

prodotto Prendere stringa di input "abc.." per generare matrici "abc.."x"abc..". N ^ 2 complessità. rappresentano la matrice come vettore e ripetere moltiplicazione per "abc", complessità (N^2)*N, ripetizione.

Answer 3

STL come la funzione per next_variation. Accettare iteratori di qualsiasi contenitore di numero come tipo. È possibile utilizzare anche galleggiante / doppie. Algoritmo è di per sé è molto semplice. Necessità di iteratore è di essere solo in avanti. Anche uno std :: list <...> può essere utilizzato.

template<class _Tnumber, class _Titerator >
 bool next_variation
  (
       _Titerator const& _First
     , _Titerator const& _Last
     , _Tnumber const& _Upper
     , _Tnumber const& _Start = 0
     , _Tnumber const& _Step  = 1
  )
  {
   _Titerator _Next = _First;
   while( _Next  != _Last )
    {
      *_Next += _Step;
     if( *_Next < _Upper )
      {
       return true;
      }
     (*_Next) = _Start;
     ++_Next;
    }
   return false;
  }

int main( int argc, char *argv[] )
 {
  std::string s("aaaa");
  do{
      std::cout << s << std::endl;
  }while (next_variation(s.begin(), s.end(), 'c', 'a'));

  std::vector< double > dd(3,1);
  do{
   std::cout << dd[0] << "," << dd[1] << "," << dd[2] << ","  << std::endl;
  }while( next_variation<double>( dd.begin(), dd.end(), 5, 1, 0.5 ) );

  return EXIT_SUCCESS;
 }