[C# / Tutti] - Algoritmo per soluzione problema

[Kralizek]

Salve a tutti,
volevo chiedervi una mano per una cosa che devo fare a lavoro.

Non mi interessa la soluzione codificata, quanto più l'algoritmo più veloce da seguire. (certo se qualcuno ha voglia di scrivere un po' di codice non lo fermo mica :P)

In pratica il problema è questo:
Ho un insieme di liste di stringhe di lunghezza variabile.
Ogni stringa rappresenta una condizione booleana.
Ciascuna lista di stringhe rappresenta la combinazione in OR delle suddette condizioni booleane.
L'insieme delle liste rappresenta la condizione in AND delle liste.

Di fatto, date le tre liste
L1 = {"A=123", "A=234", "A=345", "A=567"}
L2 = {"B=asd", "B=mno"}
L3 = {"C=qwe", "C=rty", "C=xyz"}

Queste combinate rappresenterebbero la seguente espressione booleana

("A=123" OR "A=234" OR "A=345" OR "A=567") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")

Fin qui tutto semplice. Il primo problema è che la stringa risultante ha una lunghezza massima che non può essere superata. Quindi la soluzione è decomporre questa espressione in espressioni equivalenti che combinate danno l'espressione originale.

La soluzione più semplice è calcolare il prodotto cartesiano delle liste, così da avere L1xL2xL3 espressioni banali {l1, l2, l3}.

Il problema è che ciascuna espressione ha un cooldown di 1 secondo, quindi è necessario minimizzare il numero di espressioni equivalenti.

Spero di aver esposto il problema chiaramente.

Come detto, mi accontento anche di idee generali.

[Kralizek]

Up?

[cdimauro]

Infatti col prodotto cartesiano hai decomposto l'espressione generale generando tutti i casi possibili, ma hai prodotto una miriade di espressioni.

Una soluzione generale potrebbe essere quella di decomporre l'espressione completa (al momento mi riferisco a questa senza tenere conto dell'attuale rappresentazione che hai fornito, per esemplificare il discorso) finché non arrivi al punto in cui hai ottenuto che le nuove espressioni non superino la lunghezza massima prevista.

Ad esempio, da quella generale dividendo a metà la prima sottoespressione ottieni le seguenti produzioni:

("A=123" OR "A=234") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")
OR
("A=345" OR "A=567") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")

Ho aggiunto l'OR perché è chiaro che per ottenere l'equivalenza con l'espressione originale, serve combinarle in questo modo. Ma puoi ignorare l'OR, e pensare di avere generate una lista di due elementi. Questo poi lo vedi tu come organizzarlo.

A questo punto si presentano due casi: se le nuove produzioni soddisfano il requisito della lunghezza, hai finito. Altrimenti applica lo stesso procedimento a loro.

Quindi supponendo che le due produzioni non soddisfino la condizione, applicando nuovamente il procedimento otterremo:

("A=123") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")
OR
("A=234") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")
OR
("A=345") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")
OR
("A=567") AND ("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz")

A questo punto la produzione più a sinistra (che è il nostro riferimento: partiamo sempre da sinistra in queste operazioni; quindi col primo elemento dell'espressione più complessa) contiene una sola condizione, per cui possiamo riscrivere l'espressione nel seguente modo:

("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz") AND ("A=123")
OR
("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz") AND ("A=234")
OR
("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz") AND ("A=345")
OR
("B=asd" OR "B=mno") AND ("C=qwe" OR "C=rty" OR "C=xyz") AND ("A=567")

Questo perché la condizione a sinistra è troppo piccola e non ci è più utile nel processo di suddivisione, per cui la mettiamo alla fine.
Spostiamo, insomma, alla fine il primo elemento della lista a cui appartiene.

E' ovvio che la produzione più piccola in assoluto, quella composta dall'and di tutte le condizioni atomiche (su una sola variabile), debba necessariamente soddisfare la condizione sulla lunghezza. Peraltro, essendo tutte AND, si potrebbero anche accorpare e ridurre la lunghezza della stringa finale.

Una variante che mi viene in mente è quella di utilizzare un test, a cui segue eventualmente l'uso della bisezione anziché andare a tagliare acriticamente in due la prima condizione. Mi spiego meglio.

Dalla prima condizione, taglia l'elemento (controllo base / atomico) più a destra, e controlla se la produzione ottenuta soddisfa i requisiti di lunghezza. Se sì, in pratica hai finito, perché ti basta ricercare in mezzo alla prima condizione il punto in cui tagliare.
Per fare un esempio, metti che hai 5 controlli nella prima condizione. Vedi che staccando quello più a destra, la produzione che ottieni (con l'OR fra questo controllo atomico con le rimanenti condizioni; vedi sopra) soddisfa la lunghezza massima. A questo punto con la ricerca dicotomica ricavi che se stacchi i 3 controlli più a destra della prima condizione, la lunghezza massima è soddisfatta. Hai trovato il punto di rottura "safe" della prima condizione. Ti basta, adesso, prendere i DUE controlli più a destra della prima condizione e tenerli fissi, e poi tramite il prodotto cartesiano generare tutte le combinazioni dei primi 3 controlli in modo da realizzare tutte le nuove produzioni che avranno 3 controlli nella prima condizione.
E' chiaro che se già il test preliminare col primo elemento a destra della condizione fallisce, sei costretto a generare tutte le combinazioni delle produzioni atomiche, perché anche con un solo elemento la lunghezza massima non viene soddisfatta.

Questo procedimento è semplice se tutti gli elementi atomici (controlli di uguaglianza) hanno come valori stringhe della stessa lunghezza. Se ciò non dovesse essere vero, una possibile ottimizzazione potrebbe essere la seguente: ordina tutte le condizioni internamente in base alla lunghezza degli elementi atomici, dal più grande al più piccolo (prima i controlli con stringhe più grandi, poi quelle con stringhe più piccole). Successivamente, ordina tutte le condizioni in base alla loro lunghezza totale, sempre dalla più grande alla più piccola.
L'idea è quella di cercare di accorpare quanto più possibile le condizioni più piccole, spostandole tutte a destra, e facendo procedere il processo di suddivisione partendo da quelle più grandi, in modo da ridurre il più possibile il numero di suddivisioni. Infatti se parti suddividendo le condizioni più piccole genererai sempre molte più suddivisioni rispetto a partire da quelle più grandi.

OK, per adesso è tutto. Devo sistemare un po' di cose e uscire.

Vedi un po' se l'idea funziona e ti piace. Al limite ne riparliamo più tardi.

[Kralizek]

Oh, non avevo proprio pensato alla divisione ricorsiva...

Quello che avevo pensato era il tuo secondo approccio, ed infatti mi ero ordiato le stringhe e le liste in ordine decrescente, semplicemente mi sono "ubriacato" nel taglia e cuci.

Ad occhio credo che il secondo approccio si avvicini di più alla soluzione ottima, ma il primo é sensibilmente più veloce da implementare.

Lunedì che torno in ufficio provo e ti dico

Per fortuna ho diviso abbastanza bene il codice e non mi costa niente realizzare una nuova strategy ed iniettarla al posto di quella esistente.

Grazie mille

[cdimauro]

Con lo stomaco pieno si ragiona anche meglio , per cui ho pensato a un'altra soluzione, che poi sostanzialmente è un'implementazione ottimizzata di ciò che ho esposto prima.

Al solito, ordina le condizioni prima al loro interno in senso decrescente. Ogni condizione convertila in stringa, e ordina la lista di queste stringhe sempre in senso decrescente (di lunghezza). Quindi otterresti qualcosa del tipo:

OrderedConditionList = ['("A=123" OR "A=234" OR "A=345" OR "A=567"',
  '("C=qwe" OR "C=rty" OR "C=xyz")',
  '("B=asd" OR "B=mno")']

pythonicamente parlando.

Ma ti serve ottenere anche l'equivalente lista ordinata delle condizioni non convertite in stringa. Quindi qualcosa tipo:

OrderedList = [["A=123", "A=234", "A=345", "A=567"'],
  ["C=qwe", "C=rty", "C=xyz"],
  ["B=asd", "B=mno"]]

Vedi tu come fare. In Python metterei assieme sia la condizione convertita in stringa che la condizione ordinata, in una tupla, e il metodo sort provvederebbe a ordinare tutto senza problemi.

Nel tuo esempio le stringhe hanno tutte uguale lunghezza, per cui è chiaro che il risultato potrebbe essere diverso. Ad esempio, una condizione di un elemento potrebbe finire come primo elemento della lista ordinata perché la stringa che contiene è molto lunga, mentre altre condizioni con più elementi sono complessivamente più piccole.

A questo punto l'obiettivo è esclusivamente quello di trovare il "punto di rottura": quello che funge da spartiacque fra tutti gli elementi che a destra sono fissi (perché già ottimali) e tutti gli altri che a sinistra vanno "esplosi" col prodotto cartesiano.

Per realizzare ciò, serve una doppia bisezione. La prima che individua la parte sicuramente fissa a destra, che rimarrà costante per tutta l'operazione di esplosione. La seconda che serve a individuare, insieme alla condizione "di rottura" (quella da cui partirà il prodotto cartesiano), l'esatto spartiacque fra parte fissa e variabile; in buona sostanza, l'elemento a sinistra del quale tutti gli altri vanno combinati col prodotto cartesiano.

Prendendo la lista ordinata di stringhe di cui sopra, partendo dall'elemento di mezzo, calcoliamo la stringa con l'AND di tutte le stringhe che vanno dall'elemento di mezzo fino alla fine (a destra), e otteniamo la stringa:

TempConditions = '("C=qwe" OR "C=rty" OR "C=xyz") AND ("B=asd" OR "B=mno")'

A questo punto prendiamo dalla lista ordinata delle condizioni il primo elemento (il più cicciotto) di tutte le condizioni fermandoci prima della condizione di mezzo sulla quale stiamo lavorando.
Convertiamoli tutti come sequenza di AND. In questo caso c'è una sola condizione, per cui rimarrà soltanto

TempElements = '"A=123"'

ma se ci fossero state due condizioni, avremmo potuto ottenere qualcosa come "A=123" AND "B=xyz".
Adesso uniamo, sempre con un AND, quest'ultima stringa con quella precedente, ottenendo:

FinalCondition = '"A=123" AND ("C=qwe" OR "C=rty" OR "C=xyz") AND ("B=asd" OR "B=mno")'

A questo punto si fa un controllo con la lunghezza massima, e ci possono essere due casi ovviamente.
Se la lunghezza massima non è superata, ci si sposta nella condizione di mezzo delle condizioni che stanno a sinistra della condizione in cui ci troviamo, altrimenti ci spostiamo in quella di mezzo, ma di quelle a destra.
Supponiamo che la lunghezza massima sia superata. Quindi dobbiamo spostarci nell'elemento di mezzo delle condizioni a destra di quella attuale.
Applicando lo stesso procedimento di prima, a questo punto abbiamo:

TempConditions = '("B=asd" OR "B=mno")'

Mentre dall'unione del primo elemento di tutte le condizioni a sinistra abbiamo:

TempElements = '"A=123" AND "C=qwe"'

Fondiamole con l'AND e otteniamo:

FinalCondition = '"A=123" AND "C=qwe" AND ("B=asd" OR "B=mno")'

Se la lunghezza massima è superata, dovremmo spostarci a destra, ma a destra non c'è nessun'altra condizione, quindi vuol dire che il punto (elemento) di rottura va cercato nella condizione attuale.
Supponiamo che la lunghezza massima non sia stata superata. In questo caso la prima parte fissa diventa la condizione attuale:

RightCondition = TempConditions = '("B=asd" OR "B=mno")'

mentre il punto di rottura va cercato nella condizione a sinistra (precedente). Questo perché l'algoritmo di bisezione è terminato: la condizione a sinistra era quella di mezzo inizialmente, che è stata già valutata, altrimenti avremmo dovuto continuare a bisezionare le condizioni.
La seconda parte fissa va presa, invece, dall'unione dei primi elementi di tutte le condizioni che stanno a sinistra della condizione immediatamente a sinistra (cioè quella di mezzo). In questo caso:

LeftCondition = '"A=123"'

Adesso che abbiamo fissato parte destra e parte sinistra, prendiamo la condizione di mezzo, quella in cui andrà cercato l'elemento separatore.
Applicando lo stesso algoritmo di bisezione, l'obiettivo è di trovare la parte fissa centrale, costituita dall'OR di tutti gli elementi a destra dell'elemento separatore. Da notare che l'elemento separatore NON può essere assolutamente il primo della condizione attuale, perché altrimenti l'intera condizione sarebbe divenuta parte della parte fissa a destra.
Per farla breve e senza ripetere nuovamente i passi dell'algoritmo di bisezione, supponiamo che l'elemento separatore sia proprio quello centrale, cioè "C=rty", perché dalla combinazione della parte fissa a sinistra, di quella fissa a destra, e della parte centrale costituita con l'OR di tutti gli elementi a destra dell'elemento separatore incluso lui, abbiamo che la stringa risultante:

Temp = '("A=123") AND ("C=rty" OR "C=xyz") AND ("B=asd" OR "B=mno")'

che ha lunghezza non superiore a quella massima.

Questo vuol dire che tutti gli elementi alla sua destra diventeranno la parte fissa centrale, e saranno combinati con l'OR di tutti gli elementi della condizione attuale. In buona sostanza la parte fissa centrale è costituita dal solo elemento "C=xyz", che va combinato con l'OR di tutti gli altri elementi della condizione. In questo caso, quindi, otterremmo 2 condizioni centrali che espresse sotto forma di liste stringhe saranno:

CentralCondition = ['("C=qwe" OR "C=xyz")',
'("C=rty" OR "C=xyz")']

Che combinati con AND con la parte fissa a destra daranno l'elenco di condizioni fisse:

FixedConditions = ['("C=qwe" OR "C=xyz") AND ("B=asd" OR "B=mno")',
'("C=rty" OR "C=xyz") AND ("B=asd" OR "B=mno")']

Questa lista sostanzialmente copre tutte le condizioni a destra di quella di rottura, inclusa quella di rottura.
E queste stringhe vanno combinate, sempre con l'OR questa volta, col prodotto cartesiano di tutti gli elementi di tutte le condizioni a sinistra della condizione di rottura. In buona sostanza si otterranno 8 stringhe finali (2 condizioni fisse moltiplicato i 4 elementi della prima condizione), di cui riporto soltanto il primo per comodità:

FinalList = ['"A=123" OR (("C=qwe" OR "C=xyz") AND ("B=asd" OR "B=mno"))',
[...]
]

A naso dovrebbe funzionare. Mi dirai tu lunedì se va bene oppure no, ma credo che quest'implementazione sia di gran lunga più efficiente (e forse anche più semplice).

[Kralizek]

per ora ho optato per lo split binario. Appena ho tempo provo ad implementare l'altra strategia