C++ program that generates all possible shuffled variations of a word without duplicates. Single header file.

shuffle.hpp

/*
  Copyright 2022 orbyfied <https://www.github.com/orbyfied>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
For test program usage, go to the test program section at the end of the file.
To use this as a library, just include this header and you are good to go.
If you want debug information printed, compile the files including the header with
```
g++ ... -D _DEBUG
```
, or define _DEBUG manually in the file like so:
```
#define _DEBUG 1 // always do it before including
#include <shuffle.hpp>
```
*/

#pragma once

// header guard
#ifndef __HG_ORBYFIED_SHUFFLE
#define __HG_ORBYFIED_SHUFFLE

// std includes
#include <string>
#include <vector>
#include <memory.h>
#include <math.h>
#include <sstream>
#include <iterator>

// debug definitions

#include <iostream>

inline std::string rep_str(std::string str, int a) {
    std::ostringstream oss;
    for (int i = 0; i < a; i++)
        oss << str;
    return oss.str();
} 

#ifdef _DEBUG

#define dprintln(x) std::cout << "+- DEBUG: " << x << std::endl;

static bool IS_DEBUG = true;
#define debugc if (1)
#define edump_stack abort();

#else // _DEBUG

static bool IS_DEBUG = false;
#define debugc if (0)
#define edump_stack

#endif // _DEBUG

template <typename T>
inline void printlnd(T x) { 
#ifdef _DEBUG
    dprintln(x);
#endif // _DEBUG
}

/*
   
    Utilities

*/

#define m_min(a, b) (a < b ? a : b)

// common typedefs
typedef char* cstr;

typedef unsigned long long u64;
typedef          long long i64;
typedef unsigned int       u32;
typedef          int       i32;
typedef unsigned short     u16;
typedef          short     i16;
typedef char u8;
typedef u8   byte;

using std::string;
using std::vector;

/**
 * @brief Converts a number to a hexadecimal string
 * @tparam I The type of number.
 * https://stackoverflow.com/a/33447587/14837740
 */
template <typename I> 
string tostr16(I w, size_t hex_len = sizeof(I) << 1) {
    static const char* digits = "0123456789ABCDEF";
    string rc(hex_len,'0');
    for (size_t i = 0, j = (hex_len-1) * 4 ; i < hex_len; ++i ,j -= 4)
        rc[i] = digits[ (w>>j) & 0x0f ];
    return rc;
}

/**
 * @brief Gets the string representation of a vector.
 * @tparam T The element type.
 * @param vec The vector.
 * @return string The string representation.
 */
template <typename T>
inline string vec_to_string(vector<T>& vec) {
    if (vec.empty()) return "[]";
    std::ostringstream oss;
    oss << "[";
    std::copy(vec.begin(), vec.end() - 1, std::ostream_iterator<T>(oss, ","));
    oss << vec.back();
    oss << "]";
    return oss.str();
}

/**
 * @brief A simple string builder or buffer class.
 */
class str_buf {

public:
    /**
     * @brief Construct a new string buffer.
     * 
     * @param initAlloc The initial allocated size.
     */
    str_buf(int initAlloc) {
        this->alloc = initAlloc;
        this->len   = 0;
        this->resize(initAlloc);
    }

    /**
     * @brief The actual size of the buffer allocated
     */
    int alloc;

    /**
     * @brief The length of the buffer.
     * Also used as the offset to the tail of the buffer.
     */
    int len;

    /**
     * @brief The buffer itself.
     */
    char* buf;

    /**
     * @brief Appends a C string to this buffer.
     * It adds each individual character until it hits a '\0'
     * @param what The string to append.
     * @return str_buf* This.
     */
    str_buf* append(const cstr what) {
        char c;
        int i = 0;
        while ((c = what[i++]) != '\0') {
            this->append(c);
        }
        return this;
    }

    /**
     * @brief Appends a C++ string to this buffer.
     * Utilities memcpy(...) for performance.
     * Checks if it should resize in one go, then
     * memcpy(...) s the string data into the buffer,
     * increments pointer and length by the string length.
     * @param what The string to append.
     * @return str_buf* This.
     */
    str_buf* append(const string& what) {
        int l = what.length();
        if (len + l >= alloc) {
            // resize
            this->resize((int)(alloc + l * 1.4));
        }

        memcpy(this->buf, what.data(), l * sizeof(char));
        this->len += what.length();
        return this;
    }

    /**
     * @brief Appends one character to this buffer.
     * Checks if it should resize, sets character and
     * increments the tail pointer and length.
     * @param what The character to append.
     * @return str_buf* This.
     */
    str_buf* append(char what) {
        if (len + 1 == alloc) {
            // resize
            this->resize((int)(alloc * 1.6));
        }

        this->buf[len++] = what;
        return this;
    }

    /**
     * @brief Trims the buffer from the tail by { mag }
     * Decrements the pointer and length by { mag },
     * means that anything appended will overwrite the
     * data that was previously there. 
     * @param mag The magnitude / amount to trim.
     * @return str_buf* This.
     */
    str_buf* back(int mag) {
        this->len -= mag;
        return this;
    }

    /**
     * @brief Resizes and copies the buffer.
     * This is more of an internal function.
     * @param size The target size.
     * @return str_buf* This.
     */
    str_buf* resize(int size) {
        this->alloc = size;
        char* buf = this->buf;
        this->buf = (char*)malloc(size * sizeof(char));
        if (this->len > 0) {
            memcpy(this->buf, buf, m_min(this->len, size));
            free(buf);
        }
        return this;
    }

    /**
     * @brief Closes this buffer, deallocating all resources.
     */
    void close() {
        free(this->buf);
        this->len   = 0;
        this->alloc = 0;
    }

    /**
     * @brief Returns the length of this buffer.
     * @return int The length.
     */
    int length() {
        return this->len;
    }

    /**
     * @brief Compiles the buffer into an std::string.
     * ...
     * @return str The std::string.
     */
    string compile() {
        string s(this->build_cstr());
        return s;
    }

    /**
     * @brief Compiles the buffer into a C string.
     * Compiles this buffer into a char* by copying the
     * contents of the buffer in the range (0-len) into
     * a buffer with size len + 1, and adds the '\0' 
     * character at the end.
     * @return cstr The char* string.
     */
    cstr build_cstr() {
        char* s = (char*)malloc((len + 1) * sizeof(char));
        memcpy(s, this->buf, len);
        s[len] = '\0';
        return s;
    }

    /**
     * @brief Prints debug information about the buffer.
     * Only if _DEBUG is enabled.
     * Prints content, tail pointer, length, allocated memory, 
     * address, etc.
     */
    inline void print_debug() {
#ifdef _DEBUG
    std::cout << "buf[" << tostr16((u64)(this)) 
        << "] len: " << this->len
        << ", alloc: " << this->alloc 
        << ", str: '" << this->build_cstr() << "'" << std::endl;
#endif
    }

}; // class str_buf

/*

    Magic

*/

/**
 * @brief Internal function for appending the next character.
 * Utilitzes recursion.
 * 
 * @param buf The buffer for the final products.
 * @param depth The recursion depth.
 * @param chars The usable characters.
 * @param used The unusable character from the last stage.
 * @param out The output vector of possibilities.
 */
void next_char(str_buf* buf, 
                int depth, 
                vector<char>* chars, 
                char used, 
                vector<string>* out
#ifdef _DEBUG
                ,int initDepth
#endif // _DEBUG
                ) {

#ifndef _DEBUG
    static const int initDepth = 0;
#endif

    // clone chars for local use
    vector<char> useChars;
    useChars.reserve(chars->size() - 1);

    // remove used character
    bool h = false;
    int l = chars->size();
    for (int i = 0; i < l; i++) {
        char c = chars->at(i);
        if (c == used && !h) {
            h = true;
            continue;
        }
        useChars.push_back(c);
    }

    debugc std::cout 
        << "/" << rep_str(" ", initDepth - depth) << "-depth: " << depth 
        << ", used: '" << used
        << "', chars: " << vec_to_string(useChars)
        << std::endl;

    // iterate over possible characters
    int l2 = useChars.size();
    for (int i = 0; i < l2; i++) {
        char c = useChars[i];

        // append character to the buffer
        buf->append(c);

        debugc {
            std::cout << "| " << rep_str(" ", initDepth - depth);
            buf->print_debug();
        }

        // check depth
        if (depth != 0) {// if depth isnt 0, go to next character
            next_char(buf, depth - 1, &useChars, c, out
#ifdef _DEBUG
                ,initDepth
#endif // _DEBUG
            );
        } else { // else add it as a variation
            out->push_back(buf->compile());
        }

        // reverse character add
        buf->back(1);

    }

    debugc { 
        std::cout << "| " << rep_str(" ", 5 - depth) << "END: ";
        std::cout << "depth: " << depth << "  ";
        buf->print_debug(); 
    }

}

/**
 * @brief Get the all shuffled variations of a string.
 * 
 * @param in The string to shuffle.
 * @return vec<str>* -> The list of variations.
 */
vector<string>* get_all_shuffles(string in) {

    // create buffer
    int l = in.size();
    str_buf* buf = new str_buf(l);

    // get depth
    int depth = l - 1;

    // no used characters
    char used = '\0';

    // create output vector
    vector<string>* out = new vector<string>;

    // get possible characters
    vector<char> chars;
    chars.reserve(l);
    for (int i = 0; i < l; i++)
        chars.push_back(in.at(i));

    // do the magic
    next_char(buf, depth, &chars, used, out
#ifdef _DEBUG
                ,depth
#endif // _DEBUG
    );

    // close buffer
    buf->close();
    
    // return output vector
    return out;

}

#ifdef _TEST

#include <chrono>

using namespace std::chrono;
using namespace std::literals;
using namespace std::string_literals;

using std::to_string;

/*
Simple Test Program Usage:

Enter the file you want to call it from (in my case main.cpp)
<main.cpp>
```
#define _TEST 1 // enable and include the test program
#include "shuffle.hpp" // include the header file (order is important)

int main() {
    // call the test program
    shuffle_test_program();
}
```
*/



/**
 * @brief Runs a simple test program.
 */
vector<string>* shuffle_test_program() {

    // get a word to shuffle from the console
    char* buf = new char[1024];
    std::cout << "+ input: ";
    std::cin >> buf;
    string input(buf);
    std::cout << "+ inputted: " << input << std::endl;

    // shuffle the word (w/ performance monitoring)
    auto t1 = steady_clock::now();
    std::cout << "+ generating " << std::endl;

    vector<string>* shuffles = get_all_shuffles(input);

    auto t2 = steady_clock::now();
    auto tg = t2 - t1;
    string elapsedtimestr = to_string(tg / 1us) + "us ("s + to_string(tg / 1ms) + "ms)"s;
    std::cout << "| generated " << shuffles->size() << " variations in " << elapsedtimestr << std::endl;

    // output 
    std::cout << "+ outputting" << std::endl;
    int l = shuffles->size();
    for (int i = 0; i < l; i++) {
        string v = shuffles->at(i);

        std::cout << "| var " << i << ": " << v << std::endl;
    }

    std::cout << "| count: " << l << std::endl;
    std::cout << "| generated in " << elapsedtimestr << std::endl;

    // return
    return shuffles;

}

#endif

#endif // __HG_ORBYFIED_SHUFFLE