एक PHP सरणी के सभी क्रमपरिवर्तन प्राप्त करें?

Question

तार के एक PHP सरणी, यह देखते हुए उदा .:

['peter', 'paul', 'mary'] 

कैसे इस सरणी के तत्वों के सभी संभव क्रमपरिवर्तन उत्पन्न करने के लिए? यानी .:

peter-paul-mary 
peter-mary-paul 
paul-peter-mary 
paul-mary-peter 
mary-peter-paul 
mary-paul-peter 

Answer 1

function pc_permute($items, $perms = array()) { 
    if (empty($items)) { 
     echo join(' ', $perms) . "<br />"; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      pc_permute($newitems, $newperms); 
     } 
    } 
} 

$arr = array('peter', 'paul', 'mary'); 

pc_permute($arr); 

या

function pc_next_permutation($p, $size) { 
    // slide down the array looking for where we're smaller than the next guy 
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } 

    // if this doesn't occur, we've finished our permutations 
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1) 
    if ($i == -1) { return false; } 

    // slide down the array looking for a bigger number than what we found before 
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { } 

    // swap them 
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 

    // now reverse the elements in between by swapping the ends 
    for (++$i, $j = $size; $i < $j; ++$i, --$j) { 
     $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    } 

    return $p; 
} 

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells') 
$size = count($set) - 1; 
$perm = range(0, $size); 
$j = 0; 

do { 
    foreach ($perm as $i) { $perms[$j][] = $set[$i]; } 
} while ($perm = pc_next_permutation($perm, $size) and ++$j); 

foreach ($perms as $p) { 
    print join(' ', $p) . "\n"; 
} 

http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

Answer 2

मैं कुछ इसी तरह की जरूरत है और जबकि देख इस पोस्ट पाया। नौकरी करने वाले निम्नलिखित लिखने लगी।

8 आइटमों के साथ यह काफी तेज़ी से काम करता है (उदाहरणों से मुझे थोड़ा सा उदाहरण मिलता है), लेकिन उससे आगे और रन टाइम रैंप तेजी से बढ़ते हैं। यदि आपको केवल परिणामों को आउटपुट करने की आवश्यकता है तो इसे तेज बनाया जा सकता है और स्मृति उपयोग बड़े पैमाने पर कम हो जाता है।

print_r(AllPermutations(array('peter', 'paul', 'mary'))); 

function AllPermutations($InArray, $InProcessedArray = array()) 
{ 
    $ReturnArray = array(); 
    foreach($InArray as $Key=>$value) 
    { 
     $CopyArray = $InProcessedArray; 
     $CopyArray[$Key] = $value; 
     $TempArray = array_diff_key($InArray, $CopyArray); 
     if (count($TempArray) == 0) 
     { 
      $ReturnArray[] = $CopyArray; 
     } 
     else 
     { 
      $ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray)); 
     } 
    } 
    return $ReturnArray; 
} 

ध्यान दें कि क्रमपरिवर्तन की संख्या सरणी में वस्तुओं की संख्या का कारक है। 3 वस्तुओं के लिए 6 क्रमपरिवर्तन हैं, 4 के लिए 24 हैं, 5 के लिए 120 हैं, 6 के लिए 720 हैं, आदि

Answer 3

यह वही है जो आपको चाहिए, यानी कोई अतिरिक्त मेमोरी आवंटित किए बिना। यह परिणामी क्रमपरिवर्तन $ परिणाम सरणी स्टोर करता है। मुझे पूरा भरोसा है कि यह कार्य को हल करने का सबसे तेज़ तरीका है।

<?php 
function computePermutations($array) { 
    $result = []; 

    $recurse = function($array, $start_i = 0) use (&$result, &$recurse) { 
     if ($start_i === count($array)-1) { 
      array_push($result, $array); 
     } 

     for ($i = $start_i; $i < count($array); $i++) { 
      //Swap array value at $i and $start_i 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 

      //Recurse 
      $recurse($array, $start_i + 1); 

      //Restore old order 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 
     } 
    }; 

    $recurse($array); 

    return $result; 
} 


$results = computePermutations(array('foo', 'bar', 'baz')); 
print_r($results); 

यह PHP> 5.4 में काम करता है। मैंने मुख्य फ़ंक्शन के इंटरफ़ेस को साफ रखने के लिए रिकर्सन के लिए एक अज्ञात फ़ंक्शन का उपयोग किया।

Answer 4

मैं जैक

function pc_permute($items, $perms = [],&$ret = []) { 
    if (empty($items)) { 
     $ret[] = $perms; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      $this->pc_permute($newitems, $newperms,$ret); 
     } 
    } 
    return $ret; 
} 

के जवाब पर थोड़ा विस्तार किया यह वास्तव में सभी संभव क्रमपरिवर्तन के साथ एक सरणी वापस आ जाएगी।

$options = ['startx','starty','startz','endx','endy','endz']; 
$x = $this->pc_permute($options); 
var_dump($x); 

    [0]=> 
array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [1]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [2]=> 
    array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [3]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [4]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [5]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [6]=> ................ a lot more 

मुझे स्ट्रिंग के बजाय सरणी वापस पाने के लिए थोड़ा और उपयोगी पाया गया। तो फिर यह कैसे resutls को संभालने के लिए अनुप्रयोग का उपयोग करने के लिए हो रहा है (उन्हें शामिल होने के, या कुछ और) प्रत्यावर्तन और कोई कृत्रिम अतिरिक्त तर्क के साथ

Answer 5

सरल संस्करण:

function permuteArray(array $input) { 
    $input = array_values($input); 

    // permutation of 1 value is the same value 
    if (count($input) === 1) { 
     return array($input); 
    } 

    // to permute multiple values, pick a value to put in the front and 
    // permute the rest; repeat this with all values of the original array 
    $result = []; 
    for ($i = 0; $i < count($input); $i++) { 
     $copy = $input; 
     $value = array_splice($copy, $i, 1); 
     foreach (permuteArray($copy) as $permutation) { 
      array_unshift($permutation, $value[0]); 
      $result[] = $permutation; 
     } 
    } 

    return $result; 
} 

इस एल्गोरिथ्म अच्छा और शिक्षाप्रद है कि कैसे आप कागज पर ऐसा करेंगे, लेकिन अन्यथा बहुत अक्षम है क्योंकि यह कई बार समान क्रमिक गणना करता है। यह नहीं कहना कि अंतरिक्ष और संख्याओं की संख्या तेजी से बढ़ने के कारण बड़े सरणी के क्रमपरिवर्तन की गणना के लिए यह बहुत अव्यवहारिक है।