生成随机序列时的尴尬标准

Question

我需要做什么才能生成给定范围内满足我的特定标准的非重复整数序列？

标准如下：

1. 仅使用 1 到 MAX 之间的数字（假设为 9）。
2. 数字在序列中不能重复，除了：
   2a。序列中前 5 个数字中的两个必须重复。
   2b。这两个数字必须在最终序列的最后 5 个位置内的随机点上重复（最后 5 个位置包括重复）。

例如： 设置：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 以及用 x 随机放置它们的插入点（最终序列的最后 5 个）。

非常感谢任何帮助解决这个问题的帮助。实际使用会比这更复杂一些，但我知道一旦我能做到这一点我需要做什么。

编辑

为了澄清一点，我有 1-20，并且我需要一个 22 位随机序列。每个数字都必须使用，两个数字将使用两次，正如我在原始帖子中讨论的那样。我选择上面的10来简化一点。我应该能够适应你们所给出的逻辑。

Answer 1

我假设当你说“不重复”时，你的意思是“不同”（唯一）而不是“最终变成周期性”（如“圆周率的数字不重复”）

1. 生成n个不同的整数在你的范围内。
2. 从前 5 个中选择两个。将其命名为 a 和 b。
3. 从列表中删除最后 3 个。
4. 在子列表中的位置 0、1、2 或 3 处插入 a。
5. 在子列表中的位置 0、1、2、3 或 4 处插入 b。
6. 将子列表添加回列表末尾。

删除子列表不是必需的，但可以更容易概念化。

如果 n+2 小于 10，该怎么办并不明显。特别是，当 n < 10 时，该算法可能会崩溃。 5 并返回 n=7 的错误结果。

Answer 2

如果我理解正确的话，您有 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 3

关于此解决方案的警告。我不会将它用于大量数字。如果我对更大的集合执行相同的解决方案，我将使用 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 4

希望这能让你上路：

$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 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

$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)));