Al volo, partizione casuale di un intervallo di numeri [0, N] in gruppi di dimensione M massima

2

Supponiamo che tu abbia un intervallo di numeri da 0 a N che vuoi separare casualmente in gruppi di numeri sequenziali M massimi. Questo è fatto facilmente con un bitmap e un generatore di numeri casuali, ma non è efficiente in termini di spazio per istanze molto grandi di N.

Quindi, quello che voglio è un generatore che, dato un numero N e M, inizierà a produrre gruppi non sovrapposti in un ordine casuale e con dimensioni casuali, con meno di O (N) di efficienza spaziale.

es. per N = 7 e M = 3, un output valido è il seguente:

4
1, 2
3
5, 6, 7
0

Qualcuno conosce un algoritmo che può aiutare a produrre un simile output?

    
posta nine 01.12.2014 - 10:18
fonte

2 risposte

1

Ho creato un programma di partizionamento con utilizzo dello spazio O (1) ma tempo di esecuzione O (N ^ 2). Puoi trovare il codice sorgente qui . Nei commenti c'è una buona spiegazione dell'algoritmo di shuffling usato.

La parte fondamentale di questo programma è il passo di mischia, che è il passo che richiede O (N ^ 2). Doc Brown ha chiesto "come puoi mescolare N elementi in meno di O (N) spazio"? Ho estratto la logica di shuffling e ho creato un programma separato che è elencato di seguito.

Per ottenere la spiegazione completa, fai riferimento al codice sorgente collegato sopra. Quanto segue è una breve spiegazione:

La funzione shuffling simula un rimescolamento di Fisher-Yates, in cui si scambia l'array [0] con l'array [r], dove r è un numero casuale nell'intervallo [0..N-1]. Quindi si scambia l'array [1] con l'array [r], dove r è un nuovo numero casuale nell'intervallo [1..N-1]. Continui a spostarti lungo l'array, scambiando elementi casuali, fino a raggiungere la fine dell'array.

Per utilizzare lo spazio O (1), non c'è alcuna matrice. Invece, per ogni nuovo elemento casuale che selezioniamo, dobbiamo riprodurre gli swap precedenti in ordine inverso per capire da dove proviene veramente l'elemento dell'array. In sostanza, selezioniamo un elemento a caso, quindi annulliamo gli swap che sono arrivati prima per determinare dove fosse la posizione originale dell'elemento. Possiamo riprodurre gli swap precedenti semplicemente riportando il generatore di numeri casuali su un seme precedentemente salvato.

Modifica: dopo aver pubblicato questa soluzione, ho trovato questa domanda di stackoverflow che elenca alcuni modi migliori per creare una permutazione di N numeri nello spazio costante. Quindi, se sostituisci una di quelle soluzioni per la mia funzione di shuffling, puoi fare meglio di O (N ^ 2) e utilizzare ancora lo spazio O (1).

/* Given a number N, shuffle the elements from 0..N-1 and print them. */
/* This algorithm uses O(1) space but uses O(N^2) time.               */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static void shuffle(int n);

int main(int argc, char *argv[])
{
    if (argc < 2) {
        printf("Usage: shuffle N\n");
        exit(0);
    }

    shuffle(atoi(argv[1]));
    return 0;
}

static void shuffle(int n)
{
    uint32_t seedOriginal = time(NULL);
    uint32_t seed         = 0;
    int      i            = 0;
    int      j            = 0;
    int      slot         = 0;

    for (i=0;i<n;i++) {
        seed = seedOriginal;
        srand(seed);

        // Skip n-i-1 random numbers.
        for (j=n-i-1;j>0;j--)
            rand();

        // Select an array slot from [i..n-1].
        slot = i + (rand() % (n - i));

        // Find out what that slot corresponds to in the original order.
        // We do this by backtracking through all the previous steps.
        for (j=i-1;j>=0;j--) {
            int r = j + (rand() % (n - j));

            // Every time we see the slot we are looking for, we switch
            // to looking for slot j instead, because at this previous step
            // we swapped array[j] with array[slot].
            if (r == slot)
                slot = j;
        }

        // Slot is now the correct element we are looking for.
        printf("%d\n", slot);
    }
}
    
risposta data 01.12.2014 - 21:39
fonte
1

Generalmente generare gruppi casuali non sovrapposti in un ordine casuale sarebbe un dolore al collo. Ad esempio, hai selezionato un "inizio" casuale; quindi cerca i gruppi esistenti per assicurarti che l'inizio sia utilizzabile e trovi la "fine più alta possibile" per quell'inizio; quindi seleziona una "fine" casuale tra "inizio" e "massima fine possibile". Finché stai selezionando un "inizio" casuale, non puoi evitare una sorta di ricerca.

Invece, dividerlo in 2 parti: generi gruppi casuali non sovrapposti in ordine ascendente; quindi mescolali in modo che finiscano in ordine casuale.

Generare gruppi casuali non sovrapposti in ordine crescente è semplice. Ogni gruppo inizia dove finisce il gruppo precedente e hai solo bisogno di una lunghezza casuale.

    
risposta data 01.12.2014 - 11:31
fonte

Leggi altre domande sui tag