Как я нашел бы все наборы одноразрядных, неповторяющихся чисел N, которые составляют в целом данную сумму в PHP?
Скажем, я хочу найти все наборы 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). Если это делает, добавьте его к списку возможных наборов соответствия.
Я делаю это для персонального проекта, который поможет мне в решении загадок Kakuro, на самом деле не решая все это сразу. Да, это может обманывать, но это... дело не в этом плохо... :P
6 ответов
Наивным подходом было бы увеличить переменную с 12345 до 98765 и выбирать ее, только если она имеет уникальные цифры, а сумма цифр равна 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";
}
Я знаю, что для этого есть алгоритмы, и они, вероятно, будут предоставлены другими людьми, но вот одно быстрое упрощение, которое вы можете сделать: найдите все наборы из 4 однозначных цифр, которые в сумме дают 21–29 (я предполагаю вы не считаете 0 как цифру) и просто удалите те, для которых 30- (сумма) является одной из цифр.
Если бы я хотел попробовать что-то еще быстрее, я бы подумал о том, чтобы начать с 45678 и постепенно изменять это, добавляя 1 к цифре и вычитая 1 из другой цифры. Хотя не уверен, насколько хорошо это сработает в итоге.
Это, вероятно, достаточно быстро:
<?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";
}
}
?>
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";
}
}
Использование кода комбинаций из здесь
foreach(new Combinations("123456789", 5) as $p)
$r[array_sum(str_split($p))] .= "$p ";
print_r($r);
result
[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
разве это не мило?