Меню
Что нового?

10 случайных, неповторяющихся чисел

Viktor_Rez

Viktor_Rez

Новичок
Мои пять копеек
PHP: 
function get_rand($mn, $mx, $mall) // $mall уникальных чисел от $mn до $mx 
{
        while(count($ar) < $mall)
        {
                $ar = Array();
                for($i = 0; $i < $mall; $i++)
                {
                        $ar[] = rand($mn,$mx);
                }

                $ar = array_unique($ar);
        }
        return $ar;
}

print_r(get_rand(1,10,10));
 

Gas

может по одной?
хоть логика немного и отличается, но всё равно почти что этот вариант

и $ar лучше перед while инициализировать, тогда array_slice добавить (такой вариант тоже вроде был) - а если этого не сделать, можно сказать что это наверное самый оптимистичный алгоритм из представленных.
 
xInOrK

xInOrK

Новичок
А что насчёт такого варианта ?
PHP: 
function generate_numbers($num, $min, $max) {
  $rand[0]=mt_rand($min, $max);
  for ($i=1;$i<$num;++$i) {
    do {
      $check=true;
      $rand[$i]=mt_rand($min, $max);
      for ($ii=0;$ii<(count($rand)-1);++$ii) {
        if ($rand[$i] == $rand[$ii] && $check) {
          $check=false;
          break;
        }
      }
    } while (!$check);
  }
  return $rand;
}

print_r(generate_numbers(10, 1, 1000000));
 
zerkms

zerkms

TDD infected
Команда форума
не вникая в алгоритм - 3 вложенных цикла это просто пздц :))))))
 
xInOrK

xInOrK

Новичок
Ну по скорости помоему нормально, на лаптопе.
0.018656969070435 seconds.
 
HraKK

HraKK

Мудак
Команда форума
у меня быстрее ЦМС генерирует сайт с меню новостми и тд :)
Наш алгоритмы в тысячи или сотнитысяч быстрее))) а так да - нормальная скорость))))))))
 

ksnk

прохожий
А почему у меня эта тема всплыла ?
Ну и чтобы 2 раза не вставать, задачка забавна, не прошло и 11 лет :) ...
PHP: 
function generate_unique_numbers($num, $min, $max) {
    $result=[];
    for($i=0;$i<$num;$i++){
        $result[]=mt_rand($min, $max-$i);
    }
    for($i=0;$i<$num-1;$i++){
        for($j=$i+1;$j<$num;$j++){
            if($result[$j]<=$result[$i] )$result[$j]++;
        }
    }
    return $result;
}

print_r(generate_unique_numbers(10, 1, 1000000));
Сложность никак не зависит от максимального.
 
WMix

WMix

герр M:)ller
Партнер клуба
PHP: 
    function generate_unique_numbers($num, $min, $max) {
        if($max-$min <= $num){
            throw new \Exception('impossible to generate ...');
        }
        $out=[];
        while(count($out)<$num){
            $rand = random_int($min, $max);
            if(!isset($out[$rand])){
                $out[$rand] = true;
            }
        }
        return array_keys($out);
    }
 

ksnk

прохожий
@WMix, ежели что, то в твоем случае, вообще говоря, неопределенное количество вызовов функции генерации случайного числа, а в моем - ровно num. И по моему - я что-то такое тут уже видел, с isset в результате...
 
WMix

WMix

герр M:)ller
Партнер клуба
@ksnk, это да, но твое читать невозможно, да и неповторяемость слегка утеряна
 

ksnk

прохожий
Насчет читать невозможно - спорить не могу, а вот насчет случайность утеряна - это о чем ? Если претензии к функции mt_rand - то ладно, использование random_int более кошерно, а если к алгоритму - не вижу в чем...
 
WMix

WMix

герр M:)ller
Партнер клуба
@ksnk, неповторяемость я поправил, вот вызовы твоей,

Код: 
 print_r(generate_unique_numbers(10, 1,15));
Array
(
    [0] => 1
    [1] => 2
    [2] => 5 <<
    [3] => 4
    [4] => 5 <<
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
    [9] => 10
)
php > print_r(generate_unique_numbers(10, 1,15));
Array
(
    [0] => 13
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 8 <<
    [7] => 8 <<
    [8] => 9
    [9] => 10
)
php > print_r(generate_unique_numbers(10, 1,15));
Array
(
    [0] => 6
    [1] => 12
    [2] => 7
    [3] => 4
    [4] => 8 <<
    [5] => 6
    [6] => 8 <<
    [7] => 9
    [8] => 10
    [9] => 11
)
про случайность: вероятность что есть "случайное" число на 1 выше чем предыдушее возрастает
 
  • Like
Реакции: ksnk

ksnk

прохожий
Опс, ашипка... слишком самонадеянно получилось :(
PHP: 
function generate_unique_numbers($num, $min, $max)
{
    $sorted = [];
    for ($i = 0; $i < $num; $i++) {
        $rand = mt_rand($min, $max - $i);
        if(!empty($sorted))
            foreach ($sorted as $s) {
                if ($rand >= $s) $rand++;
                else break;
            }
        array_push($sorted, $rand);
        asort($sorted);
    }
    return $sorted;
}
вот так будет правильнее, но при этом несколько теряется порядок генерации случайных чисел, хотя его можно восстановить перебирая ключи результирующего массива.
p.s. хотя теперь "эффективность" будет упираться в неопрееленное количество вызовов генератора с одной стороны, или 10 вызовов сортировки массива, с другой... В общем - уже совсем не так все однозначно выглядит...
 
fixxxer

fixxxer

К.О.
Партнер клуба
Да сколько можно. 10 лет прошло.

Пусть надо выбрать K целых чисел от 0 до N-1.
1. Если N небольшое, то range() и shuffle
2. Если N велико, то:
2.1. Недетерменированный алгоритм (очевидный, сто раз озвученный) с хэш-таблицей и while, при условии N >> K вероятность пересечений несущественна.
2.2. Если детерминированность алгоритма предпочтительнее его сложности (скажем, K/N достаточно велико), вариант, который я писал на 4-й странице, можно модифицировать, развернув "наоборот", тогда insertion sort комбинируется с поиском позиции и инкрементом налету, и получается вроде неплохо:

PHP: 
function random_ints_unique($count, $min, $max) {
    $result = [];
    for ($i = 0; $i < $count; ++$i) {
        $value = random_int($min, $max - $i);
        for ($pos = 0; $pos < $i; ++$pos) {
            if ($result[$pos] > $value) {
                break;
            }
            ++$value;
        }
        array_splice($result, $pos, 0, $value);
    }
    return $result;
}
/EOT

UPD: исправил баг, на который указал @ksnk.
 
Последнее редактирование:

ksnk

прохожий
Не, не EOT :)
Код: 
print_r(random_ints_unique(10, 1, 15));
получается
Код: 
Array
(
    [0] => 1
    [1] => 4
    [2] => 5
    [3] => 6
    [4] => 9
    [5] => 10
    [6] => 11
    [7] => 14
    [8] => 16
    [9] => 24
)
Числа > 15
 

ksnk

прохожий
WMix написал(а):
про случайность: вероятность что есть "случайное" число на 1 выше чем предыдушее возрастает
Нажмите для раскрытия...
Должно ли это значить, что распределение будет перекошено в "большую" сторону?
Вот код, который считает количество попаданий каждого числа
PHP: 
$max=20;
$num=10;

function random_ints_unique($count, $min, $max) {
    $result = [];
    for ($i = 0; $i < $count; ++$i) {
        $value = random_int($min, $max - $i);
        for ($pos = 0; $pos < $i; ++$pos) {
            if ($result[$pos] > $value) {
                break;
            }
            ++$value;
        }
        array_splice($result, $pos, 0, $value);
    }
    return $result;
}

$stat=[];

for($y=1;$y<=$max;$y++) $stat[$y]=0;

for($i=0;$i<100000;$i++){
    $x=random_ints_unique($num, 1, $max);
    foreach($x as $ix) $stat[$ix]++;
}
echo array_sum(array_slice($stat,1,$max>>1)).' '.array_sum(array_slice($stat,$max>>1+1,$max>>1));
Код вычисляет сумму количества попавших чисел о 1 до 5 и от 6 до 10. Вот 4 последовательных запуска скрипта
Код: 
500284 500338
500091 499404
499778 500269
500260 499673
Никакого "перекоса" вероятности не вижу.
 
Vladson

Vladson

Сильнобухер
Эх, такой пятничный угар пропустил. Когда увидел название, сразу подумал о варианте @WMix, имхо идеал. Ни добавить, ни убавить.
 
Войдите или зарегистрируйтесь для ответа.
Сверху