У меня есть функция (из предыдущего вопроса, которая осталась без ответа), которая создает массив с 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 и / или отрицательных целых чисел .
Хорошо, эта проблема фактически вращается вокруг линейных последовательностей. При минимальном значении 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. Вы знаете свой первый номер. Теперь вы создаете последовательность из трех чисел, всего 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 * 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 }
После генерирования индекса сортировки перетасовывайте порядок индексов для дублирования значений, чтобы избежать прогонов в последовательности столкновений. (или просто перетасовать конечный результат, если заказ не имел значения)
Перемешать индексы обманов:
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) для каждого обмана. Затем регулировочный контур просто должен повторить попытку обхода, прежде чем применять настройку.