7

C++ で文字列の繰り返しを使用してすべてのバリエーションを生成したいのですが、非再帰アルゴリズムを強く希望します。過去に再帰アルゴリズムを思いついたことがありますが、複雑さ (r^n) のため、反復的なアプローチが必要です。

Web や 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++ プログラムが必要です。

これは学習目的であり、宿題ではありません。宿題がこうだったらいいのに。

4

3 に答える 3

5

アルファベットの文字数に等しい基数で数えると考えることができます（可能な入力である場合は、アルファベットの複数の等しい文字に特別な注意を払ってください）。aaaa aaab aaba ...たとえば、例は実際には0〜15の数値の2進表現です。

基数変換を検索し、各「数字」から対応する文字へのマッピングを実装してから、0からword_lengthalphabet_sizeへのforループを実行するだけです。

このようなアルゴリズムは、一定量のメモリを使用して生成する必要のある文字列の数に比例して時間内に実行する必要があります。

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
于 2010-06-11T21:21:40.340 に答える
1

これは一般的なレシピであり、製品の実装に固有の C++ ではありません。

積の入力文字列"abc.."を取得して、行列を生成し "abc.."x"abc.."ます。N^2 の複雑さ。行列をベクトルとして表し、"abc"、complexity (N^2)*N、repeat による乗算を繰り返します。

于 2010-06-11T21:49:46.867 に答える