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

Question

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

Я хочу генерировать все изменения с повторениями строки в 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 ткань из верблюжьей шерсти abbb baaa baab ромовая баба Бабб bbaa bbab bbba bbbb

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

Это для изучения целей, это не домашняя работа. Мне жаль, что моя домашняя работа не была похожа на это.

6

c++ algorithm permutation combinatorics

задан svenstaro 11 June 2010 в 21:08

2 ответа

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

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

2

ответ дан 17 December 2019 в 00:03

Другие вопросы по тегам:

c++ algorithm permutation combinatorics

Похожие вопросы:

score 5 · Accepted Answer

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

Просто выполните поиск по radix-преобразованиям, реализуйте отображение каждой "цифры" на соответствующий символ, а затем просто выполните цикл for от 0 до длины слова_length^{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