Как сгенерировать все варианты с повторениями строки? - PullRequest
Новая
       27

Как сгенерировать все варианты с повторениями строки?

6 голосов
/ 12 июня 2010

Я хочу генерировать все варианты с повторениями строки в C ++, и я бы предпочел нерекурсивный алгоритм.В прошлом я придумал рекурсивный алгоритм, но из-за сложности (r ^ n) я хотел бы увидеть итеративный подход.

Я весьма удивлен, что не смогнайти решение этой проблемы в любом месте в Интернете или в StackOverflow.

Я придумал скрипт Python, который также делает то, что я хочу: 

import itertools

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

Вывод:

aaaa aaab aaba aabb abaa abab abba abbb baaa baab baba babb bbaa bbab bbba bbbb

В идеале я бы хотел программу на C ++, которая может производить точный вывод, принимая точныете же параметры.

Это для целей обучения, это не домашняя работа.Я бы хотел, чтобы моя домашняя работа была такой.

Ответы [ 3 ]

5 голосов
/ 12 июня 2010

Вы могли бы думать об этом как о подсчете, с основанием, равным количеству символов в алфавите (особенно заботясь о нескольких равных символах в алфавите, если это возможно). Например, aaaa aaab aaba ... пример - это двоичное представление чисел 0-15.

Просто выполните поиск радикальных преобразований, осуществите сопоставление от каждой "цифры" до соответствующего символа, а затем просто выполните цикл for от 0 до длины_символа alphabet_size

Такой алгоритм должен работать во времени, линейно пропорциональном количеству строк, которые должны быть получены с использованием постоянного объема памяти.

Демонстрация на 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);
        }
    }
}

выход: 

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
2 голосов
/ 12 июня 2010

вот общий рецепт, а не C ++, специфичный для реализации продукта:

Возьмите строку ввода продукта "abc.." для генерации матрицы "abc.."x"abc..".N ^ 2 сложность.представить матрицу как вектор и повторить умножение на "abc ", сложность (N^2)*N, повторить.

0 голосов
/ 25 февраля 2017

STL-подобная функция для next_variation. Принимать итераторы любого контейнера типа типа. Вы также можете использовать float / doubles. Алгоритм сам по себе очень прост. Требование к итератору должно быть только вперед. Можно использовать даже std :: list <...>. 

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;
 }
...