Entra

View Full Version : soluzione algoritmica


omniaforever
20-02-2010, 13:08
allora ragazzi, mi servirebbe un aiuto algoritmico..
in c# ma alla fin anche in pseudo codice mi sta bene..

sostanzialmente io ho una stringa del genere(con più coppie di numeri, anche formati da più cifre):
1-2|2-3|3-4|5-6|6-7|8-9
dovrei suddividerla in sottostringhe in modo da avere in ognuna di esse tutte le coppie del tipo a-b mostrate in precedenza che contengono un elemento in comune,..nel caso
sottostringa a) 1-2-3-4 (ma mi starebbe bene anche in 1-2-2-3-3-4, che deriva dall'unione di 1-2 con 2-3 e 2-3 con 3-4 che contengono i primi il 2 in comune e i secondi il 3)

sottostringa b) 5-6-7 (o 5-6-6-7 che derivano dall'unione di 5-6 con 6-7)

sottostringa c) 8-9

premesso che so come splittare in sottostringhe in coppie a-b(splitting sul carattere |), ed inoltre estrarre da ognuna di queste coppie il singolo numero a o b (ulteriore spit sul carattere -), ma mi interessava proprio la soluzione algoritmica per ottenere ciò che voglio..
grazie

WarDuck
20-02-2010, 13:36
In pratica se ho capito bene vorresti estrarre da:

1-2 e 2-3

1-3? giusto?

Se è così non dovrebbe essere molto complicato, dovresti tener conto in pratica degli elementi:

(a, b) (c, d) tali che b=c e a quel punto derivare la nuova coppia (a, d).

omniaforever
20-02-2010, 13:57
In pratica se ho capito bene vorresti estrarre da:

1-2 e 2-3

1-3? giusto?

Se è così non dovrebbe essere molto complicato, dovresti tener conto in pratica degli elementi:

(a, b) (c, d) tali che b=c e a quel punto derivare la nuova coppia (a, d).

no, voglio creare diverse concatenazioni che mi uniscono tutte le coppie a-b che hanno almeno un elemento in comune: cioè se ho a1-b1 e a2-b2 deve accadere che a1==a2 oppure a1==b2 oppure b1==a2 oppure b1==b2 ed in questo caso concatenerò
nel caso 1-2|2-3|3-4|5-6|6-7|8-9, lo concatnazioni finali dovranno essere 1-2|2-3|3-4( semplificando togliendo i doppioni:1-2-3-4) poi 5-6|6-7(senza doppioni 5-6-7) e poi 8-9

gugoXX
20-02-2010, 14:44
Edita il titolo perche' non e' conforme.

Inizio con una proposta bruta e poco efficiente.
Complessita' O(N^2 Log N)


class Program
{
static void Main(string[] args)
{
string src = "1-2|5-6|3-2|6-7|9-8|3-4";

var coupleStrings = src.Split('|');

// Parso e ordino le coppie secondo l'elemento minore
var CoupleOrdered = coupleStrings.Select(cs => new Couple(cs))
.OrderBy(cp => cp.NumA)
.ToArray();

// Conterra' per ciascuna coppia ordinata quale e' il suo gruppo finale
Dictionary<int, int> Clusters = new Dictionary<int, int>();

// Costruisco i Cluster.
// Doppio ciclo O(N^2)
// Per ciascun elemento se ancora non fa parte di un cluster
// Ne creo uno e ve lo assegno.
// Ciclo sui successivi e ciascuno di quelli che sono insieme al pilota
// li assegno allo stesso cluster del pilota.
int maxGroup=0;
int ln = CoupleOrdered.Count();
for (int t = 0; t < ln; t++)
{
int CurrentGroup;
Couple reference = CoupleOrdered[t];
if (!Clusters.TryGetValue(t, out CurrentGroup))
{
Clusters[t] = maxGroup;
CurrentGroup = maxGroup;
maxGroup++;
}

for (int u = t+1; u < ln; u++)
{
Couple other = CoupleOrdered[u];
if (reference.IsTogetherWith(other))
{
Clusters[u] = CurrentGroup;
}
}
}

// Raggruppo i Cluster di Couple secondo l'ordinale di gruppo
// Per ogni elemento del gruppo considero la coppia originale
// Della coppia originale ottengo l'array dei suoi 2 valori
// Per ciasucn cluster quindi unisco insieme tutti
// gli array da 2 valori di tutte le coppie (SelectMany)
// Ottengo quindi un array di stringhe per ciascun gruppo
// Spool-out di un record per gruppo, con l'ordinale e la stringa
// composta dai valori distinti e ordinati comma-separated
var res = from cluster in Clusters
group cluster by cluster.Value into grp
let OriginalValues = grp.Select(gr => gr.Key)
.SelectMany(oi=>CoupleOrdered[oi].DNum)
.Distinct()
.OrderBy(oi=>oi)
.Select(oi=>oi.ToString())
.ToArray()
select new
{
GrpKey = grp.Key,
Data = string.Join(",", OriginalValues)
};

// Spool-out su Console.
var resFinalizer = res.ToList();
resFinalizer.ForEach(Console.WriteLine);
Console.ReadKey();
}

public class Couple
{
public Couple(string src)
{
var strspl = src.Split('-');
int numA = int.Parse(strspl[0]);
int numB = int.Parse(strspl[1]);
NumA = Math.Min(numA, numB);
NumB = Math.Max(numA, numB);
DNum = new int[2] { NumA, NumB };
}

public int NumA { get; private set; }
public int NumB { get; private set; }
public int[] DNum {get; private set;}

public bool IsTogetherWith(Couple other)
{
return (NumA == other.NumA || NumA == other.NumB || NumB == other.NumA || NumB == other.NumB);
}
}
}


Risultato

{ GrpKey = 0, Data = 1,2,3,4 }
{ GrpKey = 1, Data = 5,6,7 }
{ GrpKey = 2, Data = 8,9 }

gugoXX
20-02-2010, 15:36
Getto anche una soluzione migliore.
O(N)
passando attraverso matrici di adiacenze e un simil algoritmo flood-fill

Lo so, oggi mia moglie lavora e non mi passa un c...o
ma ora esco e vado con un amico ai festeggiamenti del capodanno Cinese

A sto giro non commento.
Ciau.


class Program
{
public class Couple
{
public Couple(string src)
{
var strspl = src.Split('-');
int numA = int.Parse(strspl[0]);
int numB = int.Parse(strspl[1]);
NumA = Math.Min(numA, numB);
NumB = Math.Max(numA, numB);
DNum = new int[2] { NumA, NumB };
}

public int NumA { get; private set; }
public int NumB { get; private set; }
public int[] DNum {get; private set;}

public bool IsTogetherWith(Couple other)
{
return (NumA == other.NumA || NumA == other.NumB || NumB == other.NumA || NumB == other.NumB);
}
}

static void Main(string[] args)
{
string src = "1-2|5-6|3-2|6-7|9-8|3-4";

var coupleStrings = src.Split('|');

// Parso le coppie
var Couples = coupleStrings.Select(cs => new Couple(cs))
.ToArray();

var Matrix = new Dictionary<int, List<int>>();

// Matrice Adiacenze
foreach(var couple in Couples)
{
var NumA = couple.NumA;
var NumB = couple.NumB;
AddMat(Matrix, NumA, NumB);
AddMat(Matrix, NumB, NumA);
}

// FloodFill
int CurGroup = 0;

var res = new Dictionary<int, HashSet<int>>();

while (Matrix.Count != 0)
{
var cline = Matrix.First();
Stack<int> CurrentFiller=new Stack<int>(cline.Value);
res[CurGroup] = new HashSet<int>{cline.Key};
Matrix.Remove(cline.Key);
while (CurrentFiller.Count>0)
{
var cd = CurrentFiller.Pop();
res[CurGroup].Add(cd);
List<int> brother;
if (Matrix.TryGetValue(cd, out brother))
{
CurrentFiller.PushMany(brother);
Matrix.Remove(cd);
}
}
CurGroup++;
}

var spooler = from r in res
let vals = r.Value
.OrderBy(val => val)
.Select(val => val.ToString())
.ToArray()
select new {
GrpKey = r.Key,
Data = string.Join(",", vals)
};

// Spool-out su Console.
var resFinalizer = spooler.ToList();
resFinalizer.ForEach(Console.WriteLine);
Console.ReadKey();
}

public static void AddMat(Dictionary<int, List<int>> Matrix, int NumA, int NumB)
{
List<int> line;
if (!Matrix.TryGetValue(NumA, out line))
{
line = Matrix[NumA] = new List<int>();
}
line.Add(NumB);
}
}

public static class Extensions
{
public static void PushMany<T>(this Stack<T> domain, IEnumerable<T> data)
{
foreach (T t in data)
domain.Push(t);
}
}


Risultato


{ GrpKey = 0, Data = 1,2,3,4 }
{ GrpKey = 1, Data = 5,6,7 }
{ GrpKey = 2, Data = 8,9 }

omniaforever
20-02-2010, 19:37
strepitoso!grazie :D

gugoXX
20-02-2010, 21:15
strepitoso!grazie :D

Non e' per un esercizio vero?
Perche' tanto, anche se lo fosse, ti sgamerebbero subito. :p

omniaforever
21-02-2010, 00:56
Non e' per un esercizio vero?
Perche' tanto, anche se lo fosse, ti sgamerebbero subito. :p

nono...mi serviva questa piccola parte per la mia tesi (ed onestamente già l'avevo trovata e volevo un confronto qui..diciamo che la mia soluzione ci sta il doppio della tua prima :sofico: )