?

Log in

No account? Create an account
Grizzly Weinstein
sea_gaagii
.:.::.. .:.:.::.:
April 2009
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30

Grizzly Weinstein [userpic]
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;
}