Равномерно выбрать N элементов из массива

Question

Мне нужно равномерно выбрать n элементов из массива. Я думаю, что лучший способ объяснить это на примере.

скажи, что у меня есть:

массив [0,1,2,3,4] и мне нужно выбрать 3 числа .. 0,2,4.

Конечно, если длина массива <= <em>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

EDIT:

больше примеров:
массив [0,1,2], 2 элемента: 0,2
массив [0,1,2,3,4,5,6,7], 5 элементов: 0,2, либо 3, либо 4, 5,7

и да, я бы хотел всегда включать первый и последний элементы.

РЕДАКТИРОВАТЬ 2:

то, о чем я думал, было что-то вроде ... сначала + последний элемент, а затем продолжил свой путь, используя медианное значение. Хотя я застрял / смутился, пытаясь это сделать.

Я посмотрю на алгоритм, который вы публикуете. спасибо!

РЕДАКТИРОВАТЬ 3:

Вот улучшенная версия решения incrediman с PHP. Работает также с ассоциативными массивами, сохраняя ключи.

<?php

/**
 * Selects $x elements (evenly distributed across $set) from $set
 *
 * @param $set array : array set to select from
 * @param $x int     : number of elements to select. positive integer
 *
 * @return array|bool : selected set, bool false on failure
 */
///FIXME when $x = 1 .. return median .. right now throws a warning, division by zero

function select ($set, $x) {
    //check params
    if (!is_array($set) || !is_int($x) || $x < 1)
        return false;

    $n = count($set);

    if ($n <= $x)
        return $set;

    $selected = array ();
    $step     = ($n - 1) / ($x - 1);
    $keys     = array_keys  ($set);
    $values   = array_values($set);

    for ($i=0; $i<$x; $i++) {
        $selected[$keys[round($step*$i)]] = $values[round($step*$i)];
    }

    return $selected;
}

?>

Возможно, вы можете реализовать Итератор , но мне не нужно заходить так далеко.

Answer 1

Наслаждайтесь! (Псевдо-код): * * +1001

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 как число с плавающей запятой и round , кратные 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)

Answer 2

Пусть n+1 будет числом элементов, которое вы хотите, уже ограниченным длиной массива.

Тогда вам нужны элементы с индексами 0/n, 1/n, ..., n/n пути к концу массива.

Пусть m+1 будет длиной массива. Тогда ваши индексы будут round(m*i/n) (с делением с плавающей запятой).

Answer 3

Похоже, вы хотите включить в свой список как первый, так и последний элементы.

Если вы хотите извлечь X элементов из списка из N элементов, размер вашего шага будет (N-1) / (X-1) Просто закрутите, как хотите, вытаскивая каждого.

Answer 4

Ваш размер шага (ArraySize-1) / (N-1).
Просто добавьте размер шага к аккумулятору с плавающей запятой и округлите аккумулятор, чтобы получить индекс массива. Повторите, пока аккумулятор> размер массива.