Programming Stuff : .Net Examples : Fun With Permutations and Bit Shift

The Issue: I have an order with mutiple items on it. I have a list of template objects that represent possible orders. I need to find all the unique permutations of those items on the order that fall between our minimum and maximum count of items. The results are to be used to see if a combination of items matches any templates that defines a discount. You may have multiple discounts per order, but only one discount per item.

The Solution: Instead of looping over a List, I use an array so that the order will stay the same, and then build permutations of the index values instead of the objects themselves. I take the length of my array and turn it into a maximum uint value for a binary with that many digits. After that, I loop over the uint value that acts as a bitmask for what index to include for a permutation. If the number of indexes in a permutation are within my min and max values, I add it to the return list of valid index permutations.

        /// <summary>
        /// Find every possible permutation of item indexes that are provided.
        /// </summary>
        /// <param name="indexes">All of the possible item indexes that can be used.</param>
        /// <param name="min">The minimum number of items required.</param>
        /// <param name="max">The maximum number of items required.</param>
        /// <returns></returns>
        private List<List<int>> Combos(int[] indexes, int min, int? max)
        {
            // I have an array where I want every possible combination of the indexes for the array.
            // The order of the indexes does not matter, only how they are combined.
            // For example the array elements specified by indexes 1, 2, and 3 are equal
            // to the indexes 3, 2, and 1 so I only want the distinct combination.

            int numOfElements = indexes.Length;
            // This needs to be tested to make sure the index length isn't higher than 32.
            // It takes too long with that many items anyhow.
            if (numOfElements > 32)
            {
                throw new ArgumentException("Cannot have more than 32 items.");
            }

            // Bitmask to the rescue.
            // I know how many elements I have. If I treat each of of the elements as a true/false,
            // I can create a bitmask from it that is the length of the number of elements.
            // Then I can represent the max value as an uint which would be all items and loop
            // over all the values. KAKOW!

            uint combos; // max number of permutations.
            double tmp = Math.Pow(2, numOfElements) - 1; // Minus one for the 0 value.

            if (tmp > uint.MaxValue) // This shouldn't happen. Better safe than sorry.
            {
                combos = uint.MaxValue;
            }
            else
            {
                combos = Convert.ToUInt32(tmp);
            }

            // Declare these outside of the loop so we don't waste processor time and memory allocating
            // variables. // Which I later discovered the IL does for us.

            List<List<int>> itemIndexes = new List<List<int>>();
            List<int> tmpIndexes;

            uint i = 0; // outer loop
            int j = 0; // inner loop
            uint mybit = 0; // we will use this to determine whether to include an item index or not
            uint computed = 0; // the result of the logical and will go in this variable

            // for each digit representation of the bitmask
            for (i = 1; i <= combos; ++i)
            {
                // reset these variables for each possible combo.
                mybit = 0;
                tmpIndexes = new List<int>();
                // for each item index
                for (j = 0; j < numOfElements; ++j)
                {
                    mybit = 1u << j; // bit shift, this basically represents the index we are testing.
                    computed = i & mybit; // logical and
                    // if the binary represented by i has a bit set to true,
                    // and the binary represented by mybit also has that bit set to true,
                    // then the logical and of them should equal the value of mybit since mybit only
                    // has 1 binary place set to true at a time.
                    if (computed == mybit)
                    {
                        // This index is needed for this permutation, add it to the list.
                        tmpIndexes.Add(j);
                    }
                }
                // Is there a faster way to do this and eliminate it from the number of combos?
                if (tmpIndexes.Count() >= min && (!max.HasValue || max.Value >= tmpIndexes.Count()))
                {
                    // Meets the min and max requirements for distribution.
                    itemIndexes.Add(tmpIndexes);
                }
            }

            return itemIndexes;
        }