Выборка n случ. неповторяющихся чисел из x кол-ва?

Royal Flash

-=MaestrO=-
Выборка n случ. неповторяющихся чисел из x кол-ва?

Есть задача: выбрать 10 случайных значений (значения: 1, 2, 3, 4, ... 200) из 200., и чтобы значения не повторялись ни в коем случае (23, 23, 1, 109, 187, 2 .... - 2 раза 23 быть не должно). Подскажите алгоритм, или, лучше, код программки...
 

Сергей123

Новичок
С тебя куча баксов

Вывести K случайных неповторяющихся чисел из диапазона [1; N] каждое:

[в коде - ошибка (спасибо, .des.), исправлю позже...]

PHP:
for ( $i = 1; $i <= $K; $i++ ) {

    $r = mt_rand($i, $N);

    if ( ! isset ($arr[$r]) ) {

        echo $r;

    } # if
    else {

        echo $arr[$r];

    } # else

    $arr[$r] = $i;

} # for
 

c0dex

web.dev 2002-...
Команда форума
Партнер клуба
http://ru3.php.net/rand для диапазона 1-200, заносим в массив значение, при следующем занесении тестим на наличие уже такого значения в массиве, если есть повторяем выборку
 

Royal Flash

-=MaestrO=-
Гм.. Кому просто, а кому и не просто :) Может, всетаки, код? Там же написать 2 минуты :) - маленький цикл....
 

Сергей123

Новичок
c0dex
есть же алгоритм сложности O(K)

-~{}~ 06.04.05 17:30:

Royal Flash
не две, а три (если знаешь алгоритм)
 

Royal Flash

-=MaestrO=-
Бресь Сергей За код спасиба, конечно... Вот только, я так думаю, твой пример не отвечает условию: "неповотряющихся чисел". Ведь есть вероятность, что $r будет 2 раза 23?
 

.des.

Поставил пиво кому надо ;-)
:) php иногда радует своим подходом к именованию функций и передачи в них параметров .
 

Royal Flash

-=MaestrO=-
Вот нашел функцию - array_rand ( array input [, int num_req] )

for ($i=1; $i<201; $i++)
{
$k[$i] = $i;
}
$arr = array_rand ($k, 10);

Так правильно?
 

.des.

Поставил пиво кому надо ;-)
Бресь Сергей ну почему же грустно он не просто копирует код, а пытается написать что то сам..
вполне достойное желание Ж)
 

Сергей123

Новичок
.des.
я бы подискутировал с тобой, но у меня до сих пор выполняется твой код при $n == 20000000 :)
от чего жутко сложно ходить по форуму (и не только) :)
 

.des.

Поставил пиво кому надо ;-)
Бресь Сергей первое правило оптимизации подсказать?

-~{}~ 06.04.05 18:32:

Кстати, результат работы Вашего алгоритма при $N=20, $K=14.

11,4,8,19,1,15,14,13,20,7,5,18,17,4,

по моему это не совсем то, что мы ожидали увидеть :)
 

Royal Flash

-=MaestrO=-
Так код, приведенный выше можно использовать? От чего так грустно? :)
 

c0dex

web.dev 2002-...
Команда форума
Партнер клуба
Royal Flash
тебе .des. дал вариант, что ты еще хочешь?
 

c0dex

web.dev 2002-...
Команда форума
Партнер клуба
Royal Flash
не вижу смысла в горке кода в случае где можно обойтись строкой
print_r(array_rand(range(1, 200), 10));
 

Royal Flash

-=MaestrO=-
c0dex
Твой вариант не правилен изначально..., хотя за идею - респект. Дело в том, что функция array_rand () (прочитав все варианты, решил почитать мануал :)) возвращает не значения, а ключи массива, поэтому вариант
PHP:
print_r(array_rand(range(1, 200), 10));
время от времени возвращает 0 - (ключ массива), хотя в задании, нуля то как-раз и нет... Я вот написал следующее, что работает на 100%:

PHP:
$k = range(1, 200);
shuffle($k);
$t = array_rand($k, 10);
for ($i = 0; $i < count($t); $i++)
  {
  $m = $t[$i]; // выбираем произвольные ключи массива $k
  echo $k[$m].' -<br>';
  }
Помимо всего прочего, тут возвращаются еще и непоследовательные значения, например "74 54 131 127 99 90 84 143 152 129" в отличие от твоего варианта, который возвращает нечто, наподобии: "( [0] => 0 [1] => 21 [2] => 29 [3] => 60 [4] => 81 [5] => 89 [6] => 111 [7] => 185 [8] => 190 [9] => 195 ) ", т.е. числа идут подряд.

Может кто-то подскажет оптимизацию моего варианта?
 
Сверху