2
\$\begingroup\$

I'm looking to improve my skills as a developer so I recently challenged myself to design a string permutation generator without recursion. To add to the algorithm I also decided that the string should have a filter to it. An example of a filter would be "lld" where "l" is any character a-z and "d" is any digit 0-9. The filter "lld" should produce all strings aa0-zz9. Would love feedback on how to improve this algo. Thanks.

Implementation in C++

#include <iostream>

#define CHAR_SET_LEN 26
#define INT_SET_LEN 10
#define FILTER_LEN 3

int main() {
    std::cout << "Hello, World!" << std::endl;

    char char_set[CHAR_SET_LEN] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    char int_set[INT_SET_LEN] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    bool doLoop = true;

    int filterStack[100];

    int filterLength = FILTER_LEN;

    char filter[FILTER_LEN+1] = "lld";

    for (int i=0; i < filterLength; i++) {
        filterStack[i] = 0;
    }

    while (doLoop) {
        char string[FILTER_LEN];

        for (int a = 0; a < filterLength; a++) {
            if (filter[a] == 'l') {
                string[a] = char_set[filterStack[a]];
            }
            else {
                string[a] = int_set[filterStack[a]];
            }

        }
//
        std::cout << string << std::endl;
//
        for (int z = (filterLength-1); z > -1; z--) {
            filterStack[z] = filterStack[z] + 1;

            int finalFilter = INT_SET_LEN;
            if (filter[z] == 'l') {
                finalFilter = CHAR_SET_LEN;
            }

            if (filterStack[z] < finalFilter) {
                break;
            }
            else {
                if (z == 0 && (filterStack[z] == finalFilter)) {
                    doLoop = false;
                    break;
                }

                filterStack[z] = 0;
            }
        }
    }


    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ I think you need char string[FILTER_LEN + 1]; string[FILTER_LEN] = '\0' to create a null-terminated string. If your std::cout << string works, it's by chance. \$\endgroup\$ Jan 12, 2018 at 16:27
  • \$\begingroup\$ Alternatively, create a standard string: std::string(string, sizeof string). You might want to rename your variable! \$\endgroup\$ Jan 12, 2018 at 16:41

1 Answer 1

1
\$\begingroup\$

Are you sure this is C++?

...because this is almost 100% C. Let's go over some things:

  1. #define is discouraged in modern C++, as is reliance on the C preprocessor in general. Just define your constants with const and (depending on the situation) constexpr.
  2. Don't define raw arrays. Use std::array for fixed size arrays, std::vector for dynamic arrays, or any other standard container class.
  3. Don't use char arrays if you mean strings. C++ offers std::string for general string handling and std::stringstream for string building.
  4. Use standard algorithms. For example, your first for-loop could be replaced with a call to std::fill.

That said, there are

Other Issues

  1. Don't use std::endl. '\n' does the same thing, but doesn't include the unnecessary flush std::endl comes with.
  2. You don't need char_set and int_set. You can generate all lowercase letter by adding their offset in the alphabet to 'a' (i.e. 'a' + 1 == 'b') thanks to the (almost) ubiquitous ASCII encoding. The same is true for digits.
  3. int is not the right type for index variables. Use somethings more appropriate, such as std::size_t, instead.
  4. You should export some of your code to proper functions. Just putting everything into main makes your code hard to read and prone to bugs.
  5. As Cris Luengo pointed out in the comments already, string is not null-terminated, and thus you're causing undefined behavior when writing it to std::cout.
  6. filter is one character longer than it needs to be. Since you never do something with it that would require it to be null terminated (and don't even null terminate the string, just keep an unused character at the end), it suffices to make its length FILTER_LEN.
\$\endgroup\$
5
  • \$\begingroup\$ You're right. I seem to have one toe in C and one in C++. Will clean that up. Really this should be C \$\endgroup\$
    – atr07
    Jan 12, 2018 at 21:39
  • \$\begingroup\$ Well, C++17 std::string_view is preferable to std::string where applicable. \$\endgroup\$ Jan 12, 2018 at 21:56
  • \$\begingroup\$ @Deduplicator It is, but I don't think it is applicable here (except for filter maybe). \$\endgroup\$ Jan 12, 2018 at 21:59
  • \$\begingroup\$ @Deduplicator, due to its absence of ownership semantics, I'd prefer to use it only in template metaprogramming context, or in cases where doing otherwise will complicate things. \$\endgroup\$ Jan 13, 2018 at 15:36
  • \$\begingroup\$ @Incomputable: For best effect, use it in any and all contexts where the callee shall not acquire ownership, and preferentially in contexts where it wraps a string-literal. It's absence of ownership is its greatest strength. \$\endgroup\$ Jan 13, 2018 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.