Chunking di un array in gruppi di lettere generalmente di uguale lunghezza

1

Dato un elenco di elementi, voglio suddividerlo in quattro gruppi con la stessa lunghezza possibile. Gli articoli devono essere raggruppati in base alla prima lettera in ogni voce.

26 lettere / 4 gruppi in genere coprono 6,5 lettere in ciascun gruppo. Se avessimo una quantità uguale di elementi che iniziano con la stessa lettera in ciascun gruppo, potrebbe avere un aspetto simile a questo:

[A-F] (6 letters)
[G-M] (7 letters)
[N-S] (6 letters)
[T-Z] (7 letters)

Tuttavia, in pratica, potremmo scoprire che il nostro elenco originale è pesante sugli articoli nel gruppo [N-S].

[A-F] (50 items)
[G-M] (40 items)
[N-S] (70 items)
[T-Z] (40 items)

Potremmo voler spingere tutti gli elementi che iniziano con N nel gruppo 2 e tutti gli elementi che iniziano con S nel gruppo 4 per raggiungere il bilanciamento:

[A-F] (50 items)
[G-N] (50 items)
[O-R] (50 items)
[S-Z] (50 items)

Qualcuno ha qualche idea su dove indirizzarmi in termini di un algoritmo in grado di risolvere questo tipo di problema.

Molto probabilmente userò javascript sul client per implementare qualsiasi soluzione possa funzionare. Mi piacerebbe utilizzare il più possibile come funzionale.

    
posta mkaatman 26.08.2016 - 17:30
fonte

4 risposte

2

Crea 4 elenchi per i risultati e 26 elenchi per conservare gli articoli provvisori per lettera iniziale, quindi applica questo pseudo-codice:

foreach item in masterlist
    append item to initial letter list
    increment total counter

average bucket size = total/4

iterate letter buckets in order
    if current results bucket size  + length letter bucket < avergae bucket size
        append letter bucket to results bucket
    else
        append letter bucket to results bucket if it will be over average by less than it would be under if you do nothing
        move to next results bucket
    
risposta data 26.08.2016 - 18:09
fonte
4

Non vengono forniti altri requisiti e
partendo dal presupposto che vuoi incollare solo le prime lettere e
supponendo che ti atterrai a un numero di gruppi che è una potenza di 2:

  • Ordina l'elenco alfabeticamente
  • Tagliala più vicino alla metà possibile
  • Taglia questi due pezzi il più vicino alla metà possibile

Questo risolve il problema "read ahead" che stai sollevando. Ogni taglio considera l'intero elenco.

Un bel po 'di riutilizzo anche qui.

Un modo funzionale per affrontare questo problema è una chiusura. Produce una funzione che si chiude sulla lista ordinata e prende un altro elenco che definisce i gruppi come un parametro. Questo elenco di lettere sarebbe costituito da lettere iniziali e finali dei gruppi. La funzione produce una nuova lista di lettere che raddoppia il numero di gruppi.

Le tue liste di lettere procedono così:

[A-Z]

[A-N] [O-Z]

[A-F] [G-N] [O-R] [S-Z]

In pseudo codice

h = ItemRepository(sortedListOfItems).Halve;
result = h(h([A-Z]));
    
risposta data 26.08.2016 - 18:10
fonte
1

Forse mi manca qualcosa ma penso che questo approccio generale potrebbe essere quello che stai cercando:

  1. prendi tutti gli oggetti N e ordinali
  2. a partire dall'articolo N / 4 x
  3. x inizia con la stessa lettera dell'elemento precedente?
    1. sì: passa all'elemento successivo x, ripeti 3.
    2. no: x è l'inizio del gruppo successivo

Ripeti questo per ogni gruppo. Il problema principale qui è che se dici metà delle parole iniziano con A, non ti darà i risultati che desideri. Devi iniziare a guardare la seconda lettera e così via.

    
risposta data 26.08.2016 - 18:06
fonte
1

La forza bruta è l'approccio migliore per questo problema, a condizione che la dimensione dei dati sia relativamente piccola. Significa che (a) otterrà una risposta perfetta ogni volta, non e approssimazione e (b) avrà un codice più comprensibile e gestibile. L'unico costo è un po 'più tempo di elaborazione, ma è economico.

Hai bisogno di:

1) Un iteratore in grado di generare ogni raggruppamento e restituire il prossimo tipo di raggruppamento

2) Una funzione che calcola il grado di equilibrio tra i gruppi. Questo potrebbe probabilmente essere un semplice calcolo di deviazione standard sulle dimensioni dell'array.

In pseudocodice, sarà qualcosa del tipo:

For each possible way of grouping {
  Create a new structure for that grouping
  Spread the items among the groups
  Get the count of items in each group
  Calculate the standard deviation of the counts
  If this is the lowest standard deviation so far {
      save it together with the grouping that created it
      }
}
Result is the last grouping saved
    
risposta data 26.08.2016 - 20:16
fonte

Leggi altre domande sui tag