Unique combinations of list

Question

Absolute mind blank on this. It's been one of those days. But I have been looking for a solution for getting unique combinations of a list of items of a certain length. e.g., given a list [a, b, c] and a length of 2, it will return [a,b] [a,c] [b,c] but not [b,a] [c,a] [c,b]

For this I found numerous pieces of code, but none which seems to fit. The following code seemed best fit and I've been trying to alter 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 is supposed to do, but it returns ALL permutations, regardless of them being unique. I've tried to get my head around which piece, if any, of this code to change to get the unique values. Or is the a better way to implement this functionality?

Answer 1

I have tried all methods Above but failed because they were eating a lot of Ram and crash if input is larger. But i got a very very simple solution for that:

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+" ");
        });

    }
}

Answer 2

Try this:

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 a count of 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 a count of 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, e 
c, d, e

Is this what you expect?

Answer 3

and just for completeness .. if you already have all permutations ( :) and because its just a copy and paste for me ) with the extensionmethods below you can get distinct results like this:

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

just an example and if your working with comparing lists a lot the other methods may come in handy elsewhere too

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 4

In set-speak, what you're looking for is a subset of the power set based on length n. If you do a Google search for "C#" + "Power set" that should give you plenty to get started.

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

Answer 5

The remaining items list in the implementation contains all items except the current starting item.

Get the items that are after the starting item instead:

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

Answer 6

Instead of AllExcept, you should use a Subsequence that gives you only the items after the one you are considering.