Sign in to follow this  
Code-R

Generating all the possible permutations

Recommended Posts

Code-R    136
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 this post


Link to post
Share on other sites
stylin    758
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 this post


Link to post
Share on other sites
Ilici    862
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 this post


Link to post
Share on other sites
Extrarius    1412
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 examples
typedef unsigned long TBigNumber;

//TSymbolIndex is used to index TSymbolVector
//Must be signed so it can be used in backwards loops
typedef long TSymbolIndex;
//TSymbolVector is used to return vectors of symbols
typedef std::vector<TSymbolIndex> TSymbolVector;
//Position is used to index sequences
typedef 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 this post


Link to post
Share on other sites
Code-R    136
Quote:
Original post by stylin
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.


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

Thanks everyone, Ratings were given as due.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this