Grizzly Weinstein (sea_gaagii) wrote,
Grizzly Weinstein
sea_gaagii

Shrinking the stack

More efficient solution to r-permutation problem

It really isn't recursion that is the problem it is all the times new vectors are being created on the stack and copied into. Here is a better solution that allows for global management of the vectors.

0) Create a sorted vector of char's marked with depth (default 0) from the word, store it gobally, create a global work in progress string.
1) Call recursive_permute with the number of chars required in the output.
2) Iterate through the global sorted char-depth list, checking the stored depth of the next char vs the current depth
2a) If the stored depth is less then the current depth we are interested unless it was the same as the last char and the last char was at the same level of recursion.
2b) Save off the old depth
2c) Mark the depth as the current depth
2d) Add char to the build string
2e) call recursive_permute (step 2) with depth of one less
2f) After call returns - remove character from work in progress string and restore depth
3) If we didn't call the recursive function once through the loop - possibly at level 0
3a) Print the work in progress string.
4) return;


#include <vector>
#include <stdio.h>
#include <string>
#include <algorithm>

namespace
{
    typedef std::vector<char> CHAR_VECTOR;
    typedef std::pair<char, int> MARKED_CHAR;
    typedef std::vector<MARKED_CHAR> MARKED_CHAR_VECTOR;

    MARKED_CHAR_VECTOR markedCharVector_;
    CHAR_VECTOR buildString_;

    void PermuteRecursive(int depth)
    {
        bool iterated = false;
        char lastChar = '\0';
        for (MARKED_CHAR_VECTOR::iterator nextMarkedChar = markedCharVector_.begin();
             nextMarkedChar != markedCharVector_.end(); nextMarkedChar++)
        {
            if (nextMarkedChar->second >= depth)
            {
                lastChar = '\0';
            }
            else if (lastChar != nextMarkedChar->first)
            {
                iterated = true;
                int oldDepth = nextMarkedChar->second;
                nextMarkedChar->second = depth;
                lastChar = nextMarkedChar->first;
                buildString_.push_back(nextMarkedChar->first);
                PermuteRecursive(depth-1);
                buildString_.pop_back();
                nextMarkedChar->second = oldDepth;
            }
        }
        if (!iterated)
        {
            buildString_.push_back('\0');
            printf("%s\n", &buildString_[0]);
            buildString_.pop_back();
        }
    }
}

void Permute(const std::string& word, int outputSize)
{
    std::string mutableWord(word);
    std::sort(mutableWord.begin(), mutableWord.end());

    markedCharVector_.clear();
    for (std::string::const_iterator nextChar = mutableWord.begin();
         nextChar != mutableWord.end();
         nextChar++)
    {
        markedCharVector_.push_back(MARKED_CHAR(*nextChar, 0));
    }

    buildString_.clear();
    PermuteRecursive(outputSize);
}

int main(void)
{
    Permute("ABAC", 3);

    return 0;
}
Subscribe

  • Racist or just Stupid?

    The internets have been having fun with a recent opinion post from Byron York. Of particular ridicule is this portion: ... and his sky-high ratings…

  • Had a thought today

    I should copyright my DNA. Then if I were ever sued for paternity, I could counter-sue for copyright violations for the derivative work!

  • New 3 Mile Time

    Beat my old time by a few seconds, but the old time was with no incline, the new time is at 1% 3 miles @ 1% incline - 20 minutes 54 seconds.

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments