Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
261 views
in Technique[技术] by (71.8m points)

c# - Unique combinations of list

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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?


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...