Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Permutations, Combinations, and Variations using C# Generics

, 23 May 2008
Discusses the six major types of combinatorial collections, with examples and formulas for counting. Expands with a C# Generics-based set of classes for enumerating each meta-collection.
combinatoricssample.zip
CombinatoricsSample
TextSumProblemSample
bin
Debug
Release
Combinatorics
Facet.ico
obj
Debug
Refactor
TempPE
Release
TempPE
Properties
Settings.settings
TextSumProblemSample.csproj.user
textsumproblemsample.zip
// Copyright 2008 Adrian Akison
// Distributed under license terms of CPOL http://www.codeproject.com/info/cpol10.aspx
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Facet.Combinatorics {
    /// <summary>
    /// Utility class that maintains a small table of prime numbers and provides
    /// simple implementations of Prime Factorization algorithms.  
    /// This is a quick and dirty utility class to support calculations of permutation
    /// sets with indexes under 2^31.
    /// The prime table contains all primes up to Sqrt(2^31) which are all of the primes
    /// requires to factorize any Int32 positive integer.
    /// </summary>
    public class SmallPrimeUtility {
        /// <summary>
        /// Utility class, no instances allowed.
        /// </summary>
        private SmallPrimeUtility() {
            ;
        }

        /// <summary>
        /// Performs a prime factorization of a given integer using the table of primes in PrimeTable.
        /// Since this will only factor Int32 sized integers, a simple list of factors is returned instead
        /// of the more scalable, but more difficult to consume, list of primes and associated exponents.
        /// </summary>
        /// <param name="i">The number to factorize, must be positive.</param>
        /// <returns>A simple list of factors.</returns>
        public static List<int> Factor(int i) {
            int primeIndex = 0;
            int prime = PrimeTable[primeIndex];
            List<int> factors = new List<int>();
            while(i > 1) {
                if(i % prime == 0) {
                    factors.Add(prime);
                    i /= prime;
                }
                else {
                    ++primeIndex;
                    prime = PrimeTable[primeIndex];
                }
            }
            return factors;
        }

        /// <summary>
        /// Given two integers expressed as a list of prime factors, multiplies these numbers
        /// together and returns an integer also expressed as a set of prime factors.
        /// This allows multiplication to overflow well beyond a Int64 if necessary.  
        /// </summary>
        /// <param name="lhs">Left Hand Side argument, expressed as list of prime factors.</param>
        /// <param name="rhs">Right Hand Side argument, expressed as list of prime factors.</param>
        /// <returns>Product, expressed as list of prime factors.</returns>
        public static List<int> MultiplyPrimeFactors(IList<int> lhs, IList<int> rhs) {
            List<int> product = new List<int>();
            foreach(int prime in lhs) {
                product.Add(prime);
            }
            foreach(int prime in rhs) {
                product.Add(prime);
            }
            product.Sort();
            return product;
        }

        /// <summary>
        /// Given two integers expressed as a list of prime factors, divides these numbers
        /// and returns an integer also expressed as a set of prime factors.
        /// If the result is not a integer, then the result is undefined.  That is, 11 / 5
        /// when divided by this function will not yield a correct result.
        /// As such, this function is ONLY useful for division with combinatorial results where 
        /// the result is known to be an integer AND the division occurs as the last operation(s).
        /// </summary>
        /// <param name="numerator">Numerator argument, expressed as list of prime factors.</param>
        /// <param name="denominator">Denominator argument, expressed as list of prime factors.</param>
        /// <returns>Resultant, expressed as list of prime factors.</returns>
        public static List<int> DividePrimeFactors(IList<int> numerator, IList<int> denominator) {
            List<int> product = new List<int>();
            foreach(int prime in numerator) {
                product.Add(prime);
            }
            foreach(int prime in denominator) {
                product.Remove(prime);
            }
            return product;
        }

        /// <summary>
        /// Given a list of prime factors returns the long representation.
        /// </summary>
        /// <param name="value">Integer, expressed as list of prime factors.</param>
        /// <returns>Standard long representation.</returns>
        public static long EvaluatePrimeFactors(IList<int> value) {
            long accumulator = 1;
            foreach(int prime in value) {
                accumulator *= prime;
            }
            return accumulator;
        }

        /// <summary>
        /// Static initializer, set up prime table.
        /// </summary>
        static SmallPrimeUtility() {
            CalculatePrimes();
        }

        /// <summary>
        /// Calculate all primes up to Sqrt(2^32) = 2^16.  
        /// This table will be large enough for all factorizations for Int32's.
        /// Small tables are best built using the Sieve Of Eratosthenes,
        /// Reference: http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
        /// </summary>
        private static void CalculatePrimes() {
            // Build Sieve Of Eratosthenes
            BitArray sieve = new BitArray(65536, true);
            for(int possiblePrime = 2; possiblePrime <= 256; ++possiblePrime) {
                if(sieve[possiblePrime] == true) {
                    // It is prime, so remove all future factors...
                    for(int nonPrime = 2 * possiblePrime; nonPrime < 65536; nonPrime += possiblePrime) {
                        sieve[nonPrime] = false;
                    }
                }
            }
            // Scan sieve for primes...
            myPrimes = new List<int>();
            for(int i = 2; i < 65536; ++i) {
                if(sieve[i] == true) {
                    myPrimes.Add(i);
                }
            }

        }

        /// <summary>
        /// A List of all primes from 2 to 2^16.
        /// </summary>
        public static IList<int> PrimeTable {
            get {
                return myPrimes;
            }
        }

        private static List<int> myPrimes = new List<int>();

    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Adrian Akison
Program Manager SMS Management & Technology
Australia Australia
I have been a professional software developer for twenty years, starting with C++ and migrated to C#. While I have transitioned into full time management, writing code is still my passion. As I don't write code for work very often, I have had the opportunity to apply my programming skills as a hobby where I have recently authored two Windows 8 store apps. First, an Asteroids tribute game, 'Roid Rage and most recently Shared Whiteboard (which does what it says).
 
I make a habit of contributing production code to every project I run. Most notably, I have recently run teams to build The Navigator for The Advertiser newspaper and Street Lights Out for SA Power Networks.
Follow on   Twitter

| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 23 May 2008
Article Copyright 2008 by Adrian Akison
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid