Come trovo tutti i set di N numeri a singola cifra e non ripetibili che sommano a una data somma in PHP?

Question

Diciamo che voglio trovare tutti i set di 5 numeri a cifra singola, non ripetibili che aggiungono fino a 30 ... Mi piacerebbe finire con [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] e [8,7, 6,5,4]. Ciascuno di questi set contiene 5 cifre non ripetitive che sommano fino a 30, la somma data.

Qualsiasi aiuto sarebbe molto apprezzato. Anche solo un punto di partenza per me da usare sarebbe fantastico.

Mi è venuto in mente un metodo, che sembra un lungo cammino: ottenere tutti i numeri univoci a 5 cifre (12345, 12346, 12347, ecc.), Sommare le cifre e vedere se è uguale a la somma data (ad es. 30). Se lo fa, aggiungilo alla lista dei possibili set corrispondenti.

Lo sto facendo per un progetto personale, che mi aiuterà a risolvere i puzzle di Kakuro senza effettivamente risolvere il tutto in una volta. Sì, potrebbe essere un imbroglio, ma è ... non è così male ...: P

Answer 1

Un approccio ingenuo sarebbe quello di incrementare una variabile da 12345 fino 98765 e per selezionare solo se ha cifre uniche e somma delle cifre è 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

So che ci sono algoritmi per questo, e saranno probabilmente forniti da altre persone, ma ecco una rapida semplificazione che puoi make: cerca tutti i set di 4 cifre singole che sommano a 21-29 (presumo che tu non stia contando 0 come cifra) e elimini solo quelli per cui 30- (la somma) è una delle cifre .

Se volessi provare qualcosa ancora più veloce, penserei di iniziare con 45678 e di modificarlo in modo incrementale aggiungendo 1 a una cifra e sottraendo 1 da un'altra cifra. Non sono sicuro di quanto bene funzionerebbe alla fine, però.

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

Questo è probabilmente sufficientemente veloce:

<?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

Utilizzando il codice combinazioni da here

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

risultato

[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 

Non è carino?

Answer 6

Credo che questo è noto come il problema sottoinsieme Somma: F Scrivi

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

Answer 7

Let (30,5,1) per la risposta al vostro problema. Il 30 indica la somma desiderata, il 5 indica il numero di cifre che dovrebbe aggiungere alla somma desiderata e 1 indica la cifra minima accettabile. In questa forma, puoi risolvere il problema in modo ricorsivo. Ad esempio,

f (30,5, b) = somma _{(i = 1..9)} f (30-i, 4, i + 1)

Ci sono effettivamente esaurendo il basso valore che sto verificando nella combinazione che cerchi. Se si pensa più attentamente al valore massimo possibile di i (non può essere troppo grande poiché è il minimo delle cifre) e si aggiungono alcune condizioni di salvataggio appropriate, allora si avrà una soluzione molto veloce.