What is the best way to find all combinations of items in an array?

by

UPDATED

Here are a set of generic functions (require .net 3.5 or higher) for different scenarios. The outputs are for a list of {1, 2, 3, 4} and a length of 2.

Permutations with repetition

static IEnumerable<IEnumerable<T>> 
    GetPermutationsWithRept<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutationsWithRept(list, length - 1)
        .SelectMany(t => list, 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Output:

{1,1} {1,2} {1,3} {1,4} {2,1} {2,2} {2,3} {2,4} {3,1} {3,2} {3,3} {3,4} {4,1} {4,2} {4,3} {4,4}

Permutations

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(o => !t.Contains(o)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Output:

{1,2} {1,3} {1,4} {2,1} {2,3} {2,4} {3,1} {3,2} {3,4} {4,1} {4,2} {4,3}

K-combinations with repetition

static IEnumerable<IEnumerable<T>> 
    GetKCombsWithRept<T>(IEnumerable<T> list, int length) where T : IComparable
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetKCombsWithRept(list, length - 1)
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Output:

{1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4}

K-combinations

static IEnumerable<IEnumerable<T>> 
    GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetKCombs(list, length - 1)
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Output:

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

More Related Contents:

  1. I am interested in a more optimized solution for sum of all fizzbuzz numbers in a given range
  2. Different combinations of an array (C#)
  3. Algorithm to detect overlapping periods [duplicate]
  4. All Possible Combinations of a list of Values
  5. Select N random elements from a List in C#
  6. How to find all partitions of a set
  7. Quick and Simple Hash Code Combinations
  8. Remove text in-between delimiters in a string (using a regex?)
  9. Algorithm to find which numbers from a list of size n sum to another number
  10. How to “zip” or “rotate” a variable number of lists?
  11. C# hashcode for array of ints
  12. Detect if geolocation is in complex polygon or not
  13. How to create a trie in c# [closed]
  14. Efficient Cartesian Product algorithm
  15. Finding all combinations of well-formed brackets
  16. Best hashing algorithm in terms of hash collisions and performance for strings
  17. LINQ to find series of consecutive numbers
  18. Reversible shuffle algorithm using a key
  19. DirectoryInfo.EnumerateFiles(…) causes UnauthorizedAccessException (and other exceptions)
  20. C#: Seeking PNG Compression algorithm/library [closed]
  21. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  22. Find if point lies on line segment
  23. What’s the quickest way to compute log2 of an integer in C#?
  24. Flood Fill Algorithms
  25. Creating a power set of a Sequence
  26. All cases covered Bresenham’s line-algorithm [closed]
  27. Sorting a linked list
  28. How is a random number generated at runtime?
  29. Best algorithm for evaluating a mathematical expression?
  30. Implementing Luhn algorithm using C#

Leave a Comment