आप एन के माध्यम से 0 के सभी संभावित क्रमपरिवर्तनों की गणना कैसे करेंगे?

Question

मुझे क्रमिक क्रमपरिवर्तन की गणना करने की आवश्यकता है। विधि हस्ताक्षर लगता है:

int[][] permute(int n)

n = 3 के लिए उदाहरण के लिए, वापसी मान होगा:

[[0,1,2], 
[0,2,1], 
[1,0,2], 
[1,2,0], 
[2,0,1], 
[2,1,0]] 

आप सबसे कारगर तरीका संभव में iteratively ऐसा करने के बारे में कैसे जाना होगा? मैं इसे बार-बार कर सकता हूं, लेकिन मुझे इसे करने के कई वैकल्पिक तरीकों को देखने में दिलचस्पी है।

Answer 1

देख QuickPerm एल्गोरिथ्म, यह पुनरावृत्ति है: http://www.quickperm.org/

संपादित करें:

स्पष्टता के लिए रूबी पुनः लिखा:

def permute_map(n) 
    results = [] 
    a, p = (0...n).to_a, [0] * n 
    i, j = 0, 0 
    i = 1 
    results << yield(a) 
    while i < n 
    if p[i] < i 
     j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0 
     a[j], a[i] = a[i], a[j] # Swap 
     results << yield(a) 
     p[i] += 1 
     i = 1 
    else 
     p[i] = 0 
     i += 1 
    end 
    end 
    return results 
end 

Answer 2

मैंने here से एल्गोरिदम का उपयोग किया है। पृष्ठ में बहुत उपयोगी जानकारी है।

संपादित करें: क्षमा करें, वे रिकर्सिव थे। uray ने अपने जवाब में पुनरावृत्त एल्गोरिदम के लिए लिंक पोस्ट किया।

मैंने एक PHP उदाहरण बनाया है। जब तक आप वास्तव में परिणाम के सभी वापस जाने के लिए की जरूरत है, मैं केवल निम्नलिखित की तरह एक सतत वर्ग बनाना होगा:

<?php 
class Permutator implements Iterator 
{ 
    private $a, $n, $p, $i, $j, $k; 
    private $stop; 

    public function __construct(array $a) 
    { 
    $this->a = array_values($a); 
    $this->n = count($this->a); 
    } 

    public function current() 
    { 
    return $this->a; 
    } 

    public function next() 
    { 
    ++$this->k; 
    while ($this->i < $this->n) 
    { 
     if ($this->p[$this->i] < $this->i) 
     { 
     $this->j = ($this->i % 2) * $this->p[$this->i]; 

     $tmp = $this->a[$this->j]; 
     $this->a[$this->j] = $this->a[$this->i]; 
     $this->a[$this->i] = $tmp; 

     $this->p[$this->i]++; 
     $this->i = 1; 
     return; 
     } 

     $this->p[$this->i++] = 0; 
    } 

    $this->stop = true; 
    } 

    public function key() 
    { 
    return $this->k; 
    } 

    public function valid() 
    { 
    return !$this->stop; 
    } 

    public function rewind() 
    { 
    if ($this->n) $this->p = array_fill(0, $this->n, 0); 
    $this->stop = $this->n == 0; 
    $this->i = 1; 
    $this->j = 0; 
    $this->k = 0; 
    } 

} 

foreach (new Permutator(array(1,2,3,4,5)) as $permutation) 
{ 
    var_dump($permutation); 
} 
?> 

ध्यान दें कि यह एक अनुक्रमित सरणी के रूप में हर पीएचपी सरणी व्यवहार करता है।

Answer 3

एक क्रमपरिवर्तन से अगले तक कदम उठाने के लिए एल्गोरिदम प्राथमिक विद्यालय के अतिरिक्त के समान है - जब एक अतिप्रवाह होता है, "एक ले जाएं"।

यहाँ एक कार्यान्वयन मैं सी में लिखा है:

#include <stdio.h> 

//Convenience macro. Its function should be obvious. 
#define swap(a,b) do { \ 
     typeof(a) __tmp = (a); \ 
     (a) = (b); \ 
     (b) = __tmp; \ 
    } while(0) 

void perm_start(unsigned int n[], unsigned int count) { 
    unsigned int i; 
    for (i=0; i<count; i++) 
     n[i] = i; 
} 

//Returns 0 on wraparound 
int perm_next(unsigned int n[], unsigned int count) { 
    unsigned int tail, i, j; 

    if (count <= 1) 
     return 0; 

    /* Find all terms at the end that are in reverse order. 
     Example: 0 3 (5 4 2 1) (i becomes 2) */ 
    for (i=count-1; i>0 && n[i-1] >= n[i]; i--); 
    tail = i; 

    if (tail > 0) { 
     /* Find the last item from the tail set greater than 
      the last item from the head set, and swap them. 
      Example: 0 3* (5 4* 2 1) 
      Becomes: 0 4* (5 3* 2 1) */ 
     for (j=count-1; j>tail && n[j] <= n[tail-1]; j--); 

     swap(n[tail-1], n[j]); 
    } 

    /* Reverse the tail set's order */ 
    for (i=tail, j=count-1; i<j; i++, j--) 
     swap(n[i], n[j]); 

    /* If the entire list was in reverse order, tail will be zero. */ 
    return (tail != 0); 
} 

int main(void) 
{ 
    #define N 3 
    unsigned int perm[N]; 

    perm_start(perm, N); 
    do { 
     int i; 
     for (i = 0; i < N; i++) 
      printf("%d ", perm[i]); 
     printf("\n"); 
    } while (perm_next(perm, N)); 

    return 0; 
} 

Answer 4

1.9 का उपयोग कर रहा है ऐरे # क्रमपरिवर्तन एक विकल्प?

>> a = [0,1,2].permutation(3).to_a 
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] 

Answer 5

यहाँ, सी # में एक कार्यान्वयन है एक विस्तार पद्धति के रूप में:

public static IEnumerable<List<T>> Permute<T>(this IList<T> items) 
{ 
    var indexes = Enumerable.Range(0, items.Count).ToArray(); 

    yield return indexes.Select(idx => items[idx]).ToList(); 

    var weights = new int[items.Count]; 
    var idxUpper = 1; 
    while (idxUpper < items.Count) 
    { 
     if (weights[idxUpper] < idxUpper) 
     { 
      var idxLower = idxUpper % 2 * weights[idxUpper]; 
      var tmp = indexes[idxLower]; 
      indexes[idxLower] = indexes[idxUpper]; 
      indexes[idxUpper] = tmp; 
      yield return indexes.Select(idx => items[idx]).ToList(); 
      weights[idxUpper]++; 
      idxUpper = 1; 
     } 
     else 
     { 
      weights[idxUpper] = 0; 
      idxUpper++; 
     } 
    } 
} 

और एक इकाई परीक्षण:

[TestMethod] 
public void Permute() 
{ 
    var ints = new[] { 1, 2, 3 }; 
    var orderings = ints.Permute().ToList(); 
    Assert.AreEqual(6, orderings.Count); 
    AssertUtil.SequencesAreEqual(new[] { 1, 2, 3 }, orderings[0]); 
    AssertUtil.SequencesAreEqual(new[] { 2, 1, 3 }, orderings[1]); 
    AssertUtil.SequencesAreEqual(new[] { 3, 1, 2 }, orderings[2]); 
    AssertUtil.SequencesAreEqual(new[] { 1, 3, 2 }, orderings[3]); 
    AssertUtil.SequencesAreEqual(new[] { 2, 3, 1 }, orderings[4]); 
    AssertUtil.SequencesAreEqual(new[] { 3, 2, 1 }, orderings[5]); 
} 

विधि AssertUtil.SequencesAreEqual एक कस्टम परीक्षण सहायक है जो आसानी से निर्मित किया जा सकता है पर्याप्त।

Answer 6

नीचे मेरी जेनरिक सी # में अगले क्रमचय एल्गोरिथ्म बारीकी एसटीएल के next_permutation समारोह जैसी का संस्करण है (लेकिन यह संग्रह रिवर्स नहीं करता है तो यह अधिकतम संभव क्रमचय पहले से ही है, सी ++ संस्करण की तरह)

सिद्धांत रूप में इसे किसी भी IList <> IComparables के साथ काम करना चाहिए।

static bool NextPermutation<T>(IList<T> a) where T: IComparable 
    { 
     if (a.Count < 2) return false; 
     var k = a.Count-2; 

     while (k >= 0 && a[k].CompareTo(a[k+1]) >=0) k--; 
     if(k<0)return false; 

     var l = a.Count - 1; 
     while (l > k && a[l].CompareTo(a[k]) <= 0) l--; 

     var tmp = a[k]; 
     a[k] = a[l]; 
     a[l] = tmp; 

     var i = k + 1; 
     var j = a.Count - 1; 
     while(i<j) 
     { 
      tmp = a[i]; 
      a[i] = a[j]; 
      a[j] = tmp; 
      i++; 
      j--; 
     } 

     return true; 
    } 

और डेमो/परीक्षण कोड:

 var src = "1234".ToCharArray(); 
     do 
     { 
      Console.WriteLine(src); 
     } 
     while (NextPermutation(src)); 

Answer 7

मैं जॉय 'एडम्स सबसे पठनीय होने के संस्करण पाया, लेकिन मैं की वजह से कैसे सी # scoping संभालती सी # करने के लिए इसे सीधे बंदरगाह नहीं कर सका फॉर-लूप चर के लिए।

/// <summary> 
/// Performs an in-place permutation of <paramref name="values"/>, and returns if there 
/// are any more permutations remaining. 
/// </summary> 
private static bool NextPermutation(int[] values) 
{ 
    if (values.Length == 0) 
     throw new ArgumentException("Cannot permutate an empty collection."); 

    //Find all terms at the end that are in reverse order. 
    // Example: 0 3 (5 4 2 1) (i becomes 2) 
    int tail = values.Length - 1; 
    while(tail > 0 && values[tail - 1] >= values[tail]) 
     tail--; 

    if (tail > 0) 
    { 
     //Find the last item from the tail set greater than the last item from the head 
     //set, and swap them. 
     // Example: 0 3* (5 4* 2 1) 
     // Becomes: 0 4* (5 3* 2 1) 
     int index = values.Length - 1; 
     while (index > tail && values[index] <= values[tail - 1]) 
      index--; 

     Swap(ref values[tail - 1], ref values[index]); 
    } 

    //Reverse the tail set's order. 
    int limit = (values.Length - tail)/2; 
    for (int index = 0; index < limit; index++) 
     Swap(ref values[tail + index], ref values[values.Length - 1 - index]); 

    //If the entire list was in reverse order, tail will be zero. 
    return (tail != 0); 
} 

private static void Swap<T>(ref T left, ref T right) 
{ 
    T temp = left; 
    left = right; 
    right = temp; 
} 

Answer 8

कैसे पुनरावर्ती एल्गोरिदम के बारे में आप iteratively कॉल कर सकते हैं: इसलिए, यह उसकी कोड का एक थोड़ा बदलाव किया संस्करण है? यदि आपको वास्तव में उस सामान की एक सूची के रूप में उस सामान की आवश्यकता होगी (आपको स्पष्ट रूप से इनलाइन करना चाहिए कि व्यर्थ स्मृति का एक समूह आवंटित करने के बजाय)। आप बस इसके सूचकांक द्वारा फ्लाई पर क्रमपरिवर्तन की गणना कर सकते हैं।

क्रमपरिवर्तन की तरह ही पूंछ को फिर से बदलना (0 पर वापस जाने के बजाए) को जोड़ना है, विशिष्ट क्रमपरिवर्तन मान को अनुक्रमणित करना आधार एन में किसी संख्या के अंकों को ढूंढना है तो n-1 फिर n- 2 ... प्रत्येक पुनरावृत्ति के माध्यम से।

public static <T> boolean permutation(List<T> values, int index) { 
    return permutation(values, values.size() - 1, index); 
} 
private static <T> boolean permutation(List<T> values, int n, int index) { 
    if ((index == 0) || (n == 0)) return (index == 0); 
    Collections.swap(values, n, n-(index % n)); 
    return permutation(values,n-1,index/n); 
} 

बूलियन रिटर्न देता है कि आपका सूचकांक मूल्य सीमा से बाहर था या नहीं। अर्थात् यह एन मानों से बाहर हो गया लेकिन अभी भी शेष सूचकांक शेष रहा था।

और यह 12 से अधिक वस्तुओं के लिए सभी क्रमपरिवर्तन नहीं मिल सकता है। 12! < Integer.MAX_VALUE < 13!

- लेकिन, यह बहुत बहुत सुंदर है। और यदि आप बहुत सी चीजें करते हैं तो गलत हो सकता है।

Answer 9

मैं भी एक और उत्तर में संदर्भित क्विकपर्म एल्गोरिदम में आया था। मैं इस जवाब को इसके अतिरिक्त साझा करना चाहता था, क्योंकि मैंने कुछ तत्काल परिवर्तन देखा जो इसे कम लिखने के लिए कर सकते हैं। उदाहरण के लिए, यदि इंडेक्स सरणी "पी" को थोड़ा अलग तरीके से शुरू किया गया है, तो यह लूप से पहले पहला क्रमपरिवर्तन वापस करने के लिए सहेजता है। इसके अलावा, उन सभी जबकि लूप्स और यदि बहुत अधिक कमरा लिया गया है।

void permute(char* s, size_t l) { 
    int* p = new int[l]; 
    for (int i = 0; i < l; i++) p[i] = i; 
    for (size_t i = 0; i < l; printf("%s\n", s)) { 
     std::swap(s[i], s[i % 2 * --p[i]]); 
     for (i = 1; p[i] == 0; i++) p[i] = i; 
    } 
} 

Answer 10

मैंने जावास्क्रिप्ट में एल्गोरिदम लागू किया है।

var all = ["a", "b", "c"]; 
console.log(permute(all)); 

function permute(a){ 
    var i=1,j, temp = ""; 
    var p = []; 
    var n = a.length; 
    var output = []; 

    output.push(a.slice()); 
    for(var b=0; b <= n; b++){ 
    p[b] = b; 
    } 

    while (i < n){ 
    p[i]--; 
    if(i%2 == 1){ 
     j = p[i]; 
    } 
    else{ 
     j = 0; 
    } 
    temp = a[j]; 
    a[j] = a[i]; 
    a[i] = temp; 

    i=1; 
    while (p[i] === 0){ 
     p[i] = i; 
     i++; 
    } 
    output.push(a.slice()); 
    } 
    return output; 
}