10

これについては絶対に気にしないでください。それはその日の1つです。しかし、私は特定の長さのアイテムのリストのユニークな組み合わせを取得するための解決策を探していました。たとえば、リスト[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

セットスピークでは、探しているのは長さnに基づくべき集合のサブセットです。「C＃」+「Powerset」をGoogleで検索すると、開始するのに十分な情報が得られるはずです。

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

于 2012-09-03T13:53:47.880 に答える
0

完全を期すために..すでにすべての順列（:)があり、以下のextensionmethodsを使用してコピーアンドペーストするだけなので、次のような明確な結果を得ることができます。

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 に答える