एक सेट

Question

में अद्वितीय क्रमपरिवर्तन की कुशलतापूर्वक गणना करना मैं वर्तमान में डेटा की एक सरणी के अद्वितीय क्रमपरिवर्तन की गणना कर रहा हूं। जबकि निम्न कोड काम कर रहा है, यह उतना कुशल नहीं है जितना मैं चाहूंगा। एक बार जब मैं 6 या 8 से अधिक वस्तुओं को प्राप्त करता हूं, तो यह बहुत धीमा हो जाता है और मैं स्मृति समस्याओं में दौड़ना शुरू करता हूं।

यहाँ कोड और एक विवरण

<?php 
function permuteUnique($items, $count = false, $perms = [], &$return = []) { 
    if ($count && count($return) == $count) return $return; 

    if (empty($items)) { 
     $duplicate = false; 

     foreach ($return as $a) { 
      if ($a === $perms) { 
       $duplicate = true; 
       break; 
      } 
     } 
     if (!$duplicate) $return[] = $perms; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($tmp) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $tmp); 
      permuteUnique($newitems, $count, $newperms, $return); 
     } 
     return $return; 
    } 
} 

function factorial($n) { 
    $f = 1; 
    for ($i = 2; $i <= $n; $i++) $f *= $i; 
    return $f; 
} 

इनपुट [1, 1, 2] मैं निम्नलिखित उत्पादन की उम्मीद के रूप में प्राप्त देखते हुए

array (size=3) 
    0 => 
    array (size=3) 
     0 => int 1 
     1 => int 1 
     2 => int 2 
    1 => 
    array (size=3) 
     0 => int 1 
     1 => int 2 
     2 => int 1 
    2 => 
    array (size=3) 
     0 => int 2 
     1 => int 1 
     2 => int 1 

$count पैरामीटर है तो मैं अद्वितीय क्रमपरिवर्तन की संख्या पारित कर सकते हैं मैं फ़ंक्शन की अपेक्षा करें और एक बार इसे कई बार मिल जाए, तो यह डेटा की गणना करना बंद कर सकता है। यह सभी डुप्लिकेट की गिनती के फैक्टोरियल के उत्पाद द्वारा विभाजित वस्तुओं की कुल संख्या के फैक्टोरियल के रूप में गणना की जाती है। मुझे यकीन नहीं है कि मैंने कहा है कि ठीक है तो मुझे आपको एक उदाहरण दिखाएं।

सेट [1, 2, 2, 3, 4, 4, 4, 4] क्योंकि वहाँ 8 कुल आइटम, उनमें से एक दो बार दोहराया गया है कर रहे हैं अद्वितीय क्रमपरिवर्तन की गिनती 8!/(2!4!) = 840 के रूप में गणना की जाती है, और एक अन्य 4 बार दोहराया गया है को देखते हुए।

अब अगर मैं php कोड है कि अनुवाद करते हैं ...

<?php 
$set = [1, 2, 2, 3, 4, 4, 4, 4]; 
$divisor = 1; 

foreach (array_count_values($set) as $v) { 
    $divisor *= factorial($v); 
} 

$count = factorial(count($set))/$divisor; 
$permutations = permuteUnique($set, $count); 

यह बहुत धीमी है। अगर मैं permuteUnique फ़ंक्शन में काउंटर फेंकता हूं, तो यह 840 अद्वितीय क्रमिकताओं को खोजने से पहले 100k बार से अधिक चलाता है।

मैं इसे कम करने और अद्वितीय क्रमपरिवर्तनों के लिए सबसे कम संभव पथ खोजने का तरीका ढूंढना चाहता हूं। मैं आपकी सहायता या सलाह की सराहना करता हूं।

Answer 1

इसलिए मैंने इस बारे में सोचने में कुछ और समय बिताया और यहां मैं यही आया हूं।

<?php 
function permuteUnique($items, $perms = [], &$return = []) { 
    if (empty($items)) { 
     $return[] = $perms; 
    } else { 
     sort($items); 
     $prev = false; 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $tmp = array_splice($newitems, $i, 1)[0]; 
      if ($tmp != $prev) { 
       $prev = $tmp; 
       $newperms = $perms; 
       array_unshift($newperms, $tmp); 
       permuteUnique($newitems, $newperms, $return); 
      } 
     } 
     return $return; 
    } 
} 

$permutations = permuteUnique([1, 2, 2, 3, 4, 4, 4, 4]); 

पिछला आँकड़े

Uniques: 840 
Calls to permuteUnique: 107,591 
Duplicates found: 38737 
Execution time (seconds): 4.898668050766 

नए आँकड़े

Uniques: 840 
Calls to permuteUnique: 2647 
Duplicates found: 0 
Execution time (seconds): 0.0095300674438477 

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

Answer 2

मैंने विकी पर "लेक्सिकोग्राफिक ऑर्डर में जेनरेशन" की कोशिश की, और यह आपके "1,2,2,3,4,4,4,4" नमूने के लिए एक ही परिणाम उत्पन्न करता है, इसलिए मुझे लगता है कि सही है।

function &permuteUnique($items) { 
    sort($items); 
    $size = count($items); 
    $return = []; 
    while (true) { 
     $return[] = $items; 
     $invAt = $size - 2; 
     for (;;$invAt--) { 
      if ($invAt < 0) { 
       break 2; 
      } 
      if ($items[$invAt] < $items[$invAt + 1]) { 
       break; 
      } 
     } 
     $swap1Num = $items[$invAt]; 
     $inv2At = $size - 1; 
     while ($swap1Num >= $items[$inv2At]) { 
      $inv2At--; 
     } 
     $items[$invAt] = $items[$inv2At]; 
     $items[$inv2At] = $swap1Num; 
     $reverse1 = $invAt + 1; 
     $reverse2 = $size - 1; 
     while ($reverse1 < $reverse2) { 
      $temp = $items[$reverse1]; 
      $items[$reverse1] = $items[$reverse2]; 
      $items[$reverse2] = $temp; 
      $reverse1++; 
      $reverse2--; 
     } 
    } 
    return $return; 
} 

अपने उदाहरण इनपुट के लिए समय की रूपरेखा: उपरोक्त विधि: यहाँ कोड है 2600,3000,3000,2400,2400,3000; आपका "परमिट करने के लिए कॉल करें: 2647" विधि: 453425.6,454425.4,454625.8। इस उदाहरण के इनपुट में, यह लगभग 500 गुना तेज है :) यदि आप इस गैर-पुनरावर्ती विधि का उपयोग करके परिणाम को एक-एक करके (मुझे लगता है कि आप करेंगे), तो आप जेनरेट की गई प्रक्रिया को संसाधित कर सकते हैं और फिर अगला उत्पन्न कर सकते हैं सभी को उत्पन्न करना और प्रसंस्करण से पहले सभी को स्टोर करना)।

Answer 3

इस संशोधित पुनरावृत्ति संस्करण को आजमाएं। इसमें रिकर्सिव ओवरहेड नहीं है। http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

मूल:

पर मिला

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"; 
} 

यहाँ एक विचार है अलग क्रमपरिवर्तन के लिए यह संशोधित करने के लिए है, लेकिन मुझे लगता है कि तेजी से समाधान देखते हैं ....

function pc_next_permutation($p, $size) { 
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } 
    if ($i == -1) { return false; } 
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { } 
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    for (++$i, $j = $size; $i < $j; ++$i, --$j) { 
     $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    } 

    return $p; 
} 

$uniqueMap=array(); 
$set = split(' ', '1 2 2 3 4 4 4 4'); 
$size = count($set) - 1; 
$perm = range(0, $size); 
$j=0; 

do { 
    $uniqueSetString=""; 
    foreach ($perm as $i) 
     $uniqueSetString .= "|".$set[$i]; 

    if (!isset($uniqueMap[$uniqueSetString])) 
    { 
     foreach ($perm as $i) 
      $perms[$j][] = $set[$i]; 

     $uniqueMap[$uniqueSetString]=1; 
    } 
} while ($perm = pc_next_permutation($perm, $size) and ++$j); 

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

Answer 4

आपको factoriadic की आवश्यकता है, यह आपको पिछले सभी/followin के बिना nth क्रमपरिवर्तन उत्पन्न करने की अनुमति देता है जी वाले मैंने इसे PHP में कोड किया है लेकिन मेरे पास यह एटीएम नहीं है, क्षमा करें।

संपादित करें: Here you go, आपको इसे शुरू करना चाहिए।