CODEWITHSUNDEEP
c++combinationspermutation
Nicholas Pipitone
Nicholas Pipitone

Reputation: 4192

Non-repeating permutations

I am having an issue. I want to iterate through all the possible combinations of the 26 letters of the alphabet (Well.... only 25 letters, I want to exclude 'q'). It appears to be simple, but it is proving difficult. I want to start with a char* containing a-z excluding q, and a for loop which will flip through every possible combination of those letters (order matters, no repeating letters), executing a function that checks if that combination is the one I'm looking for.

std::next_permutation doesn't work for my scenario. Specifically, I need code that will iterate backwards. Start with: a bcd.... z, b acde.... z, c abde.... z, ... z abcd.... y,

ab cdef.... z, ac bdef.... z, ad
.. az

ba bc bd

Pretty much come up with every combination of two letters words, then three letters, then four, adding the rest of the alphabet afterwords. I have the code that adds the rest of the alphabet, so all I need is the first part.

After I figure out how to generate n-letter words, it will be causing repeats. Iterate through every two letter word and I get "ab ac ad ... az ba bc bd .. bz" but remember I add abcdef..z to the end of it (excluding used up letters) so it is actually "abcd..z acbde..z adbcef..z" etc. The two letter word ab and the three letter word abc overlap, which is inefficient for larger keywords.

Upvotes: 1

Views: 1082

Answers (2)

Graham Griffiths
Graham Griffiths

Reputation: 2216

Try this. I usually avoid recursion but here it works quite well :

#include <vector>
#include <set>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;
using std::find;

void printVec(vector<char> &vec)
{
    for(int i = 0; i < vec.size(); i++)
    {
        cout << vec[i];
    }
    cout << endl;
}

void incrementCharAvoidingDuplicates(vector<char> v, char &c)
{
    // increment newChar until we find one not in the vector already
    while(std::find(v.begin(), v.end(), c)!=v.end())
    {
        c++;
    }
}

bool incrementVec(vector<char> &v)
{
    if(v.size() == 0 || v.size() >= 25)
            return false;

    //try incrementing the final character
    char newChar = v.back() + 1;

    incrementCharAvoidingDuplicates(v, newChar);

    // if it's still in range, we have succesfully incremented the vector
    if(newChar <= 'z')
    {
        v.back() = newChar;

        return true;
    }
    // if not (e.g. "abz") then remove the final character and try to increment the base part instead
    else
    {
        vector<char> w(v.begin(), v.end() - 1);

        if(incrementVec(w))
        {
            // we succeeded in incrementing the base ... so find a remaining character that doesn't conflict and append it
            // (note there will always be one since we insisted size < 25)
            v.resize(w.size());
            std::copy(w.begin(), w.end(), v.begin());

            char newChar = 'a';

            incrementCharAvoidingDuplicates(v, newChar);

            v.push_back(newChar);

            return true;
        }
        // otherwise we could not increment the final char, could not increment the base...so we are done
        else
        {
            return false;
        }
    }
}

int main()
{
    static const char arr[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','r','s','t','u','v','w','x','y','z'};
    vector<char> originalAlphabet (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    vector<char> currentWord;
    int desiredWordLength;

    for(desiredWordLength = 1; desiredWordLength < 25; desiredWordLength++)
    {
        currentWord.clear();

        //build first list e.g. a, abc, abcdef, ...
        for(int j = 0; j < desiredWordLength; j++)
        {
            currentWord.push_back(originalAlphabet[j]);
        }

        do{
            printVec(currentWord);
        } while( incrementVec(currentWord));

    }

    return 0;
}

Upvotes: 1

Sumit Trehan
Sumit Trehan

Reputation: 4045

You can use the idea of backtracking to start with. But generating 25! is a daunting task. Iterating through such a large search space will take a lot (i really mean a lot) for a normal computer. You should try to PRUNE your search space by thinking of such cases which you are sure that it can never occur in the desired output. You should look for a technique called backtracking with prunning.

Upvotes: 1

Related Questions