एक सेट की कुशलतापूर्वक और भेद के साथ क्रमशः

Question

मैं here से कोड पर निर्माण कर रहा हूं। मैं एक सेट के सभी क्रमपरिवर्तन उत्पन्न करने के लिए करना चाहते हैं, उदाहरण के लिए (धागा से लिया गया):

Collection: 1, 2, 3 
Permutations: {1, 2, 3} 
       {1, 3, 2} 
       {2, 1, 3} 
       {2, 3, 1} 
       {3, 1, 2} 
       {3, 2, 1} 

हर सेट के लिए संभव क्रमपरिवर्तन रहे हैं, लेकिन यह नहीं है कि मैं प्राप्त करने के लिए चाहते हैं। विचार के लिए ले लो,, सेट निम्नलिखित:

यह क्रमपरिवर्तन, का एक चरम amout प्राप्त करेगी। गणना करने के लिए यह असाधारण लंबा समय लगेगा, क्योंकि प्रत्येक शून्य को अद्वितीय माना जा रहा है।

इसके बजाय, मैं केवल विशिष्ट क्रमपरिवर्तन उत्पन्न करना चाहता हूं। अगर हम ऐसा करते हैं, वहाँ केवल

क्रमपरिवर्तन remaining, के रूप में 18 आइटम समान (के) कर रहे हैं।

अब, मैं निर्दिष्ट थ्रेड से कोड चला सकता हूं और डुप्लिकेट क्रमपरिवर्तन को समाप्त कर परिणामों को एक हैशसेट में संग्रहीत कर सकता हूं। हालांकि, यह बेहद अक्षम होगा। मैं सीधे भेदभाव के साथ क्रमपरिवर्तन उत्पन्न करने के लिए एक एल्गोरिदम की तलाश में हूं।

Answer 1

स्वैप एल्गोरिदम के साथ क्रमपरिवर्तन खोजने के लिए आप सीधे उन हिस्सों को बहिष्कृत कर सकते हैं जो डुप्लिकेट क्रमपरिवर्तन उत्पन्न करते हैं। यह एल्गोरिदम इंटरनेट पर उपलब्ध है और आप इसके बारे में अधिक जानकारी प्राप्त कर सकते हैं।

private static void Main(string[] args) 
{ 
    List<int> set = new List<int> 
    { 
     20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 
    }; 
    var permutes = Permute(set); 

    Console.WriteLine(permutes.Count); // outputs 58140 
} 

private static List<int[]> Permute(List<int> set) 
{ 
    List<int[]> result = new List<int[]>(); 

    Action<int> permute = null; 
    permute = start => 
    { 
     if (start == set.Count) 
     { 
      result.Add(set.ToArray()); 
     } 
     else 
     { 
      List<int> swaps = new List<int>(); 
      for (int i = start; i < set.Count; i++) 
      { 
       if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item 
       swaps.Add(set[i]); 

       Swap(set, start, i); 
       permute(start + 1); 
       Swap(set, start, i); 
      } 
     } 
    }; 

    permute(0); 

    return result; 
} 

private static void Swap(List<int> set, int index1, int index2) 
{ 
    int temp = set[index1]; 
    set[index1] = set[index2]; 
    set[index2] = temp; 
} 

यहां छवि है जो दिखाती है कि स्वैप एल्गोरिदम कैसे काम करता है।

तो तुम अब विचार करें A और B बराबर हैं {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, {C,A,B}

है। मैंने फ़ोटोशॉप के साथ छवि संपादित की है (माफ करना अगर मैं इसमें भयानक हूं!) और B को A के साथ बदल दिया गया। आप छवि

में देख सकते हैं Ive छवि में डुप्लिकेट की पहचान की। आप उन्हें छोड़ यदि आप {A,A,C}, {A,C,A}, {C,A,A}

होगा आप आइटम कि इतने लगा दिया जाता था अगर आइटम बराबर हैं स्टोर करने के लिए है और हम पहले से ही है कि स्वैप हम सिर्फ ड्यूप्स

if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item 
swaps.Add(set[i]); // else add it to the list of swaps. 

को रोकने के लिए परीक्षण के लिए यदि आप हटाना छोड़ दिया था इस भाग के बाद यह एल्गोरिदम डुप्लिकेट क्रमपरिवर्तन उत्पन्न करेगा और कंसोल n! आउटपुट करेगा।

Answer 2

की यह कोशिश करते हैं:

Knuths 
1. Find the largest index j such that a[j] < a[j + 1]. If no 
such index exists, the permutation is the last permutation. 

{20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 
    > > = = = = = = = = = = = = = = = = = 

ओह, वहाँ कोई सूचकांक j ऐसी है कि a[j] < a[j + 1] है।लेकिन चूंकि हम सभी अलग क्रमपरिवर्तन चाहते हैं, हम प्रत्येक सरणी और गारंटी हम शुरुआत में शुरू सॉर्ट कर सकते हैं:

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20} 

1. Find the largest index j such that a[j] < a[j + 1]. If no 
such index exists, the permutation is the last permutation. 

j = 18 since a[18] < a[19] 

2. Find the largest index l such that a[j] < a[l]. Since j + 1 
is such an index, l is well defined and satisfies j < l. 

l = 19 since a[18] < a[19] 

3. Swap a[j] with a[l]. 

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 

4. Reverse the sequence from a[j + 1] up to and including the final element a[n]. 

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 

के कुछ और करते हैं:

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,20} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20,0} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,0,10} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10,0} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,20} 
... 

आप देख सकते हैं, बड़े तत्व स्थिर रूप से (और स्पष्ट रूप से) बाएं चलते हैं:

{10,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 
yields {20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 

और क्रमपरिवर्तन डुप्लिकेट किए बिना समाप्त होता है।

Answer 3

मैंने पहले इस समस्या को किया है। आपको केवल पहले सरणी को सॉर्ट करने की आवश्यकता है और फिर आपके द्वारा देखी गई तत्वों को चिह्नित करने के लिए एक बूलियन [] विज़िट की गई सरणी का उपयोग करें। जावा में बैकट्रैकिंग का उपयोग करके मेरा समाधान:

public class Solution { 
    public List<List<Integer>> permuteUnique(int[] num) { 
     List<List<Integer>> result = new ArrayList<List<Integer>>(); 
     List<Integer> list = new ArrayList<Integer>(); 
     boolean[] visited = new boolean[num.length]; 

     Arrays.sort(num); 
     helper(result, list, num, visited); 

     return result; 
    } 

    private void helper(List<List<Integer>> result, List<Integer> list, 
      int[] num, boolean[] visited) { 
     for (int i = 0; i < num.length; i++) { 
      if (visited[i] 
        || (i > 0 && num[i] == num[i - 1] && !visited[i - 1])) { 
       continue; 
      } 
      list.add(num[i]); 
      visited[i] = true; 
      if (list.size() == num.length) { 
       result.add(new ArrayList<Integer>(list)); 
      } else { 
       helper(result, list, num, visited); 
      } 
      list.remove(list.size() - 1); 
      visited[i] = false; 
     } 
    } 
} 

Answer 4

यह अब तक का सबसे अच्छा समाधान है जिसके साथ मैं आया हूं। अनुकूलन के लिए सुझाव स्वागत है। यह वास्तव में वापस आता है!/के! आइटम नहीं है।

{20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 परमिट करने में लगभग एक सेकंड लगते हैं, 0}।

private static IEnumerable<int[]> Permute(int[] list) 
{ 
    if (list.Length > 1) 
    {  
     int n = list[0]; 
     foreach (int[] subPermute in Permute(list.Skip(1).ToArray())) 
     {  
      for (int index = 0; index <= subPermute.Length; index++) 
      { 
       int[] pre = subPermute.Take(index).ToArray(); 
       int[] post = subPermute.Skip(index).ToArray(); 

       if (post.Contains(n)) 
        continue; 

       yield return pre.Concat(new[] { n }).Concat(post).ToArray(); 
      }  
     } 
    } 
    else 
    { 
     yield return list; 
    } 
}