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

[Royal Flash]

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

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

 

[Сергей123]

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

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

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

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]

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

 

[Royal Flash]

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

 

[Сергей123]

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

-~{}~ 06.04.05 17:30:

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

 

[Royal Flash]

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

 

[.des.]

array_slice(array_shuffle(range(1,$n)), 0,$x);

 

[Сергей123]

Royal Flash
И что? Продолжай разбираться...

 

[c0dex]

shuffle =)

 

[.des.]

php иногда радует своим подходом к именованию функций и передачи в них параметров .

 

[Royal Flash]

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

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

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

 

[Сергей123]

[грустно]держите меня пятеро...[/грустно]

 

[.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]

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

 

[c0dex]

Royal Flash
тебе .des. дал вариант, что ты еще хочешь?

 

[Royal Flash]

c0dex
Чем плох мой вариант

 

[c0dex]

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

 

[Royal Flash]

c0dex
Твой вариант не правилен изначально..., хотя за идею - респект. Дело в том, что функция array_rand () (прочитав все варианты, решил почитать мануал ) возвращает не значения, а ключи массива, поэтому вариант

print_r(array_rand(range(1, 200), 10));

время от времени возвращает 0 - (ключ массива), хотя в задании, нуля то как-раз и нет... Я вот написал следующее, что работает на 100%:

$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 ) ", т.е. числа идут подряд.

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