Sélectionnez uniformément N elems du tableau

Question

Je dois uniformément sélectionner n éléments d'un tableau. Je suppose que la meilleure façon d'expliquer est par l'exemple.

dire que j'ai:

tableau

[0,1,2,3,4] et je dois sélectionner 3 numéros .. 0,2,4.

Bien sûr, si la longueur du tableau < = n, j'ai juste besoin de retourner le tableau entier.

Je suis sûr qu'il ya un algorithme défini pour cela, essayé de chercher, et j'ai regardé Introduction aux algorithmes mais n'a pas pu trouver quelque chose qui a répondu à mes besoins (probablement négligé il)

Le problème que je rencontre est que je n'arrive pas à trouver un moyen de mettre à l'échelle ceci à n'importe quel tableau [p..q], en sélectionnant N éléments uniformément.

Note: Je ne peux pas sélectionner les éléments même de l'exemple ci-dessus ..

Quelques autres exemples;

matrice [0,1,2,3,4,5,6], 3 éléments; J'ai besoin d'obtenir 0,3,6
tableau [0,1,2,3,4,5], 3 éléments; Je dois obtenir 0, 2 ou 3, et 5

EDIT:

autres exemples:
tableau [0,1,2], 2 elems: 0,2
tableau [0,1 , 2,3,4,5,6,7], 5 elems: 0,2, soit 3 ou 4, 5,7

et oui, je voudrais toujours inclure les premier et dernier éléments.

EDIT 2:

ce que je pensais était quelque chose comme .. premier + dernier élément, puis me frayer un chemin à l'aide de la valeur médiane. Bien que je sois coincé/confus en essayant de le faire.

Je vais jeter un oeil à l'algo que vous publiez. Merci!

EDIT 3:

Voici une version gonflée de solution incrediman avec PHP. Fonctionne également avec les tableaux associatifs, tout en conservant les clés.

<?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; 
} 

?> 

Vous pouvez probablement mettre en œuvre un Iterator mais je ne pas besoin de prendre jusque-là.

Answer 1

Profitez-en! (Pseudo-code):

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 

Probablement la meilleure erreur de faire ici serait de jeter step comme un entier ou rond au début. Toutefois, afin de vous assurer que les éléments corrects sont extraits, vous devez déclarer step sous la forme d'un nombre à virgule flottante et arrondir multiples de pendant que vous parcourez le tableau.

exemple en php testé ici:

<? 

    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 

(vous pouvez voir vos cas de test en action et essayer de nouvelles ici: http://codepad.org/2eZp98eD)

Answer 2

La taille de votre step est (ArraySize-1)/(N-1).
Ajoutez simplement la taille du pas à un accumulateur à virgule flottante et arrondissez l'accumulateur pour obtenir l'indice du tableau. Répétez jusqu'à accumulateur> taille du tableau.

Answer 3

Soit n+1 le nombre d'éléments que vous souhaitez, déjà limité à la longueur du tableau.

Ensuite, vous voulez des éléments aux indices 0/n, 1/n, ..., n/n à la fin du tableau.

Soit m+1 être la longueur du tableau. Alors vos indices sont round(m*i/n) (avec la division faite avec le point flottant).

Answer 4

Il semble que vous souhaitiez inclure à la fois le premier et le dernier élément de votre liste.

Si vous voulez tirer X éléments de votre liste d'éléments N, la taille de votre étape sera (N-1)/(X-1). Juste autour de vous comme vous voulez sortir chacun.