Trouble converting to use recursion

Question

I have a piece of code that uses nested loops to creates a linq expression that compares every possibility of bool combination in the object Paint. It works perfectly, but if I want to continue adding Properties to Paint, I will have to continue adding for loops to the process. I would like to convert this to use recursion but I am having trouble with that. Can anyone offer some insight/a starting point for this?

ParameterExpression param = Expression.Parameter(typeof(Paint), "t");

Expression exp = null;

object f = false;
object t = true;

List<Expression> expList = new List<Expression>();

//Properties to compare
MemberExpression memberA = Expression.Property(param, "BoolA");
MemberExpression memberB = Expression.Property(param, "BoolB");
MemberExpression memberC = Expression.Property(param, "BoolC");
MemberExpression memberD = Expression.Property(param, "BoolD");

//Loop 3 times to create expression using BoolA == true, BoolA == false, do not use BoolA
for(int aa = 0; aa <= 2; aa++)
{
    Expression aExp = null;

    if (aa == 0)
    {
        aExp = Expression.Equal(memberA, Expression.Constant(f));
        expList.Add(aExp);
    }
    if(aa == 1)
    {
        aExp = Expression.Equal(memberA, Expression.Constant(t));
        expList.Add(aExp);
    }

    for (int bb = 0; bb <= 2; bb++)
    {
        Expression bExp = null;

        if (bb == 0)
        {
            bExp = Expression.Equal(memberB, Expression.Constant(f));
            expList.Add(bExp);
        }
        if (bb == 1)
        {
            bExp = Expression.Equal(memberB, Expression.Constant(t));
            expList.Add(bExp);
        }

        for(int cc = 0; cc <= 2; cc++)
        {
            Expression cExp = null;

            if (cc == 0)
            {
                cExp = Expression.Equal(memberC, Expression.Constant(f));
                expList.Add(cExp);
            }
            if(cc == 1)
            {
                cExp = Expression.Equal(memberC, Expression.Constant(t));
                expList.Add(cExp);
            }

            for (int dd = 0; dd <= 2; dd++)
            {
                Expression dExp = null;

                if (dd == 0)
                {
                    dExp = Expression.Equal(membeDr, Expression.Constant(f));
                    expList.Add(dExp);
                }
                if (dd == 1)
                {
                    dExp = Expression.Equal(memberD, Expression.Constant(t));
                    expList.Add(dExp);
                }

                //Process expList

                //remove expression to prepare to add its opposite in its place
                expList.Remove(dExp);
            }
            expList.Remove(cExp);
        }
        expList.Remove(bExp);
    }
    expList.Remove(aExp);
}

Answer 1

You don't need recursion to implement this, nor the nested loops. I originally misread the question and thought you were just doing true/false, i.e. two states per property. Had that been the case, you could have taken advantage of the convenience of binary arithmetic to let a regular integer counter handle the enumeration of states.

However, even without that convenience, it's not too bad. It's still the same basic technique, but you simply wind up doing something more similar to the abstraction I mentioned as a requirement when the property count is higher than 63.

First, we need that abstracted counter class. Here's a version that uses byte counters, which is overkill in terms of per-property states (supports 256 states instead of just the 3 you need), but makes the implementation a lot easier than packing multiple counters into a byte or other type:

class MultiCounter
{
    private int _counterMax;
    private byte[] _counters;

    public MultiCounter(int counterCount, int counterMax)
    {
        _counterMax = counterMax;
        _counters = new byte[counterCount];
    }

    public bool Increment()
    {
        for (int i = 0; i < _counters.Length; i++)
        {
            if (++_counters[i] < _counterMax)
            {
                return true;
            }

            _counters[i] = 0;
        }

        return false;
    }

    public int this[int index] { get { return _counters[index]; } }
}

The above maintains the set of counters as if each counter were a digit in base counterMax of a number with counterCount digits. The Increment() method increments this base-counterMax number, returning true until it overflows, which allows the caller to know when all of the possible combinations are done.

An indexer provides a convenient way to read each digit.

Now, we can use this helper class to implement the actual Expression enumeration:

MemberExpression[] memberExpressions = 
{
    Expression.Property(param, "BoolA"),
    Expression.Property(param, "BoolB"),
    Expression.Property(param, "BoolC"),
    Expression.Property(param, "BoolD"),
};

MultiCounter multiCounter = new MultiCounter(memberExpressions.Length, 3);

List<Expression> expList = new List<Expression>(memberExpressions.Length);

do
{
    expList.Clear();

    for (int index = 0; index < memberExpressions.Length; index++)
    {
        int propertyCounter = multiCounter[index];

        if (propertyCounter == 2)
        {
            continue;
        }

        expList.Add(Expression.Equal(
            memberExpressions[index],
            Expression.Constant(propertyCounter == 1)));
    }

    // Process expList here

} while (multiCounter.Increment());

(Apologies in advance for typos or other errors…the above is still just typed into my browser for illustration purposes).

In other words, for N Boolean properties, you have 3^N possible combinations, including the option to ignore the property altogether. So simply iterate a count from 0 to 3^N - 1, using the MultiCounter class to maintain this base-3 number.

While this is not quite as convenient as if you had just the two states, one nice thing is that having done the extra work, now you have no significant limitation on the number of properties you can manage. To reach the 2GB limitation of the array in the MultiCounter implementation, i.e. to have 2+ billion properties, you'd have to somehow get around a number of other fundamental limitations first. :)