Nasıl N tek haneye bütün setleri bulur, PHP belirli bir toplamı kadar eklemek numaralarını olmayan yinelenen?

6 Cevap php

Diyelim ki 30 kadar eklemek 5 tek haneli, non-yinelenen sayılar tüm setleri bulmak istediğinizi varsayalım ... Ben ile bitirmek istiyorum [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] ve [8,7,6, 5.4]. Bu setleri her 30 kadar eklemek 5 sigara yinelenen basamak, verilen toplamını içerir.

Herhangi bir yardım büyük mutluluk duyacağız. Hatta bana kullanmak için sadece bir başlangıç ​​noktası harika olurdu.

Tüm benzersiz 5 haneli numaralar (12345, 12346, 12347, vb) olsun, basamak eklemek ve verilen toplamına eşittir (bkz: ben bu konuda giden uzun bir yol gibi görünüyor bir yöntem ile geldi örneğin 30). Öyle ise, olası eşleşen setleri listesine eklemek.

Ben aslında bir kerede her şeyi çözmeden Kakuro bulmaca çözme bana yardımcı olacak, kişisel bir proje için yapıyorum. Evet, bu hile olabilir, ama o kadar da kötü değil ... Neler ...: P

6 Cevap

Saf bir yaklaşım 12345 kadar 98765 ve benzersiz basamak ve basamak toplamı var sadece bunu seçmek için bir değişken artırmak için olurdu 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

Bu muhtemelen yeterince hızlı:

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

?>

here adlı kombinasyonlar kodunu kullanarak

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

sonuç

[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

şirin değil mi?

Bunun için algoritmalar olduğunu biliyorum, ve muhtemelen diğer insanlar tarafından temin edilecektir, ama burada yapabileceğiniz bir hızlı basitleştirme bulunuyor: 21-29 kadar eklemek 4 tek haneli tüm setleri için bakmak (ben sen varsayarak yaşıyorum bir rakam olarak 0 sayma) ve sadece 30 olduğu için olanları ortadan kaldırmak değil - (toplamı) basamak biridir.

Ben bile daha hızlı bir şeyler denemek istedim, ben 45678 ile başlayan ve adım adım bu değiştirme hakkında düşünmek istiyorum bir rakama 1 ekleme ve başka rakam 1 çıkartılarak tarafından. Emin olsa da, sonunda çalışmak istiyorum değil, nasıl iyi.

Ben bu alt küme toplamı problemi olarak bilinir inanıyorum:

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

Senin sorunun cevabı için f (30,5,1) yazalım. 30 arzu edilen bir miktar gösterir, 5 İstenen toplamına eklemek gerekir basamak sayısını gösterir ve 1 minimal olarak kabul edilebilir bir basamak gösterir. Bu formda, özyinelemeli sorunu çözebilir. Örneğin,

f (30,5, b) = sum (i = 1..9) f (30-i, 4, i +1)

We are effectively exhausting over the lowest value i occurring in the combination you seek. If you think more carefully about the maximum possible value of i (it can't be too large since it's the minimum of the digits), and add some appropriate bail-out conditions, then you'll have a very fast solution.

etiketler