Unique list combinations

Question

The absolute mind is empty. It was one of those days. But I was looking for a solution to get unique combinations of a list of items of a certain length. for example, given the list of [a, b, c] and length 2, it will return [a, b] [a, c] [b, c], but not [b, a] [c, a] [c, b]

I found a lot of code snippets for this, but none of them work. The following code seemed most appropriate, and I tried to change it for my needs:

// Returns an enumeration of enumerators, one for each permutation // of the input. public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count) { if (count == 0) { yield return new T[0]; } else { int startingElementIndex = 0; foreach (T startingElement in list) { IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex); foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1)) { yield return Concat<T>( new T[] { startingElement }, permutationOfRemainder); } startingElementIndex += 1; } } } // Enumerates over contents of both lists. public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b) { foreach (T item in a) { yield return item; } foreach (T item in b) { yield return item; } } // Enumerates over all items in the input, skipping over the item // with the specified offset. public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip) { int index = 0; foreach (T item in input) { if (index != indexToSkip) yield return item; index += 1; } } 

This does what it should do, but returns ALL permutations, regardless of whether they are unique. I tried to figure out which part, if any, to modify this code to get unique values. Or is this the best way to implement this functionality?

Answer 1

The list of remaining elements in the implementation contains all elements except the current initial element.

Get the elements that are after the original element:

 IEnumerable<T> remainingItems = list.Skip(startingElementIndex + 1); 

Answer 2

Try the following:

 void Main() { var list = new List<string> { "a", "b", "c", "d", "e" }; var result = GetPermutations(list, 3); } IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count) { int i = 0; foreach(var item in items) { if(count == 1) yield return new T[] { item }; else { foreach(var result in GetPermutations(items.Skip(i + 1), count - 1)) yield return new T[] { item }.Concat(result); } ++i; } } 

For counting 2, it returns this:

 a, b a, c a, d a, e b, c b, d b, e c, d c, e d, e 

For counting 3, it returns this:

 a, b, c a, b, d a, b, e a, c, d a, c, e a, d, e b, c, d b, c, e b, d, ec, d, e 

Is that what you expect?

Answer 3

Instead of AllExcept, you should use a subsequence that only gives you the elements after what you are considering.

Answer 4

In set-speak mode, what you are looking for is a subset of the power set based on length n. If you do a Google search for "C #" + "Power set", which should give you a lot of options to get started.

http://en.wikipedia.org/wiki/Power_set

Answer 5

and just for completeness. If you already have all the permutations (:) and because it is just a copy and paste for me) using the extension methods below you can get different results as follows:

 var result = permutations.Distinct((p1, p2) => !p1.Differs(p2)); 

just an example, and if you work a lot with comparing lists, other methods may be useful elsewhere.

 public static class Extensionmethods { /// <summary> /// Checks if both IEnumerables contain the same values regardless of their sequence /// </summary> /// <typeparam name="T">Type of Elements</typeparam> /// <param name="result">IEnumerable to compare to</param> /// <param name="compare">IEnumerable to compare to</param> /// <returns>Returns false if both IEnumerables contain the same values</returns> public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare) { if (result == null && compare == null) return false; if (result != null && compare == null) return true; if (result == null && compare != null) return true; return result.Count() != compare.Count() || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => item.Equals(r)).Count() != compare.Where(r => item.Equals(r)).Count()); } /// <summary> /// Checks if both IEnumerables contain the same values (corresponding to <paramref name="comparer"/> regardless of their sequence /// </summary> /// <typeparam name="T">Type of Elements</typeparam> /// <param name="result">IEnumerable to compare to</param> /// <param name="compare">IEnumerable to compare to</param> /// <param name="comparer">IEqualityComparer to use</param> /// <returns>Returns false if both IEnumerables contain the same values</returns> public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare, IEqualityComparer<T> comparer) { if (result == null && compare == null) return false; if (result != null && compare == null) return true; if (result == null && compare != null) return true; return result.Count() != compare.Count() || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => comparer.Equals(item, r)).Count() != compare.Where(r => comparer.Equals(item, r)).Count()); } public static IEnumerable<T> Distinct<T>(this IEnumerable<T> source, Func<T, T, bool> compareFunction, Func<T, int> hashFunction = null) { var ecomparer = new DynamicEqualityComparer<T>(compareFunction, hashFunction); return source.Distinct(ecomparer); } } internal class DynamicEqualityComparer<T> : IEqualityComparer<T> { public DynamicEqualityComparer(Func<T, T, bool> equalFunction, Func<T, int> hashFunction = null) { this.equalFunc = equalFunction; this.hashFunc = hashFunction; } private Func<T, T, bool> equalFunc; public bool Equals(T x, T y) { if (x == null && y == null) return true; if (x == null) return false; if (y == null) return false; if (hashFunc != null) { if (hashFunc.Invoke(x) != hashFunc.Invoke(y)) return false; } return this.equalFunc.Invoke(x, y); } private Func<T, int> hashFunc; public int GetHashCode(T obj) { if (hashFunc != null) return hashFunc.Invoke(obj); return 0; } } 

Answer 6

I tried all the methods described above, but could not, because they ate a lot of Ram and crashed if there was more input. But I have a very simple solution for this:

 class Program { static List<string> textArr = new List<string>() { "1", "2", "3", "4" }; static void Main(string[] args) { getCombination(); } static void getCombination() { var maxCombination = 1; List<string> Combinations = new List<string>(); for (var i = 1; i <= textArr.Count(); i++) { maxCombination = maxCombination * i; } while (Combinations.Count<maxCombination) { var temp = string.Join(" ", textArr.OrderBy(x => Guid.NewGuid()).ToList()); if (Combinations.Contains(temp)) { continue; } else { Combinations.Add(temp); } } Combinations.ForEach(x => { Console.WriteLine(x+" "); }); } }