[C# ma non solo] - Combinare elementi di array

[Kralizek]

Salve a tutti, causa anche sbornia della sera prima , mi sto perdendo in un bicchiere d'acqua.

Praticamente, dato un array di qualsiasi tipo (per l'esempio diremo string) di lunghezza non nota a priori,

var strings = new string[] { "a", "b", "c", "d" };

devo calcolare tutte le partizioni ordinate possibili composte da almeno 2 elementi.

a,b
a,c
a,d
b,c
b,d
c,d
a,b,c
a,b,d
a,c,d
b,c,d
a,b,c,d

Al momento ho scritto la versione per un array fatto da 4 elementi, peró l'algoritmo é generalizzabile, solo che non ci riesco -.-

void Main()
{
	var strings = new string[] { "a", "b", "c", "d" };
	
	List<string[]> result = new List<string[]>();
	
	//2
	for (int i = 0; i < strings.Length; i++)
	{
		string a1 = strings[i];
		
		for (int y = i+1; y < strings.Length; y ++)
		{
			result.Add( new string[]{a1, strings[y]});
		}
	}
	
	//3
	for (int i = 0; i < strings.Length; i++)
	{
		string a1 = strings[i];
		
		for (int y = i + 1; y < strings.Length; y ++)
		{
			string a2 = strings[y];
			
			for (int z = y + 1; z < strings.Length; z ++)
			{
				result.Add(new string[]{a1, a2, strings[z]});
			}
		}
	}
	
	//4
	for (int i = 0; i < strings.Length; i++)
	{
		string a1 = strings[i];
		
		for (int y = i + 1; y < strings.Length; y++)
		{
			string a2 = strings[y];
			
			for (int z = y + 1; z < strings.Length; z++)
			{
				string a3 = strings[z];
				
				for (int w = z + 1; w < strings.Length; w++)
				{
					result.Add(new string[]{a1, a2, a3, strings[w]});
				}
			}
		}
	}
	
	result.Dump();
}

Il codice puó essere agevolmente eseguito su LinqPad (lo conoscete vero?)

Perché dico che l'algoritmo dovrebbe essere generalizzabile? non ho fatto alcuno studio di fattibilitá a riguardo, ma ad occhio non mi sembra impossibile da risolvere...

La possibilitá di usare LINQ, ed eventualmente parallelizzare il tutto (con PLINQ o anche solo con i task) sarebbe un plus non invidiabile....

Grazie a tutti =)

[DanieleC88]

Guarda, la mia ignoranza riguardo a C# e LinqPad non mi consente di esserti di grosso aiuto, ma vedo che il procedimento che stai attuando è più o meno quello di generare l'insieme delle parti dell'insieme originario, ad esclusione però degli elementi che non superano una certa lunghezza.

Quindi un algoritmo in pseudocodice per generare l'insieme delle parti è il seguente:

algoritmo Insieme-Parti(array di interi A) → array di array di interi
{
    S = {∅};    // inizia con un insieme delle parti vuoto

    per ogni x ∈ A {
        S' = ∅;    // crea un insieme temporaneo di appoggio

        per ogni I ∈ S {
            I' = I ∪ {x};    // estendi il precedente insieme I con il nuovo elemento x
            S' = S' ∪ {I'};    // aggiungi il nuovo insieme I' così costruito ad S'
        }

        S = S ∪ {S'};    // aggiungi tutti gli elementi di S' ad S
    }

    restituisci S;
}

Alla fine otterrai tutti i possibili sottoinsiemi dell'insieme, il che purtroppo richiede tempo esponenziale (2ⁿ, perché ad ogni iterazione del ciclo esterno - e quindi per ogni elemento ricevuto in input - raddoppi la dimensione dell'insieme).

Fatto questo, puoi fare una scansione lineare di quanto hai ottenuto e rimuovere tutti quegli insiemi che hanno lunghezza minore di 2.

Ecco pronto il risultato.
ciao

[Kralizek]

grazie per lo spunto =)

ora devo vedere come togliere alcuni elementi indesiderati (tipo b,a,c,d)

[Kralizek]

risolto, per ora in maniera sequenziale... purtroppo ogni step é figlio dei risultati dello step i-1 quindi é difficilmente parallelizzabile in quel senso...

IEnumerable<T[]> GetParts<T>(T[] items)
{
	var container = new List<T[][]>();
	container.Add(items.Select(i => new[]{ i }).ToArray());
	
	for (int j = 1; j < items.Length; j++)
	{
		var parts = new List<T[]>();
		var itemsToAdd = items.Skip(j);

		for (int i = 0; i < container[j-1].Count(); i++)
		{
			for (int y = 0; y < itemsToAdd.Count(); y ++)
			{
				var indexOfLast = Array.IndexOf(items, container[j-1][i].Last());
				var indexOfItem = Array.IndexOf(items, itemsToAdd.ElementAt(y));
				
				if (indexOfLast < indexOfItem)
				{
					var list = new List<T>(container[j-1][i]);
					list.Add(itemsToAdd.ElementAt(y));
					parts.Add(list.ToArray());
				}
			}
		}
		
		container.Add(parts.ToArray());
	}
	
	return container.Skip(1).SelectMany(a => a);
}

[Kralizek]

continuo a cantarmela ed a suonarmela da solo...

ho scritto un programmino per testare le performance della funzione postata sopra anche per lo sfizio di provare ad usare la nuova TPL (Task Parallel Library) in .NET 4 (se vi interessa leggete questo facilissimo tutorial)

Ecco il codice di test:

void Main()
{
	List<Task> tasks = new List<Task>();
	
	for (int c = 2; c < 20; c++)
	{
		int itemsToProcess = c;

		var compute = Task.Factory.StartNew(() => 
		{
			var items = Enumerable.Range(1, itemsToProcess).ToArray();
			
			Stopwatch sw = Stopwatch.StartNew();
			GetParts(items);
			sw.Stop();

			return new Result { ItemsToProcess = itemsToProcess, Elapsed = sw.Elapsed };
		});
		
		tasks.Add(compute);
	}
	
	var r = Task.Factory.ContinueWhenAll(tasks.ToArray(), results => 
	{ 
		DataTable dt = new DataTable("Results");
		
		dt.Columns.Add("Processed items", typeof(int));
		dt.Columns.Add("Elapsed time", typeof(TimeSpan));
		dt.AcceptChanges();
		
		foreach(var task in results)
		{
			var result = (task as Task<Result>).Result ;
			
			var row = dt.NewRow();
			row.SetField<int>(0, result.ItemsToProcess);
			row.SetField<TimeSpan>(1, result.Elapsed);
						
			dt.Rows.Add(row);
			row.AcceptChanges();
		}
		dt.AcceptChanges();
		
		dt.Dump();
	});
	
	r.Wait();
}

IEnumerable<T[]> GetParts<T>(T[] items)
{
	var container = new List<T[][]>();
	container.Add(items.Select(i => new[]{ i }).ToArray());
	
	for (int j = 1; j < items.Length; j++)
	{
		var parts = new List<T[]>();
		var itemsToAdd = items.Skip(j);

		for (int i = 0; i < container[j-1].Count(); i++)
		{
			for (int y = 0; y < itemsToAdd.Count(); y ++)
			{
				var indexOfLast = Array.IndexOf(items, container[j-1][i].Last());
				var indexOfItem = Array.IndexOf(items, itemsToAdd.ElementAt(y));
				
				if (indexOfLast < indexOfItem)
				{
					var list = new List<T>(container[j-1][i]);
					list.Add(itemsToAdd.ElementAt(y));
					parts.Add(list.ToArray());
				}
			}
		}
		
		container.Add(parts.ToArray());
	}
	
	return container.Skip(1).SelectMany(a => a);
}

class Result
{
	public int ItemsToProcess { get; set; }
	public TimeSpan Elapsed { get; set; }
}

e questi sono i risultati ottenuti.

Processed items Elapsed time 

02    00:00:00.0051974
03    00:00:00.0753525
04    00:00:00.0746062
05    00:00:00.0468833
06    00:00:00.0147504
07    00:00:00.0462238
08    00:00:00.0771023
09    00:00:00.0907102
10    00:00:00.0672947
11    00:00:00.0307465
12    00:00:00.0631659
13    00:00:00.1878733
14    00:00:00.4249925
15    00:00:00.9270264
16    00:00:01.7154481
17    00:00:02.9197939
18    00:00:05.2214003
19    00:00:10.2407435

in realtá per avere dei tempi piú accurati non avrei dovuto usare il parallelismo perché i thread si rompono le palle tra di loro rubandosi cpu.

non a caso, studiando i tempi dei casi piú comuni (da 2 a 5 elementi) si hanno tempi che sono diversi da quelli postati prima.

2 00:00:00.0050126
3 00:00:00.0049253
4 00:00:00.0044408
5 00:00:00.0050880