soluzione algoritmica

[omniaforever]

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]

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]

Originariamente inviato da WarDuck

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]

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]

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]

strepitoso!grazie

[gugoXX]

Originariamente inviato da omniaforever

strepitoso!grazie

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

[omniaforever]

Originariamente inviato da gugoXX

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

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 )