Generating words program

Anticross

I have some set of chars QSet<QChar>, and some QStringList to store result. I need to write method that depends on int length value generates all possible combinations of char set size of length. I'll tried to done this w/o recursion but have failed. I need your help:
@void generate(QSet<QChar> & source, QStringList & result, int length)
{
if (length <= 0)
return;

QString word;

QSetIterator<QChar> iter(source);

while (iter.hasNext()) {

    word = "";

    QChar charechter = iter.next();

    for (int i = 0; i <= length; i++)
        word += charechter;

    if (result.contains(word) == false)
        result.append(word);

    int n = 1;

    while (n < length) {

        int pos = length;

        while (pos > 0) {

            QSetIterator<QChar> replaceIter(source);

            while (replaceIter.hasNext()) {

                QChar replaceChar = replaceIter.next();
                word.replace(pos, n, replaceChar);

                if (result.contains(word) == false)
                    result.append(word);
            }

            pos = pos - n;
        }

        n++;
    }
}

}@

bipll

Recursion and iteration are equal here, the choice of method depends primarily on the programming language used and personal preferences. If you do it iteratively, you'll actually get recursive approach described in terms of your own stack control instead of machine native methods. True native recursion just simplifies things a lot.
A typical iterative algorithm would look like:
if the set is empty, return an empty list;
make a vector (or dynamic array) of length length' containing QSet<QChar>::iterators (do not use Java-styke iterators here, they are not copyable), initialize its elements with source.begin(), fill a string of length length' with *source.begin(), append string to the list;
repeat:

while length'th element of iterators vector not equals to source.end(): increase that element; assign length'th element of string to the char of the source that length's element of iterators vector points to, append string to the list;
when length'th element of iterators vector is source.end(), then increase lenth-1'th element of the vector; if it equas source.end(), increase the preceding item and so on. Finally, if you find an element that was not equal to source.end()-1, and thus doesn't point to source.end() after increment
- — set the equally numbered character in the string to the char in the source this element points to;
- starting from next element of the vector up to the vector's end set all vector's elements equal to set.begin() and write the frst char of the source into corresponding positions of string; append the resulting string to the resulting list and go to the word 'repeat:'
otherwise, if all your vector's elements are equal to source.end(), then break the loop and return whatever list you have accumulated.

To visualize this procedure, imagine that you write down all numbers starting from 0 to, say, 1000000, in order, with all the leading zeros included.
And yeah, you should not check if a list already contains a new string, since all QSet elements are distinct and thus all strings would be differing from each other, They wouldn't be lexicographically ordered though, as QSet provides no ordering on stored values.

Anticross

"make a vector (or dynamic array) of length `length’ containing QSet<QChar>::iterators"

Something like this : @ QVector<QSet<QChar>::iterator> test(length);@ ?

"initialize its elements with source.begin(), fill a string of length `length’ with *source.begin(), append string to the list;"

Can you explain other words ? I don't understand what you mean here.

bipll

Guess, it can't be helped...

@#include <QSet>
#include <QChar>
#include <QStringList>
#include <QVector>
#include <functional>
#include <QDebug>

QStringList enumerate(QSet<QChar> const &alphabet, int length) {
QStringList retVal;
if(!(alphabet.empty() || length <= 0)) {
typedef QVector<QSet<QChar>::const_iterator> Word;
Word digits(length, alphabet.cbegin());
QString word(length, ' ');
while(digits[0] != alphabet.cend()) {
std::transform(digits.cbegin(), digits.cend(), word.begin(), [](Word::value_type const &i){return *i;});
retVal.append(word);
Word::iterator i(digits.end() - 1);
for(++*i; i != digits.begin() && i == alphabet.cend(); ++--i);
if(digits[0] != alphabet.cend()) for(++i; i != digits.end(); *i = alphabet.cbegin(), ++i);
}
}
return retVal;
}

int main()
{
qDebug() << enumerate(QSet<QChar>() << 'a' << 'b' << '1', 3);
}@

Anticross

So and what type is AlphaIterator ?

Anticross

I modify my code and has this :
@void MainDialog::generate(QStringList & result, int lenght)
{
if (lenght <= 0)
return;

QSet<QChar>::iterator iter;
QList<QChar> word;

for (iter = m_dictionary.begin(); iter != m_dictionary.end(); ++iter) {

    for (int i = 0; i < lenght; i++)
        word.append(*iter);

    QString sWord;

    for (int j = 0; j < word.count(); j++)
        sWord.append(word.at(j));

    result.append(sWord);
    sWord.clear();

    QSet<QChar>::iterator iter2;

    for (iter2 = iter+1; iter2 != m_dictionary.end(); ++iter2) {

        QList<QChar> word2;

        for (int i = 0; i < lenght; i++) {

            word2 = word;
            word2.replace(i,*iter2);

            for (int j = 0; j < word2.count(); j++)
                sWord.append(word2.at(j));

            result.append(sWord);

            sWord.clear();
        }

        int lenght2 = lenght -1;

        while(lenght2 > 0) {

            word = word2;

            for (int i = 0; i < lenght2; i++) {

                word2 = word;
                word2.replace(i,*iter2);                   

                for (int j = 0; j < word2.count(); j++)
                    sWord.append(word2.at(j));

                result.append(sWord);
                sWord.clear();
            }

            lenght2--;
        }
    }
    word.clear();
}

result.removeDuplicates();

}@
But in result I have not all possible values :( . What have I missed ?

Anticross

Some more modified version look someone for bugs :
@void MainDialog::generate(QStringList & result, int lenght)
{
if (lenght <= 0)
return;

QSet<QChar>::iterator iter;
QList<QChar> word;

for (iter = m_dictionary.begin(); iter != m_dictionary.end(); ++iter) {

    for (int i = 0; i < lenght; i++)
        word.append(*iter);

    QString sWord;

    for (int j = 0; j < word.count(); j++)
        sWord.append(word.at(j));

    result.append(sWord);
    sWord.clear();

    QSet<QChar>::iterator iter2;

    for (iter2 = iter+1; iter2 != m_dictionary.end(); ++iter2) {

        QList<QChar> word2;

        for (int i = 0; i < lenght; i++) {

            word2 = word;
            word2.replace(i,*iter2);

            for (int j = 0; j < word2.count(); j++)
                sWord.append(word2.at(j));

            result.append(sWord);

            sWord.clear();
        }

        int lenght2 = lenght -1;
        QList<QChar> word3;

        while(lenght2 > 0) {

            word3 = word2;

            for (int i = 0; i < lenght2; i++) {

                word2 = word3;
                word2.replace(i,*iter2);                   

                for (int j = 0; j < word2.count(); j++)
                    sWord.append(word2.at(j));

                result.append(sWord);
                sWord.clear();
            }

            lenght2--;
        }
    }
    word.clear();
}

result.removeDuplicates();

}@

Anticross

Hm, I need to make n-dimensional array of m size. Where n is my word length and m is length of dictionary. Fill every dimension by dictionary and make n-loops by it's size to save all words.

bipll

[quote author="Anticross" date="1367321003"]So and what type is AlphaIterator ? [/quote]
Oh, sorry, it just slipped out somehow. This has to be QSet<QChar>::const_iterator, of course, the same as Word::value_type, i. e. something that iterates over the alphabet.
I fixed the code in my post, it should work now.