मैं एन सिंगल-डिजिट, गैर-दोहराव संख्याओं के सभी सेट कैसे प्राप्त करूं जो PHP में दिए गए योग को जोड़ती हैं?

Question

मान लीजिए कि मैं 5 एकल अंकों के सभी सेट, गैर-दोहराने वाली संख्याएं जो 30 तक जोड़ना चाहता हूं ... मैं [9,8,7,5,1], [9,8 , 7,4,2], [9,8,6,4,3], [9,8,6,5,2], [9,7,6,5,3], और [8,7, 6,5,4]। इनमें से प्रत्येक सेट में 5 गैर-दोहराने वाले अंक होते हैं जो 30 तक जोड़ते हैं, दिए गए योग।

किसी भी मदद की सराहना की जाएगी। यहां तक ​​कि मेरे लिए उपयोग करने के लिए एक शुरुआती बिंदु भी भयानक होगा।

मैं एक विधि के साथ आया, जो इसके बारे में जाने का एक लंबा सफर लगता है: सभी अद्वितीय 5 अंकों की संख्या (12345, 12346, 12347, आदि) प्राप्त करें, अंक जोड़ें, और देखें कि यह बराबर है या नहीं दिया गया योग (उदाहरण 30)। यदि ऐसा होता है, तो इसे संभावित मिलान सेट की सूची में जोड़ें।

मैं इसे एक निजी परियोजना के लिए कर रहा हूं, जो वास्तव में पूरी चीज़ को हल किए बिना ककुरो पहेली को हल करने में मेरी सहायता करेगा। हाँ, यह धोखा दे सकता है, लेकिन यह है ... यह बुरा नहीं है ...: पी

Answer 1

एक अनुभवहीन दृष्टिकोण 98765 तक 12345 से एक चर बढ़ाने के लिए चुनने के लिए उसे केवल अगर यह अनूठा अंक और अंकों का योग है किया जाएगा 30 है:

for($i=12345;$i<98765;$i++) { 
    $arr = preg_split('//',strval($i)); 
    if(count(array_unique($arr)) == count($arr) && array_sum($arr) == 30) 
     echo $i."\n"; 
} 

Working example

Answer 2

मुझे पता है कि इसके लिए एल्गोरिदम हैं, और शायद उन्हें अन्य लोगों द्वारा प्रदान किया जाएगा, लेकिन यहां एक त्वरित सरलीकरण है जो आप कर सकते हैं बनाएं: 21-29 तक जोड़े गए 4 सिंगल अंकों के सभी सेटों को देखें (मुझे लगता है कि आप अंक के रूप में 0 की गणना नहीं कर रहे हैं) और केवल उन लोगों को खत्म करें जिनके लिए 30- (योग) अंकों में से एक है ।

अगर मैं कुछ भी तेज कोशिश करना चाहता था, तो मैं 45678 से शुरू करने के बारे में सोचता हूं और एक अंक में 1 जोड़कर और दूसरे अंक से 1 घटाकर इसे बदलता हूं। यह सुनिश्चित नहीं है कि अंत में यह कितना अच्छा काम करेगा।

Answer 3

function sumOfDigits($num) { 
    $str = "{$num}"; 
    $sum = 0; 
    for ($i=0;$i<strlen($str);$i++) { 
     $sum += (int)substr($str, $i, 1); 
    } 
    return $sum; 
} 

function hasDuplicateDigits($num) { 
    $str = "{$num}"; 
    $pieces = array(); 
    for ($i=0;$i<strlen($str);$i++) { 
     $pieces[] = substr($str, $i, 1); 
    } 
    return (count(array_unique($pieces)) != strlen($str)); 
} 

// if you prefer the opposite function 
function hasAllUniqueDigits($num) { 
    return (!hasDuplicateDigits($num)); 
} 

$numbers = range(10000, 99999); 

foreach ($numbers as $num) { 
    if (!hasDuplicateDigits($num) && (sumOfDigits($num) == 30)) { 
     print $num . "\n"; 
    } 
} 

Answer 4

यह शायद पर्याप्त तेज़ है:

<?php 

$digitCount = 5; 
$sum = 30; 

function getAnswer($b) 
{ 
     $a = ""; 
     $i = 1; 
     while ($b) 
     { 
       if ($b & 1) $a .= "$i "; 

       $b >>= 1; 
       ++$i; 
     } 
     return $a; 
} 

for ($b = 0; $b < 512; ++$b) 
{ 
     $v = 0; 
     $c = 0; 
     $i = 1; 

     $s = $b; 
     while ($s) 
     { 
       if ($s & 1) 
       { 
         if (++$c > $digitCount) continue 2; 
         $v += $i; 
       } 
       $s >>= 1; 
       ++$i; 
     } 

     if ($c == $digitCount && $v == $sum) 
     { 
       echo getAnswer($b)."\n"; 
     } 
} 

?> 

Answer 5

युग्म कोड का उपयोग करना here से

foreach(new Combinations("123456789", 5) as $p) 
    $r[array_sum(str_split($p))] .= "$p "; 
print_r($r); 

परिणाम

[15] => 12345 
[16] => 12346 
[17] => 12347 12356 
[18] => 12348 12357 12456 
[19] => 12349 12358 12367 12457 13456 
[20] => 12359 12368 12458 12467 13457 23456 
[21] => 12369 12378 12459 12468 12567 13458 13467 23457 
[22] => 12379 12469 12478 12568 13459 13468 13567 23458 23467 
[23] => 12389 12479 12569 12578 13469 13478 13568 14567 23459 23468 23567 
[24] => 12489 12579 12678 13479 13569 13578 14568 23469 23478 23568 24567 
[25] => 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567 
[26] => 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568 
[27] => 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569 34578 
[28] => 13789 14689 15679 23689 24589 24679 25678 34579 34678 
[29] => 14789 15689 23789 24689 25679 34589 34679 35678 
[30] => 15789 24789 25689 34689 35679 45678 
[31] => 16789 25789 34789 35689 45679 
[32] => 26789 35789 45689 
[33] => 36789 45789 
[34] => 46789 
[35] => 56789 

यह प्यारा नहीं है?

Answer 6

मेरा मानना ​​है कि इस सबसेट योग समस्या के रूप में जाना जाता है:

http://mathworld.wolfram.com/SubsetSumProblem.html

Answer 7

आइए लिखने च (30,5,1) अपने समस्या का जवाब के लिए। 30 वांछित राशि इंगित करता है, 5 अंक की संख्या इंगित करता है जो वांछित राशि में जोड़ना चाहिए, और 1 न्यूनतम स्वीकार्य अंक इंगित करता है। इस रूप में, आप समस्या को दोबारा हल कर सकते हैं। उदाहरण के लिए,

च (30,5, ख) = योग _{(i = 1..9)} च (30-ए, 4, मैं + 1)

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