13,146,014 members (44,839 online)

#### Stats

418.7K views
204 bookmarked
Posted 13 May 2008

# 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 TextSumProblemSample bin Debug Release Combinatorics Facet.ico obj Debug Refactor TempPE Release TempPE Properties TextSumProblemSample.csproj.user TextSumProblemSample.exe ```// 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 { /// /// 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. /// public class SmallPrimeUtility { /// /// Utility class, no instances allowed. /// private SmallPrimeUtility() { ; } /// /// 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. /// /// The number to factorize, must be positive. /// A simple list of factors. public static List Factor(int i) { int primeIndex = 0; int prime = PrimeTable[primeIndex]; List factors = new List(); while(i > 1) { if(i % prime == 0) { factors.Add(prime); i /= prime; } else { ++primeIndex; prime = PrimeTable[primeIndex]; } } return factors; } /// /// 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. /// /// Left Hand Side argument, expressed as list of prime factors. /// Right Hand Side argument, expressed as list of prime factors. /// Product, expressed as list of prime factors. public static List MultiplyPrimeFactors(IList lhs, IList rhs) { List product = new List(); foreach(int prime in lhs) { product.Add(prime); } foreach(int prime in rhs) { product.Add(prime); } product.Sort(); return product; } /// /// 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). /// /// Numerator argument, expressed as list of prime factors. /// Denominator argument, expressed as list of prime factors. /// Resultant, expressed as list of prime factors. public static List DividePrimeFactors(IList numerator, IList denominator) { List product = new List(); foreach(int prime in numerator) { product.Add(prime); } foreach(int prime in denominator) { product.Remove(prime); } return product; } /// /// Given a list of prime factors returns the long representation. /// /// Integer, expressed as list of prime factors. /// Standard long representation. public static long EvaluatePrimeFactors(IList value) { long accumulator = 1; foreach(int prime in value) { accumulator *= prime; } return accumulator; } /// /// Static initializer, set up prime table. /// static SmallPrimeUtility() { CalculatePrimes(); } /// /// 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 /// 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(); for(int i = 2; i < 65536; ++i) { if(sieve[i] == true) { myPrimes.Add(i); } } } /// /// A List of all primes from 2 to 2^16. /// public static IList PrimeTable { get { return myPrimes; } } private static List myPrimes = new List(); } } ```

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.

## Share

 Team Leader Zuuse Pty Ltd 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.

## You may also be interested in...

 Pro Pro