1

I want to make a dynamic string generator that will generate all possible unique strings from a character set with a dynamic length.

I can make this very easily using for loops but then its static and not dynamic length.

// Prints all possible strings with the length of 3

for a in allowedCharacters {
    for b in allowedCharacters {
        for c in allowedCharacters {
            println(a+b+c)
        }
    }
}

But when I want to make this dynamic of length so I can just call generate(length: 5) I get confused.

I found this Stackoverflow question But the accepted answer generates strings 1-maxLength length and I want maxLength on ever string.

Community
  • 1
  • 1
Arbitur
  • 38,684
  • 22
  • 91
  • 128
  • 1
    Why not use the recursion? – Dmitry Sep 22 '15 at 14:44
  • 2
    @Arbitur make sure to explain what "made duplicates and wasn't ordered" means - there is no mentioning of any restrictions in your post and yet you claim that linked solution is not acceptable... – Alexei Levenkov Sep 22 '15 at 14:52
  • @AlexeiLevenkov The linked answer generated something like this: a, b, aa, aa, ab, bb, bb, ab. Several duplicates. – Arbitur Sep 22 '15 at 15:11
  • @Arbitur I seriously doubt - http://ideone.com/vuEOgA... not sure what code you've actually tried. – Alexei Levenkov Sep 22 '15 at 15:17
  • @AlexeiLevenkov Im sorry, the duplications was my translating fault (brain went derp)... But the wavy-like generations was also something I didn't want. – Arbitur Sep 22 '15 at 15:27
  • @Arbitur you may want to edit you post to clarify that... Also it is now completely confusing question - "swift" with accepted answer in C#... (not sure if anything should be done about it). – Alexei Levenkov Sep 22 '15 at 15:37

3 Answers3

4

As noted above, use recursion. Here is how it can be done with C#:

static IEnumerable<string> Generate(int length, char[] allowed_chars)
{
    if (length == 1)
    {
        foreach (char c in allowed_chars)
            yield return c.ToString();
    }
    else
    {
        var sub_strings = Generate(length - 1, allowed_chars);

        foreach (char c in allowed_chars)
        {
            foreach (string sub in sub_strings)
            {
                yield return c + sub;
            }

        }
    }
}

private static void Main(string[] args)
{

    string chars = "abc";

    List<string> result = Generate(3, chars.ToCharArray()).ToList();

}

Please note that the run time of this algorithm and the amount of data it returns is exponential as the length increases which means that if you have large lengths, you should expect the code to take a long time and to return a huge amount of data.

Yacoub Massad
  • 27,509
  • 2
  • 36
  • 62
  • I will translate this to Swift and Ill return :) – Arbitur Sep 22 '15 at 14:54
  • This look basically identical to solution suggested in linked post. Please make sure to clarify how it is different (ignoring iterator part). It also does not address the fact that linked suggestion "made duplicates and wasn't ordered" (whatever it means). – Alexei Levenkov Sep 22 '15 at 14:57
  • The referenced question requires all strings of length up to a specific length, this question however requires all strings of specific length. The answer in the other question is writing the results directly to the console, here we generate the data and return them to the caller. – Yacoub Massad Sep 22 '15 at 15:01
  • It seems to me that the different between the two questions is minor – Yacoub Massad Sep 22 '15 at 15:03
  • Thanks! This is perfect :D – Arbitur Sep 22 '15 at 15:08
  • This was different from the accepted answer in the question I linked to @AlexeiLevenkov This didnt generate in a mess and it didnt create duplicate strings. – Arbitur Sep 22 '15 at 15:09
1

Translation of @YacoubMassad's C# code to Swift:

func generate(length: Int, allowedChars: [String]) -> [String] {
    if length == 1 {
        return allowedChars
    }
    else {
        let subStrings = generate(length - 1, allowedChars: allowedChars)

        var arr = [String]()
        for c in allowedChars {
            for sub in subStrings {
                arr.append(c + sub)
            }
        }

        return arr
    }
}

println(generate(3, allowedChars: ["a", "b", "c"]))

Prints:

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

Arbitur
  • 38,684
  • 22
  • 91
  • 128
  • If you are interested in a review (e.g. possible improvements) of your code then you could post it on http://codereview.stackexchange.com/tour. – Martin R Sep 22 '15 at 16:26
  • Thank you @MartinR I havent explored the other stack exchange forums that much :) – Arbitur Sep 22 '15 at 16:38
1

While you can (obviously enough) use recursion to solve this problem, it quite an inefficient way to do the job.

What you're really doing is just counting. In your example, with "a", "b" and "c" as the allowed characters, you're counting in base 3, and since you're allowing three character strings, they're three digit numbers.

An N-digit number in base M can represent NM different possible values, going from 0 through NM-1. So, for your case, that's limit=pow(3, 3)-1;. To generate all those values, you just count from 0 through the limit, and convert each number to base M, using the specified characters as the "digits". For example, in C++ the code can look like this:

#include <string>
#include <iostream>

int main() { 
    std::string letters = "abc";
    std::size_t base = letters.length();
    std::size_t digits = 3;

    int limit = pow(base, digits);

    for (int i = 0; i < limit; i++) {
        int in = i;
        for (int j = 0; j < digits; j++) {
            std::cout << letters[in%base];
            in /= base;
        }
        std::cout << "\t";
    }
}

One minor note: as I've written it here, this produces the output in basically a little-endian format. That is, the "digit" that varies the fastest is on the left, and the one that changes the slowest is on the right.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111