Неудобные критерии при генерации случайной последовательности

Question

Что мне нужно сделать, чтобы сгенерировать последовательность неповторяющихся целых чисел в заданном диапазоне, которая соответствует определенным критериям, которые у меня есть?

Вот критерии:

1. Используйте только цифры от 1 до MAX (скажем, 9).
2. Числа не могут повторяться в последовательности, кроме:
   2a.Два из первых 5 чисел из последовательности должны быть повторены.
   2b.Эти два числа должны повторяться в случайных точках в последних 5 местах в последней последовательности (последние 5 включают повторы).

Например: SET: 1,2,3,4,5,6,7,8,9

Случайная последовательность(с повторениями):
2,4,6,9,3,1,5,2,8,7,3
r, , , ,r, , ,x, , ,x

Здесь я указал числа, которые были случайно выбраны для повторения (из первых 5 в случайной последовательности) с помощью r и точки вставки, в которых они были расположены случайным образом (в последние 5 последней последовательности) с x.

. Любая помощь в выяснении этого очень ценится.Фактическое использование будет немного сложнее, чем это, но я знаю, что мне нужно будет сделать, как только я смогу это сделать.

Редактировать

Чтобы прояснить немногоболее того, у меня 1-20, и мне нужна случайная последовательность из 22 цифр.Каждый номер должен быть использован, два будут использоваться дважды, как обсуждалось в моем оригинальном посте.Я выбрал 10 выше, чтобы немного упростить.Я должен быть в состоянии адаптировать логику, которую вы все дали.

Answer 1

Слово предупреждения об этом решении.Я бы не использовал его для большого набора чисел.Если бы я делал это то же самое решение для гораздо большего набора, я бы использовал array_splice для удаления выбранных членов из массива.Поскольку вы получаете гораздо больше места, поиск неиспользуемого числа в вашем диапазоне становится довольно дорогим и требует лучшего решения, чем приведенный ниже метод грубой силы.

Это создаст половину вашего целевого набора.Вы будете называть это дважды, один раз для каждой половины.

function build_half($min, $max, $num_elements, $arr = array() ){

  while( count($arr) <= $num_elements)
   {
      $candidate = rand($min, $max);
      if( !in_array($candidate, $arr))
        {
          array_push($arr, $candidate);
        }
    }
   return $arr;
}

Это будет извлекать элементы $ this_many из массива.

function random_grab($arr, $this_many){      // don't try this on the subway
  $nums_to_repeat = array();

  // catch some edge cases...
  if( $this_many > count($arr) )
    {
      return FALSE;
    }
  else if( $this_many == count($arr) )
    {
      return shuffle($arr);
    }

  while( count($nums_to_repeat) <= $this_many) 
    {
      $rand_key = rand(0, count($arr) - 1);

      if( ! in_array($arr[$rand_key], $nums_to_repeat))
        {
          array_push($nums_to_repeat, $arr[$rand_key]);
        }
    }
 return $nums_to_repeat;
}

Это довольно специализированный случай, но его можно сделать более общим, допустив, чтобы смещенный пол и потолок передавались в качестве параметров.Для вашей задачи их будет 5 и 9, поэтому мы просто получим их напрямую.

function random_insert_2nd_half($target, $source){
  $offsets_consumed = array();
  $num_elements = count($target);

  while( count($source) > 0 )
    {
      $offset = rand( ($num_elements/2), $num_elements - 1);

      if( ! in_array( $offset, $offsets_consumed)
        {
          $arr[$offset] = array_pop($nums_to_repeat);
        }
    }
}

Хорошо, так что после того, как все это сделано, давайте приступим к работе.

// Generate the first half of the array
$my_array = $repeated_nums = array();
$my_array = build_half(1, 10, 5);

// then grab the 2 random numbers from that first half.
$repeated_nums = random_grab($my_array, 2);

// So now we have our random numbers and can build the 2nd half of the array.
// we'll just repeat the call to the first function.
$my_array = build_half(1, 10, 5, $my_array);

// Then swap out two of the values in the second half.
$my_array = random_insert_2nd_half($my_array, $repeated_nums);

// at this point $my_array should match what you are looking for.

Answer 2

Надеюсь, это поможет вам:

$max = 20;    // max value
$repeats = 2; // numbers to be repeated

$nums = range(1, $max);
shuffle($nums);

$halfPoint = ceil($max / 2);
$firstHalf = array_slice($nums, 0, $halfPoint);

$repeaters = array_intersect_key($firstHalf, array_flip(array_rand($firstHalf, $repeats)));
$secondHalf = array_merge(array_slice($nums, $halfPoint), $repeaters);
shuffle($secondHalf);

$result = array_merge($firstHalf, $secondHalf);

var_dump(join(',', $result));

Answer 3

$max = 15;

$array = array(1, $max);
for($x = 1; $x <= $max; $x++)
{ $array[$x] = rand(1, $max); }

$firstDup = $array[rand(1,5)];
$secondDup = $firstDup;
do { $firstDup = $array[rand(1,5)];
} while($firstDup == $secondDup);

do { $array[rand($max-5,$max)] = $firstDup;
} while(!in_array($firstDup,array_slice($array,$max-5,5)));

do { $array[rand($max-5,$max)] = $secondDup;
} while(!in_array($secondDup,array_slice($array,$max-5,5)));

Answer 4

Если я вас правильно понимаю, у вас есть от 1 до N случайных чисел, которые должны использоваться в перестановке из 10 наборов с некоторыми конкретными критериями относительно повторений.В php я предлагаю следующее (не считая php-internals) решение O (n):

//Generate a full list of keys
$source = range(1, MAX);
//NOTE: if MAX < 10, you must pad the array

//Get a random group of 10 of the keys
$input = array_rand(array_flip($source), 10);

//Shuffle (can be done later as well; this is the randomization).
//array_rand() does not change order.
shuffle($input);

//Select the first of 5 that must be repeated in the last 5
$one = rand(0, 4);
$onev = $input[$one];

//Remove this array key to prevent collisions with the second of 5
$input = array_diff($input, array($onev));

//Select a random index in the last 5 to be replaced with $one
$rep = rand(5, 9);
$repv = $input[$rep];

//Remove this array key to prevent collisions with the other to-be-replaced
$input = array_diff($input, array($repv));

//Acquire the new keys list of input now that two elements have been removed
$keys = array_slice(array_keys($input), 0, 3);
//Select the second-of-5 to replace in the last 5.  No worry of collision now.
$two = array_rand($keys, 1);
$two = $keys[$two];

//Select the second from the last-of-5 to be replaced by $two
//No worry of collision because the other index is removed.
$keys = array_slice(array_keys($input), 4, 8);
$rept = array_rand($keys, 1);
$rept = $keys[$rept];

//Replace one of the last-of-five with one of the first-of-five
$input[$rept] = $input[$two];

//Restore removed keys as well as perform replacement of other last-of-five
$input[$one] = $onev;
$input[$rep] = $onev;

//re-randomize based on shuffle
ksort($input);

Нет циклов, нет условий.

Answer 5

Для генерации отдельных чисел в диапазоне вы можете использовать что-то вроде этого:

$arr_num = array();

while(count($arr_num)<=7)
{
  $num = rand(1, 9);
  if (!in_array($num, $arr_num))
  {
    $arr_num[] = $num;
  }
}

$ arr_num теперь имеет 8 различных элементов. Выберите пять элементов массива:

for ($i=0; $i<=4; $i+=1)
{
  $new_arr[$i] = $arr_num[$i];
}

Теперь выберите два числа из чисел $ new_arr:

$r1 = array_rand($new_arr);
$r2 = array_rand($new_arr);

Теперь вы можете вставить эти числа в исходный массив в двух из последних случайных позиций. Надеюсь, это помогло!

Answer 6

Я предполагаю, что когда вы говорите «неповторяющийся», вы имеете в виду «отличный» (уникальный), а не «в конечном итоге становится периодическим» (как в «цифры числа пи не повторяются»)

1. Генерируйте n различных целых чисел в вашем диапазоне.
2. Выберите два из первых 5. Назовите эти a и b .
3. Удалить последние 3 из списка.
4. Вставить a в позиции 0, 1, 2 или 3 в подсписке.
5. Вставить b в позиции 0, 1, 2, 3 или 4. в подсписке.
6. Добавить подсписок обратно в конец списка.

Удаление подсписка ненеобходимо, но упрощает концептуализацию.

Не очевидно, что делать, если n + 2 меньше 10. В частности, этот алгоритм может завершиться сбоем при n <5 и вернуть неправильный результат для n = 7. </p>