संभव सरणी संयोजन

Question

अतः,

समस्या

एसक्यूएल से मैं तार के साथ एक सरणी (फ्लैट सरणी) हो रही है जाओ - यह

 
$rgData = ['foo', 'bar', 'baz', 'bee', 'feo']; 

हो अब, मैं चाहते हैं जोड़े के संभावित संयोजन और इस सरणी के तीन गुना (और, सामान्य मामले में, 4 तत्वों ई टीसी के संयोजन) प्राप्त करने के लिए। अधिक विशिष्ट होना करने के लिए: मैं

कि ऊपर सरणी के लिए है, ताकि के लिए गणित की समझ (डुप्लिकेट) के बिना है, यानी उन है, जो गिनती बराबर है में combinations मतलब दोनों जोड़े और तीनो के लिए 10 हो जाएगा।

मेरे दृष्टिकोण

मैं संभव सरणी चयनित आइटम में के लिए मानचित्रण संभावित मान से शुरू कर दिया है। मेरा वर्तमान समाधान यह इंगित करना है कि कोई तत्व "1" और "0" के रूप में चुना गया है या नहीं। कि ऊपर नमूना हो जाएगा के लिए:

 
foo bar baz bee feo 
0 0 1 1 1 -> [baz, bee, feo] 
0 1 0 1 1 -> [bar, bee, feo] 
0 1 1 0 1 -> [bar, baz, feo] 
0 1 1 1 0 -> [bar, baz, bee] 
1 0 0 1 1 -> [foo, bee, feo] 
1 0 1 0 1 -> [foo, baz, feo] 
1 0 1 1 0 -> [foo, baz, bee] 
1 1 0 0 1 -> [foo, baz, feo] 
1 1 0 1 0 -> [foo, bar, bee] 
1 1 1 0 0 -> [foo, bar, baz] 

और यह सब मैं क्या करने की जरूरत किसी भी तरह वांछित बिट सेट उत्पादन कर रहा है। यहाँ PHP में मेरी कोड है:

function nextAssoc($sAssoc) 
{ 
    if(false !== ($iPos = strrpos($sAssoc, '01'))) 
    { 
     $sAssoc[$iPos] = '1'; 
     $sAssoc[$iPos+1] = '0'; 
     return substr($sAssoc, 0, $iPos+2). 
      str_repeat('0', substr_count(substr($sAssoc, $iPos+2), '0')). 
      str_repeat('1', substr_count(substr($sAssoc, $iPos+2), '1')); 
    } 
    return false; 
} 

function getAssoc(array $rgData, $iCount=2) 
{ 
    if(count($rgData)<$iCount) 
    { 
     return null; 
    } 
    $sAssoc = str_repeat('0', count($rgData)-$iCount).str_repeat('1', $iCount); 
    $rgResult = []; 
    do 
    { 
     $rgResult[]=array_intersect_key($rgData, array_filter(str_split($sAssoc))); 
    } 
    while($sAssoc=nextAssoc($sAssoc)); 
    return $rgResult; 
} 

-I've एक सामान्य स्ट्रिंग के रूप में मेरी बिट्स स्टोर करने के लिए चुना है। अगली एसोसिएशन के उत्पादन के लिए मेरा एल्गोरिदम है:

1. "01" ढूंढने का प्रयास करें। यदि नहीं मिला, तो यह 11..100..0 मामला है (इसलिए यह अधिकतम है, और नहीं पाया जा सकता है)। यदि पाया जाता है, तो दूसरे चरण
2. पर जाएं स्ट्रिंग में "01" की सबसे सही स्थिति पर जाएं। इसे "10" पर स्विच करें और उसके बाद बाईं ओर स्थित सभी शून्यों को "01" स्थिति से अधिक सवारी करें। उदाहरण के लिए, 01110: "01" की सबसे सही स्थिति 0 है, इसलिए सबसे पहले हम इसे "01" से "10" पर स्विच करते हैं। स्ट्रिंग अब 10110 होगा। अब, सही भाग पर जाएं (यह 10 भाग के बिना है, इसलिए यह 0 + 2 = 2-nd प्रतीक से शुरू होता है), और सभी शून्यों को बाईं ओर ले जाएं, यानी 110011 होगा। नतीजतन, हमारे पास 10 + 011 = 1011101110 के लिए अगली एसोसिएशन के रूप में है।

मुझे इसी तरह की समस्या मिली है here - लेकिन वहां ओपी डुप्लिकेट के साथ संयोजन चाहता है, जबकि मैं उन्हें डुप्लिकेट किए बिना चाहता हूं।

सवाल

मेरा प्रश्न के बारे में दो अंक है:

• मेरे समाधान के लिए, वहाँ एक और तरीका है अगले थोड़ा और अधिक कुशल सेट का उत्पादन करने के लिए हो सकता है?
• क्या इसके लिए और अधिक सरल समाधान हो सकते हैं? यह मानक समस्या प्रतीत होता है।

Answer 1

मुझे PHP समाधान प्रदान करने के लिए खेद है, क्योंकि मैंने अब लंबे समय से PHP में प्रोग्राम नहीं किया है, लेकिन मुझे आपको त्वरित स्केल समाधान दिखाएं। शायद यह आपको प्रेरित करेगा:

val array = Vector("foo", "bar", "baz", "bee", "feo") 
for (i <- 0 until array.size; 
    j <- i + 1 until array.size; 
    k <- j + 1 until array.size)  
    yield (array(i), array(j), array(k)) 

परिणाम:

Vector((foo,bar,baz), (foo,bar,bee), (foo,bar,feo), (foo,baz,bee), (foo,baz,feo), (foo,bee,feo), (bar,baz,bee), (bar,baz,feo), (bar,bee,feo), (baz,bee,feo)) 

k- संयोजन पैदा करने के लिए यूनिवर्सल कोड:

def combinations(array: Vector[String], k: Int, start: Int = 0): Iterable[List[String]] = { 
    if (k == 1 || start == array.length) 
    for (i <- start until array.length) yield List(array(i)) 
    else 
    for (i <- start until array.length; c <- combinations(array, k - 1, i + 1)) yield array(i) :: c 
} 

परिणाम:

scala> combinations(Vector("a", "b", "c", "d", "e"), 1) 
res8: Iterable[List[String]] = Vector(List(a), List(b), List(c), List(d), List(e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 2) 
res9: Iterable[List[String]] = Vector(List(a, b), List(a, c), List(a, d), List(a, e), List(b, c), List(b, d), List(b, e), List(c, d), List(c, e), List(d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 3) 
res10: Iterable[List[String]] = Vector(List(a, b, c), List(a, b, d), List(a, b, e), List(a, c, d), List(a, c, e), List(a, d, e), List(b, c, d), List(b, c, e), List(b, d, e), List(c, d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 4) 
res11: Iterable[List[String]] = Vector(List(a, b, c, d), List(a, b, c, e), List(a, b, d, e), List(a, c, d, e), List(b, c, d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 5) 
res12: Iterable[List[String]] = Vector(List(a, b, c, d, e)) 

बेशक

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

Answer 2

यहाँ एक पुनरावर्ती समाधान है:

function subcombi($arr, $arr_size, $count) 
{ 
    $combi_arr = array(); 
    if ($count > 1) { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $highest_index_elem_arr = array($i => $arr[$i]); 
     foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { 
      $combi_arr[] = $subcombi_arr + $highest_index_elem_arr; 
     } 
     } 
    } else { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $combi_arr[] = array($i => $arr[$i]); 
     } 
    } 
    return $combi_arr; 
} 

function combinations($arr, $count) 
{ 
    if (!(0 <= $count && $count <= count($arr))) { 
     return false; 
    } 
    return $count ? subcombi($arr, count($arr), $count) : array(); 
}  

$input_arr = array('foo', 'bar', 'baz', 'bee', 'feo'); 
$combi_arr = combinations($input_arr, 3); 
var_export($combi_arr); echo ";\n"; 

OUTPUT: 

array (
    0 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    2 => 'baz', 
), 
    1 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    3 => 'bee', 
), 
    2 => 
    array (
    0 => 'foo', 
    2 => 'baz', 
    3 => 'bee', 
), 
    3 => 
    array (
    1 => 'bar', 
    2 => 'baz', 
    3 => 'bee', 
), 
    4 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    4 => 'feo', 
), 
    5 => 
    array (
    0 => 'foo', 
    2 => 'baz', 
    4 => 'feo', 
), 
    6 => 
    array (
    1 => 'bar', 
    2 => 'baz', 
    4 => 'feo', 
), 
    7 => 
    array (
    0 => 'foo', 
    3 => 'bee', 
    4 => 'feo', 
), 
    8 => 
    array (
    1 => 'bar', 
    3 => 'bee', 
    4 => 'feo', 
), 
    9 => 
    array (
    2 => 'baz', 
    3 => 'bee', 
    4 => 'feo', 
), 
); 

प्रत्यावर्तन तथ्य यह है कि n ($arr_size) से बाहर k ($count) तत्वों के सभी संयोजनों पाने के लिए पर आधारित है तो आपको, के सभी संभव विकल्पों के लिए उच्चतम शून्य-आधारित इंडेक्स i, i से नीचे इंडेक्स वाले शेष i तत्वों में से k-1 तत्वों के सभी "सबकॉम्बिनेशन" ढूंढें।

एरे array_slice डी नहीं है जब यह PHP की "आलसी प्रति" तंत्र का लाभ उठाने के लिए रिकर्सिव कॉल को पास किया जाता है। इस तरह कोई वास्तविक प्रतिलिपि नहीं होती है, क्योंकि सरणी संशोधित नहीं होती है।

एरे इंडेक्स को सुरक्षित करना डीबगिंग उद्देश्यों के लिए अच्छा है, लेकिन यह आवश्यक नहीं है। हैरानी की बात है कि $i => भागों को हटाकर को के साथ सरणी + को बदलना काफी मंदी का कारण बनता है। मूल संस्करण की तुलना में एक से थोड़ा बेहतर गति प्राप्त करने के लिए, तो आप इस करना है:

function subcombi($arr, $arr_size, $count) 
{ 
    $combi_arr = array(); 
    if ($count > 1) { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $highest_index_elem = $arr[$i]; 
     foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { 
      $subcombi_arr[] = $highest_index_elem; 
      $combi_arr[] = $subcombi_arr; 
     } 
     } 
    } else { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $combi_arr[] = array($arr[$i]); 
     } 
    } 
    return $combi_arr; 
} 

---

अपने प्रश्न के पहले भाग के बारे में, आप एक ही मात्रा एक से अधिक बार की गणना करने से बचना चाहिए, और आप समारोह को कम करना चाहिए कहता है। उदा।, इस तरह:

function nextAssoc($sAssoc) 
{ 
    if (false !== ($iPos = strrpos($sAssoc, '01'))) 
    { 
     $sAssoc[$iPos] = '1'; 
     $sAssoc[$iPos+1] = '0'; 
     $tailPos = $iPos+2; 
     $n0 = substr_count($sAssoc, '0', $tailPos); 
     $n1 = strlen($sAssoc) - $tailPos - $n0; 
     return substr($sAssoc, 0, $tailPos).str_repeat('0', $n0) 
             .str_repeat('1', $n1); 
    } 
    return false; 
} 

इसे बिना कोड के अपने कोड में गहरा परिवर्तन करना मुश्किल है। यह बहुत बुरा है, हालांकि, के बाद से मेरी परीक्षणों में इसकी गति लगभग आधा मेरी पुनरावर्ती समाधान में से एक (यानी, बार सीए कर रहे हैं डबल)