10

对此绝对头脑一片空白。这是那些日子之一。但我一直在寻找一种解决方案来获得一定长度的项目列表的独特组合。例如，给定一个列表 [a, b, c] 和长度为 2，它将返回 [a,b] [a,c] [b,c] 但不返回 [b,a] [c,a] [c ,b]

为此，我发现了许多代码，但似乎没有一个适合。以下代码似乎最合适，我一直在尝试根据需要对其进行更改：

// 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;
    }
}

这完成了它应该做的事情，但它返回所有排列，不管它们是唯一的。我试图弄清楚这段代码的哪一部分（如果有的话）要更改以获得唯一值。或者是实现此功能的更好方法？

4

6 回答 6

20

尝试这个：

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;
    }
}

如果计数为 2，它会返回：

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

如果计数为 3，它会返回：

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

这是你所期望的吗？

于 2012-09-03T13:53:16.690 回答
3

实现中的剩余项目列表包含除当前起始项目之外的所有项目。

获取起始项目之后的项目：

IEnumerable<T> remainingItems = list.Skip(startingElementIndex + 1);
于 2012-09-03T13:50:21.130 回答
1

而不是 AllExcept，您应该使用仅提供您正在考虑的项目之后的项目的子序列。

于 2012-09-03T13:45:36.547 回答
1

在 set-speak 中，您正在寻找的是基于长度 n 的幂集的子集。如果您在 Google 上搜索“C#”+“Power set”，那么您应该可以开始大量使用。

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

于 2012-09-03T13:53:47.880 回答
0

并且只是为了完整性..如果您已经拥有所有排列（:)并且因为它只是对我的复制和粘贴）使用下面的扩展方法，您可以获得如下不同的结果：

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

只是一个例子，如果您经常使用比较列表，其他方法也可能在其他地方派上用场

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;
    }
}
于 2012-09-03T14:06:18.963 回答
0

我已经尝试了上面的所有方法，但失败了，因为如果输入较大，它们会吃掉很多 Ram 并且崩溃。但我有一个非常非常简单的解决方案：

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

    }
}
于 2019-07-29T06:46:59.890 回答