numeri di coppia univoci casuali da due intervalli

5

Voglio scrivere una funzione che restituisca numeri di coppia univoci casuali ogni volta che lo chiamano da un intervallo fino a quando non lo si azzera. Qualcosa del genere:

function randomUniquePairs($ranges, $reset = false){
   if ($reset === false){
      // some code for reseting
   }
   /*
     some code for creating random unique pair numbers
   */
   return $result;  
} 

randomUniquePairs(range(1,10), range(1,20));
/*
  this function returns for example:
   array(2,9)
*/
randomUniquePairs(range(1,10), range(1,20));
/*
  this function returns for example:
   array(5,19)
*/

randomUniquePairs(range(1,10), range(1,20));
/*
  this function returns for example:
   array(5,9)
*/
 //this function returns random unique pairs until we pass reset paramer true

Ho provato due approcci:

Approccio 1
Il mio primo tentativo è stato quello di creare una matrice di tutte le coppie possibili e poi selezionarle casualmente, ma è molto inefficiente, perché se le gamme sono così ampie, consuma molta memoria. il codice:

  class a {
    private $asqar;

    function __construct() ($range) {

        // cycle for ranges
        foreach ($range[0] as  $v1) {
            foreach ($range[1] as $v2) {
                $asqar[] =  array(
                    $v1,
                    $v2,
                );
            }
        }
    }

    function randomUniquePairs($reset = false){

        if ($reset === true){
           $this->asgar = array();
        }

        $rndKey = array_rand($this->asgar);
        $result = $this->asqar[$rndkey];
        unset($this->asqar[$rndkey]);
        return $result;
    }
}

$c = new a(range(1,10), range(1,20));
$c->randomUniquePairs();

Approccio 2
Il mio secondo tentativo è stato quello di scrivere una funzione che producesse una coppia da questi intervalli, quindi memorizzarla in una variabile, ogni volta che la funzione richiama dopo aver prodotto una coppia, controlla se questa coppia produce prima di chiamare la funzione in modo ricorsivo, continua finché non produce un coppia unica. Ecco il codice:

class a{ 

    private $__uniqueVariables = array();

    public function randomUniquePairs($range, $reset = false) {

        if ($reset === true){
       $this->__uniqueVariables = array();
    }

    // cycle for each value
    foreach ($range as $value) {

        // shuffle
        shuffle($value);

        // selected id
        $selectedId[] = $value[0];
    }

    // check for selected variable
    if (in_array($rndUnqNum, $this->__uniqueVariables)) {

        // return for try again
        return $this->uniqueVariable($range);
    }

    // added to current unique variables
    $this->__uniqueVariables[] = $rndUnqNum;

    // return
    return $rndUnqNum;
}

}

ma questo secondo approccio presenta un problema che a volte genera Fatal error: Maximum function nesting level of '100' reached .

Sto cercando un approccio migliore al mio algoritmo.

    
posta Arash Mousavi 25.07.2013 - 17:23
fonte

3 risposte

4

Qualcosa che devi determinare è quanto "bello" vuoi che sia questo e la performance quando lo spazio non utilizzato si esaurisce.

In sostanza, vuoi una scatola a caso da una matrice N dimensionale. Non è la scatola stessa che è importante, ma la posizione della scatola è importante.

Sotto le coperte, un array 10x20 è spesso rappresentato come un array 1x200 con qualche matematica dietro per accedere al punto giusto. Se dovessi accedere a [5][13] , stai effettivamente accedendo alla posizione [5*20 + 13] . È possibile utilizzare lo stesso approccio per passare da un numero indietro alla posizione. La posizione 113 passa alla deviazione di interi per 20 e il resto restituisce 5 r13 .

Così ora, non è necessario memorizzare effettivamente 200 coppie (anche se non è molto), hai solo bisogno di un bitfield lungo 200 bit. Genera un numero casuale nell'intervallo corretto e contrassegnalo come usato nel campo bit.

Ora, la domanda su come la gestisci quando hai una collisione? Questo va alle varie tecniche di collisione hash utilizzate nelle tabelle hash . Alcuni non funzioneranno per questa applicazione, ma è comunque una buona lettura.

Un approccio semplice sarebbe una volta che hai una collisione, inizia semplicemente ad aumentare dove stai guardando finché non ne trovi una che non è stata usata. L'incremento potrebbe essere 1 o qualsiasi numero relatività primo alle dimensioni dello spazio.

Ok, sono in un posto in cui posso sedermi e scrivere qualcosa. È perl Non dovrebbe essere troppo lontano da php ed è piuttosto semplice.

#!/usr/bin/perl

my $x = shift @ARGV;
my $y = shift @ARGV;
my $f = shift @ARGV; # fill factor
my $t = $x * $y;    # total space
my $v = '';

foreach (1 .. int($t * $f)) {
    my $r = int(rand($t));  # random number from 0 .. $t-1
    my $yp = int($r / $x); # y' (y prime)
    my $xp = int($r % $x); # x' (x prime)

    print "Trying $r: $xp $yp...\n";
    while(vec($vec, $r, 1)) {
        $yp = int($r / $x);
        $xp = int($r % $x);
        print "\tcollision at $r: $xp $yp\n";
        $r += 1;
        $r %= $t;   # scale $r to within $t
    }
    $yp = int($r / $x);
    $xp = int($r % $x);
    vec($vec, $r, 1) = 1; # set the $r th bit
    print "\tsettled at $r: $xp $yp\n";
}

In definitiva, i valori "risolti" sono quelli che desideri.

Leggi due numeri dalla riga di comando e li assegni a x e y . Lo spazio di ricerca totale è t - questo è quanto sono grandi tutti i numeri possibili. Inoltre, leggi un fattore di riempimento come $f , questo dovrebbe essere un valore inferiore a 1 e viene utilizzato per limitare l'iterazione dell'elenco. L'impostazione di un valore maggiore di 1 presenterà un ciclo infinito.

Sto riempiendo lo spazio al valore specificato (il foreach (1 .. ($t * $f)) ). No, non c'è alcun controllo degli errori su $f per assicurarsi che sia inferiore o uguale a 1, ma dovrebbe esserci.

Quindi scegli un numero casuale da 0 a $t - 1. Lo spot che rappresenta è $yp e $xp - y primo e x primo.

Qui ci sono alcune cose perlastiche, vec funziona con un vettore bit di dimensioni arbitrarie. Ci sono diversi modi per farlo in una determinata lingua, è piuttosto facile con Perl. Con Java, si potrebbe usare un BitSet (questo è abbastanza grande da contenere i bit maxint, che potrebbero rappresentare una coppia di numeri 46340).

Quindi prova il bit nella posizione $r th per vedere se è stato usato. Se lo è, incrementa $r e arrotolalo se diventa più grande dello spazio totale (quindi se hai un 10 e 20 (0 .. 199) e ottieni 200, diventa 0).

Una volta trovato un bit non utilizzato, impostalo e visualizza i tuoi valori.

Ecco come appare l'output:

Trying 96: 6 9...
        settled at 96: 6 9
Trying 117: 7 11...
        collision at 117: 7 11
        settled at 118: 8 11
Trying 115: 5 11...
        settled at 115: 5 11
Trying 153: 3 15...
        settled at 153: 3 15
Trying 90: 0 9...
        settled at 90: 0 9
Trying 140: 0 14...
        collision at 140: 0 14
        collision at 141: 1 14
        collision at 142: 2 14
        settled at 143: 3 14
Trying 73: 3 7...
        settled at 73: 3 7

Questo è testato su un sistema unix così:

% rndpair.pl 10 20 0.5 | grep settled | sort | uniq | wc -l
     100

Questo mostra che con 100 numeri ci sono 100 coppie uniche stampate (basta guardare le linee "sistemate").

C'è un bel po 'di informazioni di debug in là (non è davvero necessario continuare a reimpostare il valore di $yp e $xp fino alla fine.

E poi c'è la domanda su quanto è veloce? Questo per generare il 50% delle coppie disponibili per lo spazio disponibile. Renditi conto che c'è un po 'di tempo nell'ordinamento e uniq (di possibilmente qualche piccola porzione di testo):

% time ./rndpair.pl 500 500 0.5 | grep settled | sort| uniq | wc -l
  125000

real    0m3.528s
user    0m3.901s
sys     0m0.045s

Consente di sollevarlo di una tacca e rimuovere le altre applicazioni dalla catena.

% time ./rndpair.pl 5000 5000 0.5 > /dev/null

real    0m34.668s
user    0m34.482s
sys     0m0.180s

Quanto spazio ha occupato lo spazio di archiviazione 5k x 5k? 25.000.000 bit o circa 3 megabyte.

Si noti che le prestazioni di questo calo diminuiscono con il fattore di riempimento. Per uno spazio di ricerca di 6, 80610 (un commento precedente, se l'ho letto bene), si esegue abbastanza rapidamente (notare i tempi crescenti all'aumentare del fattore di riempimento):

% time ./rndpair.pl 6 80610 0.5 | grep settled | wc -l
  241830

real    0m0.827s
user    0m1.562s
sys     0m0.029s
% time ./rndpair.pl 6 80610 0.75 | grep settled | wc -l
  362745

real    0m1.721s
user    0m3.151s
sys     0m0.043s
% time ./rndpair.pl 6 80610 0.9 | grep settled | wc -l
  435294

real    0m3.993s
user    0m7.031s
sys     0m0.079s
    
risposta data 25.07.2013 - 17:48
fonte
3

Quanto segue è una riscrittura da utilizzare per invece di foreach.

<?php

function unique_arrays($first, $second) {
    $arrays = array();
    for ($i = $first[0]; $i <= $second[0]; $i++)
        for ($j = $first[1]; $j <= $second[1]; $j++)
            $arrays[] = array($i, $j);

    return $arrays;
}

print_r(unique_arrays(array(1,6), array(3,8)));

?>

Ecco una lezione ispirata agli iteratori che dovrebbe tenere a bada la memoria.

<?php

class XYStepper {
    protected $first;
    protected $second;
    protected $current = null;

    public function __construct($first, $second) {
        $this->first = $first;
        $this->second = $second;
    }

    public function next() {
        if ($this->current == null)
            $this->current = $this->first;

        else {
            if ($this->current[0] < $this->second[0]) {
                if ($this->current[1] < $this->second[1])
                    $this->current[1]++;
                else {
                    $this->current[0]++;
                    $this->current[1] = $this->first[1];
                }
            }

            else {
                if ($this->current[1] < $this->second[1])
                    $this->current[1]++;
                else
                    return null;
            }
        }

        return $this->current;
    }
}

$xy = new XYStepper(array(1,6), array(3,8));
while (($next = $xy->next()) != null)
    print_r($next);

?>

Aggiungere la capacità di scendere o avere incrementi negativi è lasciato come esercizio al lettore.

    
risposta data 25.07.2013 - 17:58
fonte
2

Questo è basato sui commenti e sul codice di @MichaelT. Ho iniziato con questo prima che lo pubblicasse, ma sono stato sbirciando dopo aver pubblicato il suo codice in modo che non fosse del tutto originale.

Mi siedo dove i numeri in entrambe le gamme sono uguali e aggiungo l'offset in modo che sia più allineato con la specifica originale.

<?php
class Gen
{
    private $mask;            // bitmask all combinations
    private $firstOffset;     // what first range starts from
    private $secondOffset;    // what second range starts from
    private $firstWidth;      // the width of first range
    private $secondWidth;     // the width of second range
    private $permutations;    // number of permutations
    private $used = 0;        // number of permutations used

    public function __construct(array $range1, array $range2)
    {
        if( ! count($range1) || ! count($range2) )
            throw new Exception("Both ranges must contain at least one element");

        // I support both array(1, 2, 3, 4) and array(1, 4) as a range
        $this->firstOffset = $range1[0];
        $this->secondOffset = $range2[0];
        $firstEnd = array_pop($range1);
        $secondEnd = array_pop($range2);

        if( $firstEnd < $this->firstOffset ||
            $secondEnd < $this->secondOffset )
            throw new Exception('End lower than start in at least one range.' . 
                        "Given [{$this->firstOffset}, $firstEnd] " . 
                        "and [{this->secondOffset}, $secondEnd]");

        $this->firstWidth = 1 + $firstEnd - $this->firstOffset;
        $this->secondWidth = 1 + $secondEnd - $this->secondOffset;
        $this->permutations = $this->firstWidth*$this->secondWidth; // with no overlap
        $this->reset();
    }

    public function next()
    {
        if( $this->used != $this->permutations ) {
            $random_permutation = rand(0,$this->permutations);
            if( ($found = gmp_scan0($this->mask, $random_permutation)) == $this->permutations )
                $found = gmp_scan0($this->mask, 0);
            $this->used++;
            gmp_setbit($this->mask, $found);
            $first = $found % $this->firstWidth + $this->firstOffset;
            $second = floor($found / $this->firstWidth) + $this->secondOffset;
            return array( $first, $second);
        }
        throw new Exception("No more pairs available");
    }

    public function reset()
    {
        $this->mask = gmp_init(0);
        $this->used = 0;

        // Make simple variables of
        // so that the original ranges
        // are [$s1, $e1] and [$s2, $e2]
        $s1 = $this->firstOffset;    
        $s2 = $this->secondOffset;
        $e1 = $s1 + $this->firstWidth - 1;
        $e2 = $s2 + $this->secondWidth - 1;

        if( $s1 <= $e2 && $s2 <= $e1 ) {        // if the rhe ranges overlap
            $is = max($s1, $s2);                // get the start of intersect
            $ie = min($e1, $e2);                // get the end of intersect
            $this->used +=    1 + $ie - $is;    // the count of emelemts in common
            $i1end = $ie - $s1 + 1;             // calculate the end element for first range
            for( $i1 = $is - $s1,               // initialize range1 by reducing by s1
                 $i2 = $is - $s2;               // initialize range2 by reducing by s2
                 $i1 < $i1end;                  // as long as $i1 is lower than the calculates stop
                 $i1++, $i2++) {                // increment both indexes by one for next iteration

                // body of for loop sets bitmask where both
                // would get the same value when offset is added
                gmp_setbit( $this->mask, $i1 + $i2 * $this->firstWidth ); 
            }
        }
    }
}


//$g = new Gen(range(1,6), range(1,10));
//$g = new Gen(array(3,4), array(5));
$g = new Gen(array(1,6), array(3291,83901)); 
try {
    while(1) {
        print implode(", ", $g->next()) . "\n";
    }
} catch ( Exception $e ) {
    print "Done!\n";
}
    
risposta data 26.07.2013 - 15:14
fonte

Leggi altre domande sui tag