क्या आप सी # में सुंदरता के रूप में एक क्रमपरिवर्तन फ़ंक्शन लिख सकते हैं?

Question

मुझे यह 6 लाइन समाधान बहुत पसंद है और मैं इसे सी # में दोहराने की कोशिश कर रहा हूं। बिंदु मैं कुछ टिप्पणियों के बाद स्वीकार करना होगा करने के लिए पूरी तरह से नहीं

def permute(xs, pre=[]): 
    if len(xs) == 0: 
    yield pre 
    for i, x in enumerate(xs): 
    for y in permute(xs[:i] + xs[i+1:], pre + [x]): 
     yield y 

Answer 1

खैर, यह शायद नहीं है मैं इसे कैसे लिखना चाहते हैं, लेकिन:

static IEnumerable<T[]> Permute<T>(this T[] xs, params T[] pre) { 
    if (xs.Length == 0) yield return pre; 
    for (int i = 0; i < xs.Length; i++) { 
     foreach (T[] y in Permute(xs.Take(i).Union(xs.Skip(i+1)).ToArray(), pre.Union(new[] { xs[i] }).ToArray())) { 
      yield return y; 
     } 
    } 
} 

---

अपनी टिप्पणी पुन; मैं पूरी तरह से पर सवाल नहीं कर रहा हूं; अगर आपका मतलब है "यह उपयोगी क्यों है?" - अन्य चीजों के अलावा, ब्रूट-फोर्स परिदृश्यों की एक श्रृंखला है जहां आप विभिन्न क्रमपरिवर्तनों को आजमा सकते हैं - उदाहरण के लिए, छोटी बिक्री समस्याओं जैसे कि यात्रा करने वाले व्यक्ति (जो अधिक परिष्कृत समाधान की गारंटी देने के लिए पर्याप्त नहीं हैं) के लिए, आप हो सकता है कि यह जांचना चाहें कि {बेस, ए, बी, सी, बेस}, {बेस, ए, सी, बी, बेस}, {बेस, बी, ए, सी, बेस}, आदि

यदि आपका मतलब है "मैं इस विधि का उपयोग कैसे करूं?" - अनचाहे, लेकिन कुछ ऐसा:

int[] values = {1,2,3}; 
foreach(int[] perm in values.Permute()) { 
    WriteArray(perm); 
} 

void WriteArray<T>(T[] values) { 
    StringBuilder sb = new StringBuilder(); 
    foreach(T value in values) { 
     sb.Append(value).Append(", "); 
    } 
    Console.WriteLine(sb); 
} 

यदि आपका मतलब है "यह कैसे काम करता है?" - इटरेटर ब्लॉक (yield return) स्वयं में एक जटिल विषय हैं - जॉन के पास एक निशुल्क अध्याय (6) in his book है, हालांकि। शेष कोड आपके मूल प्रश्न की तरह बहुत अधिक है - केवल + (सरणी के लिए) के नैतिक समकक्ष प्रदान करने के लिए LINQ का उपयोग करना।

Answer 2

, लेकिन नीचे कोड एक परिमित अनुक्रम का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करने के लिए इस्तेमाल किया जा सकता: असल में, यह एक सरणी के तत्वों permutes। यह Fisher-Yates shuffle algorithm का एक भिन्नता है। उदाहरण int के अनुक्रम का उपयोग करता है लेकिन आप निश्चित रूप से Enumerable<T> का उपयोग कर सकते हैं।

var ints = Enumerable.Range(0, 51); 
var shuffledInts = ints.OrderBy(a => Guid.NewGuid()); 

आपको एक यादृच्छिक मूल्य जो अनिवार्य रूप से अपनी सूची permutates (इस मामले में एक Guid में) द्वारा। चाहे NewGuid यादृच्छिकता का एक अच्छा स्रोत बहस योग्य है, लेकिन यह एक सुरुचिपूर्ण और कॉम्पैक्ट समाधान है (हालांकि किसी अन्य समस्या के लिए सवाल वास्तव में था)।

Jeff Atwood (Coding Horror) से लिया गया।

Answer 3

सी # में एक उपज कीवर्ड है जो मुझे लगता है कि आपके पायथन कोड क्या कर रहा है, उतना ही उतना ही काम करता है, इसलिए अधिकतर प्रत्यक्ष अनुवाद प्राप्त करना बहुत कठिन नहीं होना चाहिए।

हालांकि यह एक पुनरावर्ती समाधान है, इसलिए सभी के लिए यह अल्पसंख्यक है। मैं व्यक्तिगत रूप से शामिल सभी गणित को व्यक्तिगत रूप से समझ नहीं पा रहा हूं, लेकिन अच्छे कुशल गणितीय क्रमिकरणों के लिए आप factoradics का उपयोग करना चाहते हैं। इस लेख की मदद करनी चाहिए:
http://msdn.microsoft.com/en-us/library/aa302371.aspx

[अपडेट]: अन्य जवाब एक अच्छा बिंदु को लाता है: अगर आप सिर्फ क्रमपरिवर्तन का उपयोग कर रहे एक फेरबदल करने के लिए वहाँ अभी भी बेहतर विकल्प उपलब्ध हैं। विशेष रूप से, Knuth/Fisher-Yatesshuffle।

Answer 4

जबकि आप ब्रेवटी को बनाए रखते हुए इसे बंद नहीं कर सकते हैं, तो आप बहुत करीब आ सकते हैं। tuples और नहीं बल्कि भारी सूची comprehensions (अर्थात LINQ) की

public static class IEnumerableExtensions 
{ 
    public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source) 
    { 
    if (source == null) 
     throw new ArgumentNullException("source"); 

    return PermutationsImpl(source, new T[0]); 
    } 

    private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, IEnumerable<T> prefix) 
    { 
    if (source.Count() == 0) 
     yield return prefix; 

    foreach (var x in source) 
     foreach (var permutation in PermutationsImpl(source.Except(new T[] { x }), 
                prefix.Union(new T[] { x })))) 
     yield return permutation; 
    } 
}