Как разложить число в PHP?

Question

[object_Object]

Суть идеи:
Допустим у меня есть ip 192.168.0.1
Сумма всех чисел 28 (1 + 9 +2 +1 + 6 + 8 + 0 + 1 = 28)
Как мне из числа 28 получить все возможные вариации IP адресов (ноль в т.ч.)?

Заранее всем спасибо!

Comments

[Василий Банников]

Перебором

Answer 1

[Андрей Ежгуров]

Можно без перебора всех вариантов стразу получать искомые IP-адреса - если идти не от чисел, а от суммы цифр каждого числа.
В результате скрипт, в котором echo было заменено на ++$count, проработал менее 14 секунд и насчитал 112279695 адресов.

$tbl = array_fill(0, 20, []);
for ($i = 0; $i < 256; ++$i) { $tbl[intdiv($i, 100) + intdiv($i, 10) % 10 + $i % 10][] = $i; }
for ($i = 0; $i <= 19; ++$i) {
    for ($j = 0; $j <= min(19, 28 - $i); ++$j) {
        for ($k = max(0, 28 - 19 - $i - $j); $k <= min(19, 28 - $i - $j); ++$k) {
            foreach($tbl[$i] as $v1) {
                foreach($tbl[$j] as $v2) {
                    foreach($tbl[$k] as $v3) {
                        foreach($tbl[28 - $i - $j - $k] as $v4) {
                            echo $v1, '.', $v2, '.', $v3, '.', $v4, "\n";
                        }
                    }
                }
            }
        }
    }
}

Сумма цифр числа в диапазоне 0..255 имеет диапазон значений от 0 (0) до 19 (199).
$tbl - массив списков чисел в диапазоне 0..255, имеющих одинаковую сумму цифр.

Comments

[object_Object]

Пиздос, а я еще собирался чекать их хеши и сравнивать

Answer 2

[Slava Rozhnev]

Можно решить в лоб: перебором всех значений - медленно но верно:

<?php
function number_sum($num)
{
    return array_sum(str_split($num));
}

$sum = 28;

for ($b1 = 1; $b1 < 256; $b1++) {
    for ($b2 = 0; $b2 < 256; $b2++) {
        for ($b3 = 0; $b3 < 256; $b3++) {
            for ($b4 = 0; $b4 < 256; $b4++) {
                if ((
                    number_sum($b1) +
                    number_sum($b2) +
                    number_sum($b3) +
                    number_sum($b4)
                ) == $sum) {
                    echo "$b1.$b2.$b3.$b4" . PHP_EOL;
                }
            }
        }
    }
}

Результат запуска PHP

Наверно можно быстрее, но если честно, лень

Comments

[object_Object]

Как раз только что пришло в голову написать подобный скрипт, но спасибо что ответил раньше!

[Developer]

object_Object, перебор - это первое, что приходит в голову и первое, от чего нужно отказываться.
Посчитай время на брутфорс

[Slava Rozhnev]

Все зависит от того что дороже: время программиста или процессорное время.
Например мой час работы стоит $50, месяц работы сервера $5 то есть в данном случае при одноразовой задаче брутфорс оправдан.
Если же например данную задачу нужно исполнять миллион раз то тогда я потрачу несколько часов (дней) и напишу оптимальный алгоритм
Так что, все относительно

Answer 3

[xmoonlight]

192.168.0.1
Это алфавит от 0 до 255.
Перестановки - это анаграмма для слова из 4-х букв.
Можно сделать хеш через простые числа:

0 -> 2
1 -> 3
2 -> 5
3 -> 7
...
255 -> ...

Затем перемножить простые 4-е числа (справа от стрелки), соответствующие одному из 4-х значений (от 0 до 255: A.B.C.D) в ip-адресе: результат при любой перестановке всегда будет одинаковым.

Comments

[Сергей Соколов]

Это усложнение никак не поможет с тем, что сумма цифр у 123 и 132 одинаковая.

[xmoonlight]

Сергей Соколов, не цифры, а числа.
Я в ответе указал: A.B.C.D