Равномерно выберите N elems из массива
Я должен равномерно выбрать n элементы из массива. Я предполагаю, что лучший способ объяснить примером.
скажите, что я имею:
массив [0,1,2,3,4] и я должен выбрать 3 числа.. 0,2,4.
конечно, если длина массива <= n, я просто должен возвратить целый массив.
Я вполне уверен существует определенный алгоритм для этого, попытка искать, и я смотрел на Введение в алгоритмы, но не мог найти ничего, что удовлетворило мои потребности (вероятно, пропустил его),
Проблема, которую я имею, состоит в том, что я не могу выяснить способ масштабировать это до любого массива [p.. q], выбирая N равномерно элементы.
примечание: Я не могу только выбрать ровные элементы из примера выше..
Пара других примеров;
массив [0,1,2,3,4,5,6], 3 элемента; я должен добраться 0,3,6
массив [0,1,2,3,4,5], 3 элемента; я должен добраться 0, или 2 или 3, и 5
Править:
больше примеров:
массив [0,1,2], 2 elems: 0,2
массив [0,1,2,3,4,5,6,7], 5 elems: 0,2, или 3 или 4, 5,7
и да, я хотел бы включать первые и последние элементы всегда.
РЕДАКТИРОВАНИЕ 2:
то, что я думал, было чем-то как.. сначала + последний элемент, затем проложите себе путь с помощью среднего значения. Хотя я засовывался/путался при попытке сделать так.
Я буду смотреть на алгоритм, который Вы отправляете.спасибо!
РЕДАКТИРОВАНИЕ 3:
Вот является souped версией incrediman решения с PHP. Работы с ассоциативными массивами также, при сохранении ключей.
Можно, вероятно, реализовать Итератор, но я не должен брать его настолько далеко.
4 ответа
Наслаждайтесь! (псевдокод):
function Algorithm(int N,array A)
float step=(A.size-1)/(N-1) //set step size
array R //declare return array
for (int i=0, i<N, i++)
R.push(A[round(step*i)]) //push each element of a position which is a
//multiple of step to R
return R
Вероятно, самой простой ошибкой здесь будет приведение step к целому числу или округление его в начале. Однако, чтобы быть уверенным, что будут извлечены правильные элементы, вы должны объявить step как число с плавающей точкой, и округлять кратные step по мере итерации по массиву.
Проверенный пример здесь в php:
<?
function Algorithm($N,$A){
$step=(sizeof($A)-1)/($N-1);
for ($i=0;$i<$N;$i++)
echo $A[round($step*$i)]." ";
echo "\n";
}
//some of your test cases:
Algorithm(3,array(1,2,3));
Algorithm(5,array(0,1,2,3,4,5,6,7));
Algorithm(2,array(0,1,2));
Algorithm(3,array(0,1,2,3,4,5,6));
?>
Outputs:
1 2 3
0 2 4 5 7
0 2
0 3 6
(вы можете увидеть свои тестовые примеры в действии и попробовать новые здесь: http://codepad.org/2eZp98eD)
Пусть n + 1 будет количеством элементов, которые вы хотите, уже ограниченные длиной массива.
Затем вам нужны элементы с индексами 0 / n , 1 / n , ..., n / n пути до конца множество.
Пусть m + 1 будет длиной массива. Тогда ваши индексы будут круглыми (m * i / n) (с делением с плавающей запятой).
Похоже, что вы хотите включить в список как первый, так и последний элементы.
Если вы хотите вытащить X элементов из списка из N элементов, размер шага будет (N-1)/(X-1). Просто округляйте, как хотите, по мере извлечения каждого элемента.
Ihre Schrittgröße ist (ArraySize-1)/(N-1).
Fügen Sie einfach die Schrittgröße zu einem Gleitkommaakkumulator hinzu und runden Sie den Akkumulator ab, um den Array-Index zu erhalten. Wiederholen Sie diesen Vorgang, bis der Akkumulator die Arraygröße >.