PDA

View Full Version : Using Qt to generate stringlist combinations



kalma
17th March 2012, 10:34
Hi

How can I use Qt to write a function “nemely, generator” that returns combinations of argument sequences “string lists” e.g. combine((‘A’,‘B’),(†˜1’,‘2’,‘3’)) will return [(‘A’,‘1’), (‘A’,‘2’), (‘A’,‘3’), (‘B’,‘1’), (‘B’,‘2’), (‘B’,‘3’)] on demand by calling next() or something i.e. the function will not create the whole list of combinations in memory at once.
The function is to be applicable to any number of sequences i.e. combine(Sequence1, Sequence2, Sequence3, …)

Can anybody help me?

Lykurg
17th March 2012, 12:56
I do not see any specific problem. First try to generate the list at whole. If you have managed that, simply store the index positions of each list in a member function the class and then you can simply implement a next function.

class Generator
{
public:
void init(/*QStringList's*/) {
// set up indexes here e.g.
m_index = 0;
}

QString next() {
// calculate m_index and return the composed string.
}
private:
quint32 m_index;
};

kalma
17th March 2012, 20:52
Hi Lykurg

Thanks for the reply;
"First try to generate the list at whole"

I would follow this but, however, the number of sequences is not predictable at that is why I must not generate the whole list in memory at once, do you have any solid idea how this can be done?

Thanks again

d_stranz
17th March 2012, 22:50
What Lykurg means is that once you know how to generate the entire list, it is relatively simple to take that apart and do it step-wise (that is, using a "next" iterator). By the way, you also need something like an atEnd() or hasNext() so you know when you've reached the end of the list.

So, I would do something like this:



// Sequencer.h:

class Sequencer
{
public:
Sequencer() {}

void initialize( const QVector < QStringList > & stringLists )
{
// store input strings into internal storage, reset indexes
sequences = stringLists;
currentIndexes.resize( sequences .size() );
sequenceLengths.resize( sequences .size() );

// store the size of each subsequence
// The currentIndexes array is used by next() to keep track

for ( int i = 0; i < sequences .size(); ++i )
{
sequenceLengths[ i ] = sequences[i].size();
currentIndexes[ i ] = 0;
}
}

QStringList next()
{
// Always increment the last index first; when it overflows, set it to zero
// then try to increment the second to last, etc. When all indexes are at their
// max value, then return an empty result

QStringList result;

// Before doing anything, make sure we can
if ( hasNext() )
{
for ( int index = sequences .size() - 1; index >= 0; --index )
{
// Check to see if we have overflowed the index at the current level
if ( currentIndexes[ index ] + 1 < sequenceLengths[ index ] - 1 )
{
// OK to increment, so we do that and quit
currentIndexes[ index ]++;
break;
}
else
{
// Set it to zero, and try the next index down
currentIndexes[ index ] = 0;
}
}

// Assemble the output sequence
for ( int index = 0; index < sequences.size(); ++index )
result << sequences[ index ][ currentIndexes[ index ] ];
}
return result;
}

// The sequence can be continued only if all indexes are less than the size
// of the respective subsequence AND the last index can still be incremented
bool hasNext() const
{
bool bHasNext = true;
for ( int index = 0; index < sequences.size(); ++index )
bHasNext &= (currentIndexes[ index ] < sequenceLengths[ index ]);
bHasNext &= (currentIndexes[ sequences.size() - 1 ] + 1 < sequenceLengths[ sequences.size() - 1 ]);
return bHasNext;
}

// Rest the counters so we can produce the same sequence again
void reset()
{
for ( int index = 0; index < sequences.size(); ++index )
currentIndexes[ index ] = 0;
}

private:
QVector< QStringList > sequences;
QVector< int > sequenceLengths;
QVector< int > currentIndexes;
};


Haven't compiled or tested this, so use at your own risk.

If you want to "recycle" the sequence, then just rewrite hasNext() to always return true, and the next() method will simply reset all the indexes to zero once it reaches the end and start over. If you wanted to start at a random place in the sequence instead of always at the beginning, you could write a randomize() method that sets each of the currentIndexes[n] entries to a random number between zero and sequences[n].size() - 1.

You could also implement hasNext() to simply multiply all of the currentIndexes[n] values together and all of the sequenceLength[n] together. If the total for the first product is less than the total for the second, then hasNext() is true. However, if the number of sequences that can be generated is very large, then this could overflow the size of an int or long and give an incorrect result. The way I implemented it is less efficient but will never overflow.

d_stranz
22nd March 2012, 05:33
@kalma: I know you've read this. You're welcome.