Questo è l'algoritmo (pseudocodice) che ho adesso per trovare tutti i sottoinsiemi di un determinato insieme con lunghezza k:
void allSubsets(set[]) {
for (i = 0; i<k; i++) {
for (j = i + 1; j<k; j++) {
print(set[i...j]);
}
}
}
Ma il tempo di esecuzione è O (n ^ 2). Qualcuno può migliorare questo?
Da quello che ho capito, questo non funziona. Non si troverà "AC" nel set "ABCD" (cioè fori). Per trovare tutti i sottoinsiemi, pensa che ogni elemento sia all'interno o meno del sottoinsieme. Che è fondamentalmente un binario si, no. Pertanto è possibile scorrere tutti i numeri con k bit 0/1 per trovare tutte le combinazioni.
Leggi altre domande sui tag algorithms