Дубликат замены оценивает в массиве с новыми случайным образом сгенерированными значениями
Я имею ниже функции (от предыдущего вопроса, который остался без ответа), который создает массив с n суммой значений. Сумма массива равна $max.
function randomDistinctPartition($n, $max) {
$partition= array();
for ($i = 1; $i < $n; $i++) {
$maxSingleNumber = $max - $n;
$partition[] = $number = rand(1, $maxSingleNumber);
$max -= $number;
}
$partition[] = $max;
return $partition;
}
Например: Если я установил $n = 4 и $max = 30. Затем я должен получить следующее.
array(5, 7, 10, 8);
Однако эта функция не принимает во внимание дубликаты и 0s. То, что я хотел бы - и пытался выполнить - должно генерировать массив с уникальными числами, которые составляют в целом мой предопределенный переменный $max. Никакие Дублирующиеся числа и № 0 и/или отрицательные целые числа.
2 ответа
Хорошо, эта проблема на самом деле вращается вокруг линейных последовательностей. При минимальном значении 1 рассмотрим последовательность:
f(n) = 1 + 2 + ... + n - 1 + n
Сумма такой последовательности равна:
f(n) = n * (n + 1) / 2
, поэтому для n = 4, например, сумма равна 10. Это означает, что если вы выбираете 4 разных чисел минимальная сумма без нулей и отрицательных чисел равна 10. Теперь сделайте обратное: если у вас всего 10 и 4 числа, то есть только одна комбинация из (1,2,3,4) .
Итак, сначала вам нужно проверить, по крайней мере, ваша сумма равна этой нижней границе. Если меньше, то комбинации нет. Если они равны, есть ровно одна комбинация. Если он выше, все усложняется.
А теперь представьте, что у вас всего 12 ограничений по 4 числа. Мы установили, что f (4) = 10. Но что, если первое (наименьшее) число равно 2?
2 + 3 + 4 + 5 = 14
Итак, первое число не может быть больше 1. Вы знаете свое первое число. Теперь вы генерируете последовательность из 3 чисел, всего 11 (от 12 до 1).
1 + 2 + 3 = 6
2 + 3 + 4 = 9
3 + 4 + 5 = 12
Второе число должно быть 2, потому что оно не может быть единицей. Это не может быть 3, потому что минимальная сумма трех чисел, начинающихся с 3, равна 12, и мы должны добавить к 11.
Теперь мы находим два числа, которые в сумме дают 9 (12 - 1 - 2), где 3 - это минимально возможный.
3 + 4 = 7
4 + 5 = 9
Третье число может быть 3 или 4. При обнаружении третьего числа фиксируется последнее. Две возможные комбинации:
1, 2, 3, 6
1, 2, 4, 5
Вы можете превратить это в общий алгоритм. Рассмотрим эту рекурсивную реализацию:
$all = all_sequences(14, 4);
echo "\nAll sequences:\n\n";
foreach ($all as $arr) {
echo implode(', ', $arr) . "\n";
}
function all_sequences($total, $num, $start = 1) {
if ($num == 1) {
return array($total);
}
$max = lowest_maximum($start, $num);
$limit = (int)(($total - $max) / $num) + $start;
$ret = array();
if ($num == 2) {
for ($i = $start; $i <= $limit; $i++) {
$ret[] = array($i, $total - $i);
}
} else {
for ($i = $start; $i <= $limit; $i++) {
$sub = all_sequences($total - $i, $num - 1, $i + 1);
foreach ($sub as $arr) {
array_unshift($arr, $i);
$ret[] = $arr;
}
}
}
return $ret;
}
function lowest_maximum($start, $num) {
return sum_linear($num) + ($start - 1) * $num;
}
function sum_linear($num) {
return ($num + 1) * $num / 2;
}
Вывод:
All sequences:
1, 2, 3, 8
1, 2, 4, 7
1, 2, 5, 6
1, 3, 4, 6
2, 3, 4, 5
Одна из реализаций этого состоит в том, чтобы получить все последовательности и выбрать одну случайным образом.Это дает то преимущество, что все возможные комбинации одинаково взвешиваются, которые могут быть полезны или необходимы для того, что вы делаете, а могут и не оказаться.
Это станет громоздким из-за больших сумм или большого количества элементов, и в этом случае вышеупомянутый алгоритм может быть изменен, чтобы возвращать случайный элемент в диапазоне от $ start до $ limit ] вместо каждого значения.
Я бы использовал ' область под треугольником 'формула ... как cletus (!?) Мне действительно придется уделять больше внимания вещам ...
В любом случае, я думаю, что сейчас это решение довольно элегантно, оно применяет желаемое минимальный интервал между всеми элементами, равномерно, равномерно масштабирует промежутки (распределение) для сохранения исходной суммы и выполняет работу нерекурсивно (за исключением сортировки):
Дан массив a () случайных чисел длины n
Создайте индекс сортировки s ()
и работайте с отсортированными интервалами a (s (0)) - a (s (1)), a (s (1)) - a (s (2)) и т. Д.
увеличивают каждый интервал на желаемый минимальный размер разделения, например 1 (это обязательно искажает их "случайность")
уменьшают каждый интервал в {{1} раз }} вычисляется для восстановления суммы ряда до того, что есть без добавленного интервала .
Если мы добавляем 1 к каждому ряду, мы увеличиваем сумму ряда на 1 * len
1, добавляемое к каждому из интервалов ряда, увеличивает сумму на: len * (len + 1) / 2 / / (треугольник? Паскаля)
Проект кода:
$series($length); //the input sequence
$seriesum=sum($series); //its sum
$minsepa=1; //minimum separation
$sorti=sort_index_of($series) //sorted index - php haz function?
$sepsum=$minsepa*($length*($length+1))/2;
//sum of extra separation
$unsepfactor100=($seriesum*100)/($seriesum+sepsum);
//scale factor for original separation to maintain size
//(*100~ for integer arithmetic)
$px=series($sorti(0)); //for loop needs the value of prev serie
for($x=1 ; $x < length; $x++)
{ $tx=$series($sorti($x)); //val of serie to
$series($sorti($x))= ($minsepa*$x) //adjust relative to prev
+ $px
+ (($tx-$px)*$unsepfactor100)/100;
$px=$tx; //store for next iteration
}
- все интервалы уменьшены на константу (неслучайный коэффициент деформации)
- разделение может быть установлено на другие значения {{1} } более одной реализации
- необходимо тщательно
настроить (обычно я тестирую и "калибрую")
, чтобы учесть ошибки округления. Вероятно, все увеличится примерно на 15 , затем отступите. Интервалы должны сохраниться, если все сделано правильно.
После создания индекса сортировки измените порядок индексов для дублирования значений, чтобы избежать запусков в последовательности конфликтующих рядов. (или просто перемешайте окончательный результат, если порядок никогда не имеет значения)
Перемешать индексы дубликатов:
for($x=1; $x<$len; $x++)
{ if ($series($srt($x))==$series($srt($x-1)))
{ if( random(0,1) )
{ $sw= $srt($x);
$srt($x)= $srt($x-1);
$srt($x-1)= $sw;
} } }
Некоторое минимальное нарушение может быть сделано для 'случайной последовательности', просто разделив дубликаты на минимально необходимый, вместо того, чтобы перемещать их больше, чем минимум - некоторая «случайная» сумма, которую искал вопрос.
Код здесь разделяет каждый элемент минимальным разделением, независимо от того, дублируется он или нет, это должно быть отчасти беспристрастным, но, возможно, переборщить. Код может быть изменен так, чтобы разделять дубликаты, просматривая их серию (sorti (n0: n1..len)) и вычисляя сепсум как + = minsep * (len-n) для каждого дублирования. Затем регулировочная петля просто должна снова проверить на наличие дефектов, прежде чем применять регулировку.