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