PHP में स्ट्रिंग के सभी क्रमपरिवर्तन कैसे उत्पन्न करें?

Question

मुझे एक एल्गोरिदम चाहिए जो एक स्ट्रिंग में सभी वर्णों के सभी संभावित संयोजन को वापस कर देता है।

मैं कोशिश की है:

$langd = strlen($input); 
for($i = 0;$i < $langd; $i++){ 
    $tempStrang = NULL; 
    $tempStrang .= substr($input, $i, 1); 
    for($j = $i+1, $k=0; $k < $langd; $k++, $j++){ 
    if($j > $langd) $j = 0; 
    $tempStrang .= substr($input, $j, 1); 
} 
$myarray[] = $tempStrang; 
} 

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

$input = "hey" कहें, परिणाम होगा: hey, hye, eyh, ehy, yhe, yeh।

Answer 1

तुम एक वापस ट्रैकिंग आधारित दृष्टिकोण व्यवस्थित सभी क्रमपरिवर्तन उत्पन्न करने के लिए उपयोग कर सकते हैं:

// function to generate and print all N! permutations of $str. (N = strlen($str)). 
function permute($str,$i,$n) { 
    if ($i == $n) 
     print "$str\n"; 
    else { 
     for ($j = $i; $j < $n; $j++) { 
      swap($str,$i,$j); 
      permute($str, $i+1, $n); 
      swap($str,$i,$j); // backtrack. 
     } 
    } 
} 

// function to swap the char at pos $i and $j of $str. 
function swap(&$str,$i,$j) { 
    $temp = $str[$i]; 
    $str[$i] = $str[$j]; 
    $str[$j] = $temp; 
} 

$str = "hey"; 
permute($str,0,strlen($str)); // call the function. 

आउटपुट:

#php a.php 
hey 
hye 
ehy 
eyh 
yeh 
yhe 

Answer 2

मैं एक सरणी में सभी पात्रों डाल होता है, और एक पुनरावर्ती समारोह लिखने जो सभी शेष पात्रों को 'पट्टी' कर देगा। यदि सरणी खाली है, तो संदर्भ पारित सरणी में।

<?php 

$input = "hey"; 

function string_getpermutations($prefix, $characters, &$permutations) 
{ 
    if (count($characters) == 1) 
     $permutations[] = $prefix . array_pop($characters); 
    else 
    { 
     for ($i = 0; $i < count($characters); $i++) 
     { 
      $tmp = $characters; 
      unset($tmp[$i]); 

      string_getpermutations($prefix . $characters[$i], array_values($tmp), $permutations); 
     } 
    } 
} 
$characters = array(); 
for ($i = 0; $i < strlen($input); $i++) 
    $characters[] = $input[$i]; 
$permutations = array(); 

print_r($characters); 
string_getpermutations("", $characters, $permutations); 

print_r($permutations); 

प्रिंटों आउट:

Array 
(
    [0] => h 
    [1] => e 
    [2] => y 
) 
Array 
(
    [0] => hey 
    [1] => hye 
    [2] => ehy 
    [3] => eyh 
    [4] => yhe 
    [5] => yeh 
) 

आह हाँ, संयोजन = क्रम doens't बात। क्रमपरिवर्तन = आदेश मायने रखता है।

तो हे, हाय ये सभी समान संयोजन हैं, लेकिन 3 अलग-अलग क्रमिक क्रम उल्लेख किए गए हैं। देखें कि वस्तुओं का स्तर बहुत तेज़ हो जाता है। इसे फैक्टोरियल कहा जाता है, और 6 की तरह लिखा गया है! = 6 * 5 * 4 * 3 * 2 * 1 = 720 आइटम (6 वर्ण स्ट्रिंग के लिए)। एक 10 वर्ण स्ट्रिंग 10 होगा! = 3628800 क्रमपरिवर्तन पहले से ही, जो एक बहुत बड़ी सरणी है। इस उदाहरण में यह 3 है! = 3 * 2 * 1 = 6.

Answer 3

मेरे संस्करण (सरणी या स्ट्रिंग इनपुट के साथ के रूप में अच्छी तरह से काम करता है)

function permute($arg) { 
    $array = is_string($arg) ? str_split($arg) : $arg; 
    if(1 === count($array)) 
     return $array; 
    $result = array(); 
    foreach($array as $key => $item) 
     foreach(permute(array_diff_key($array, array($key => $item))) as $p) 
      $result[] = $item . $p; 
    return $result; 
} 

पी.एस .: Downvoter, अपनी स्थिति के बारे में समझाएं। इस कोड को अतिरिक्त str_split और array_diff_key मानक कार्यों का उपयोग करता है, लेकिन इस कोड स्निपेट छोटी से छोटी, यह सिर्फ एक इनपुट पैरामीटर के साथ शुद्ध पूंछ प्रत्यावर्तन लागू करता है और यह isomorphic इनपुट डेटा प्रकार के है।

हो सकता है कि यह अन्य कार्यान्वयन की तुलना में थोड़ा सा बेंचमार्क खो देगा (लेकिन प्रदर्शन वास्तव में लगभग कई चरित्र तारों के लिए @ कोडाडिक्ट के जवाब जैसा ही है), लेकिन हम इसे अलग-अलग क्यों नहीं मान सकते विकल्प जिनके अपने फायदे हैं?

Answer 4

मेरे दृष्टिकोण प्रत्यावर्तन और कोई छोरों का उपयोग करता है, कृपया जाँच और प्रतिक्रिया देने के:

function permute($str,$index=0,$count=0) 
{ 
    if($count == strlen($str)-$index) 
     return; 

    $str = rotate($str,$index); 

    if($index==strlen($str)-2)//reached to the end, print it 
    { 
     echo $str."<br> ";//or keep it in an array 
    } 

    permute($str,$index+1);//rotate its children 

    permute($str,$index,$count+1);//rotate itself 
} 

function rotate($str,$index) 
{ 
    $tmp = $str[$index]; 
    $i=$index; 
    for($i=$index+1;$i<strlen($str);$i++) 
    { 
     $str[$i-1] = $str[$i]; 
    } 
    $str[$i-1] = $tmp; 
    return $str; 
} 
permute("hey");