مولد الجمع بين لينك

Question

هل من الممكن إنشاء بعض LINQ الذي ينشئ قائمة تحتوي على جميع المجموعات الممكنة لسلسلة من الأرقام؟

إذا قمت بإدخال "21"، فستندد قائمة بالعناصر:

list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"

(ليس بالتنسيق في هذا النظام)

أنا أفهم أنه يمكنك استخدام مجموعة للقيام بأشياء مثل:

List<char> letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations

الذي يولد الأبجدية من الألف إلى الياء. لكن لا يمكنني نقل هذه المعرفة لإنشاء مولد تركيبة

لقد تمكنت من معرفة ذلك مع التعليمات البرمجية التالية، ولكن يبدو الأمر ضخما للغاية وأنا متأكد من أنه يمكن القيام به مع بعض الأسطر. حقا تشعر وكأنه حل سيء صنعته.

تخيل أنني اتصلت GetAllCombinations("4321") إذا كان يساعد

public static String[] GetAllCombinations(String s)
{
    var combinations = new string[PossibleCombinations(s.Length)];

    int n = PossibleCombinations(s.Length - 1);

    for (int i = 0; i < s.Length; i++)
    {
        String sub;
        String[] subs;

        if (i == 0)
        {
            sub = s.Substring(1); //Get the first number
        }
        else if (i == s.Length - 1)
        {
            sub = s.Substring(0, s.Length - 1);
        }
        else
        {
            sub = s.Substring(0, i) + s.Substring(i + 1); 
        }

        subs = GetAllCombinations(sub);

        for (int j = 0; j < subs.Length; j++)
        {
            combinations[i * n + j] = s[i] + subs[j];
        }
    }

    return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
    int result = 1;

    for (int i = 1; i <= n; i++)
        result *= i;

    return result;
}

Answer 1

لماذا يستحق، جرب شيئا مثل هذا:

public static IEnumerable<string> GetPermutations(string s)
{
    if (s.Length > 1)
        return from ch in s
               from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
               select string.Format("{0}{1}", ch, permutation);

    else
        return new string[] { s };
}

Answer 2

للسجل: جوش الإجابة بطريقة عامة:

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
        if (items.Count() > 1) {
            return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
                                   (item, permutation) => new[] { item }.Concat(permutation));
        } else {
            return new[] {items};
        }
    }

Answer 3

إليك إلقاء علوي ووظيفتي باستخدام LinQ

public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
    if (source == null)
        throw new ArgumentNullException("source");

    yield return item;

    foreach (var element in source)
        yield return element;
}

public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();

    if (list.Count > 1)
        return from s in list
                from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                select p.Prepend(s);

    return new[] { list };
}

public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();
    if (k > list.Count)
        throw new ArgumentOutOfRangeException("k");

    if (k == 0)
        yield return Enumerable.Empty<TSource>();

    foreach (var l in list)
        foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
            yield return c.Prepend(l);
}

بالنسبة للأبجدية الحمضية "A"، "C"، "G"، 'T':

var dna = new[] {'A', 'C', 'G', 'T'};

foreach (var p in dna.Permutate())
    Console.WriteLine(String.Concat(p));

اعطي

ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA

والتركيبات (ك = 2) من الحمض النووي الأبجدية

foreach (var c in dna.Combinate(2))
        Console.WriteLine(String.Concat(c));

نكون

AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT

Answer 4

ما تبحث عنه هو في الواقع التباديل. باختصار، بتصريحات تعني أن الطلبات ذات صلة (أي، 12 يختلف عن 21) في حين أن تركيبة تعني النظام غير ذي صلة (12 و 21 معادلة). لمزيد من المعلومات، راجع ويكيبيديا.

يرى هذا الموضوع.

أما بالنسبة للقيام، فإن Linq نقي، وهذا يبدو وكأنه استخدام LinQ من أجل استخدام LinQ.

Answer 5

كما أشار آخرون إلى حلول هذه الصفحة سوف تولد تكرارات إذا كانت أي من العناصر هي نفسها. سيقوم الملحق المتميز () بإزالةها، لكنها ليست قابلة للتحجيم للغاية لأنها ستؤدي عادة إلى اجتياز شجرة البحث بأكملها على أي حال. سوف تقليم مساحة البحث بشكل كبير عن طريق استدعاءها أثناء اجتيازها:

private static IEnumerable<string> Permute(string str)
{
    if (str.Length == 0)
        yield return "";
    else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
        foreach (var p in Permute(str.Remove(index, 1)))
            yield return str[index] + p;
}

بالنسبة إلى سلسلة المثال "Bananabana" هذا يؤدي إلى 8،294 العقد التي تمت زيارتها، بدلا من 9،864،101 تمت زيارتها عندما لا تقوم بعمل اجتياز العلاج.

Answer 6

يمكنك استخدام هذا الملحق LINQ الملخص:

foreach (var value in Enumerable.Range(1,3).Permute())
  Console.WriteLine(String.Join(",", value));

مما يؤدي إلى هذا:

1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...

يمكنك اختياريا تحديد رقم التبادلات

foreach (var value in Enumerable.Range(1,2).Permute(4))
  Console.WriteLine(String.Join(",", value));

نتائج:

1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2

فئة الإرشاد لإضافة:

public static class IEnumberableExtensions
{
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}