Using Qt to generate stringlist combinations

[kalma]

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]

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;
};

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;
};

To copy to clipboard, switch view to plain text mode 

[kalma]

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]

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;
};

// 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;
};

To copy to clipboard, switch view to plain text mode 

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]

@kalma: I know you've read this. You're welcome.