# Generating all the possible permutations

This topic is 4504 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

One of the things I'm doing is generating shaders depending on the current light/surface situation. say, I could have 3 lights, light 1 could be point, 2 spot, 3 point; or 1,2 and 3 point, etc. now, let's say I have the following:
vector<light> MyLights;

and I have 3 light types. how can I generate vector<vector<light> > AllPossibleCases; as in AllCases will have, amongst the many others, one of its vectors where there're 2 point lights; 3 directional and 4 point (in different orders), etc, all possible permutations, so I can generate my shaders and compile them once at initialization time?

##### Share on other sites
http://www.andrews.edu/~calkins/math/webtexts/prod02.htm

For actually creating them, simply count from 0 to MAX_LIGHTS in base 3 (3 kinds of light):
   1   2   3   11   12   13   21   22   23   ...   etc.

##### Share on other sites
std::next_permutation may possibly help you out. Extremely useful little function, that.

*edit: nevermind. That won't help you at all. You just want a series of nested loops.

CM

##### Share on other sites
I'd guess you have to use a back-tracking algorithm:

Keep a stack onto which you add the elements from the original vector. Scan the original vector and push elements while they are valid (they are not on the stack yet), if you run out of elements either pop the last element of the stack if the stack is not yet full or if it's full you've got a solution which you keep in your solution array. Google for back-tracking generating permutations.

##### Share on other sites
What you want is a range sequence. I'm currently editing an article about them, but for now I'll post some source code:
//TBigNumber is used to store large values and might need to be redefined//An arbitrary length integer class would be a good idea//If TBigNumber is 32 bits, it can only hold up to 13!//Luckily, that is plenty for the examplestypedef unsigned long TBigNumber;//TSymbolIndex is used to index TSymbolVector//Must be signed so it can be used in backwards loopstypedef long TSymbolIndex;//TSymbolVector is used to return vectors of symbolstypedef std::vector<TSymbolIndex> TSymbolVector;//Position is used to index sequencestypedef TBigNumber TPosition;//-----//Range value must be greater than 0 (1 means one possible value, 2 means two choices, etc)typedef unsigned long TRange;typedef std::vector<TRange> TRangeVector;class TRangeSequenceIndexer{	//SymbolCount stores the number of symbols that make up the range sequence	TSymbolIndex m_SymbolCount;	//Ranges stores the valid ranges for each symbol	TRangeVector m_Ranges;	//SequenceLength stores the length of the sequence	TPosition m_SequenceLength;public:	TRangeSequenceIndexer(): m_SequenceLength(0), m_SymbolCount(0)	{	}	//Ranges[] should not have any elements that are 0	void SetRanges(const TRange* Ranges, const TSymbolIndex SymbolCount)	{		//Initialize 		m_SymbolCount = SymbolCount;		m_Ranges.clear();		m_Ranges.reserve(m_SymbolCount);		//Copy the ranges to the range sequence and calculate the sequence length		m_SequenceLength = 1;		for(TSymbolIndex WhichSymbol = 0; WhichSymbol < m_SymbolCount; ++WhichSymbol)		{			//store each range value			m_Ranges.push_back(Ranges[WhichSymbol]);			//the length is the product of all ranges			m_SequenceLength *= Ranges[WhichSymbol];		}	}	//returns sequent # SequenceIndex	TSymbolVector GetAt(TPosition SequenceIndex) const	{		//If the Index requested isn't in the sequence, return empty vector		if((SequenceIndex < 0) || (SequenceIndex >= m_SequenceLength))		{			return TSymbolVector();		}		//Calculate the sequence requested		TSymbolVector SymbolValues(m_SymbolCount);		//Start with the last symbol, work right toward the first symbol		for(TSymbolIndex WhichSymbol = (m_SymbolCount - 1); WhichSymbol >= 0; --WhichSymbol)		{			//Find the symbol's value using modulus			SymbolValues[WhichSymbol] = SequenceIndex % m_Ranges[WhichSymbol];			//Adjust the index for the symbol to be processed			SequenceIndex = SequenceIndex / m_Ranges[WhichSymbol];		}		return SymbolValues;	}	//returns index of the given Sequent, or TPosition(-1) for error	//If any of the symbols in the sequent are out of range, return value is undefined	TPosition GetIndexOf(const TSymbolVector& Sequent) const	{		//If there isn't a sequence stored in this class,		// or the given sequence isn't the proper size, return error		if((m_SequenceLength == 0) || (Sequent.size() != m_SymbolCount))		{			return TPosition(-1);		}		//Initialize the index to the first position		TPosition Index = 0;		//Calculate the index of the given sequence		//Start with the first symbol, work left to the last symbol		for(TSymbolIndex WhichSymbol = 0; WhichSymbol < m_SymbolCount; ++WhichSymbol)		{			//Verify that the current symbol is in range or return error			if((Sequent[WhichSymbol] < 0) || (TRange(Sequent[WhichSymbol]) >= m_Ranges[WhichSymbol]))			{				return TPosition(-1);			}			//Adjust the index to take this symbol into account			Index = Index * m_Ranges[WhichSymbol] + Sequent[WhichSymbol];		}				return Index;	}	const TSymbolIndex& SymbolCount() const	{		//return the stored symbol count		return m_SymbolCount;	}	const TPosition& SequenceLength() const	{		//return the stored sequence length		return m_SequenceLength;	}};//class TRangeSequenceIndexer

##### Share on other sites
Quote:
 Original post by stylinhttp://www.andrews.edu/~calkins/math/webtexts/prod02.htmFor actually creating them, simply count from 0 to MAX_LIGHTS in base 3 (3 kinds of light): 1 2 3 11 12 13 21 22 23 ... etc.

Thanks! This seems to be the easiest of all solutions! Rating++!

Thanks everyone, Ratings were given as due.