Υπάρχουν περιπτώσεις που έχω ανύσματα διαφορετικών διαστάσεων και θέλω να πάρω όλους τους μοναδικούς συνδυασμούς των στοιχείων τους. Ένα παράδειγμα του προβλήματος μπορείτε να βρείτε εδώ. Δυστυχώς, όσο κι αν έψαξα στο internet δε μπόρεσα να βρω μια υλοποίηση σε c# ή έστω σε java. Έτσι, έφτιαξα τη δική μου.
Μια προφανής προσέγγιση είναι να πολλαπλασιάζω μεταξύ τους τα διανύσματα διαδοχικά, έως ότου καταλήξω στον τελικό πίνακα των συνδυασμών των στοιχείων. Αυτό, βέβαια, έρχεται με κάποιο κόστος (μνήμης). Μια άλλη πιο κομψή προσέγγιση έρχεται από τη "λεξικογραφική" διάταξη των συνδυασμών. Ο παρακάτω κώδικας κάνει και τα δύο.
Το συνημμένο αρχείο περιέχει test project για να πειραματιστείτε μόνοι σας. Περιμένω τις παρατηρήσεις σας...
Have Fun!!
ΥΓ: Που είναι το εργαλείο για εισαγωγή κώδικα;
public static class ProductSet
{
/// <summary>
/// Multiplies two single dimensional sets and returns the unique combination of their elements.
/// </summary>
/// <param name="a">The first set</param>
/// <param name="b">The second set</param>
/// <returns></returns>
public static int[,] MulSet(int[] a, int[] b)
{
int rows = a.Length * b.Length;
int[,] product = new int[rows, 2];
//
int k = 0;
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < b.Length; j++)
{
product[k, 0] = a[ i ];
product[k, 1] = b[j];
k++;
}
}
//
return product;
}
//
/// <summary>
/// Multiplies a multidimensional set by a single dimensional set and returns the unique combination of their elements
/// </summary>
/// <param name="a">The multidimensional set</param>
/// <param name="b">The single dimentional set</param>
/// <returns></returns>
public static int[,] MulSet(int[,] a, int[] b)
{
int rows = a.GetLength(0) * b.Length;
int[,] product = new int[rows, a.GetLength(1) + 1];
//
int row = 0;
for (int i = 0; i < a.GetLength(0); i++)
{
for (int k = 0; k < b.Length; k++)
{
product[row, a.GetLength(1)] = b[k];
for (int j = 0; j < a.GetLength(1); j++)
{
product[row, j] = a[i, j];
}
row++;
}
}
//
return product;
}
//
/// <summary>
/// Returns the rows of the final matrix of the product of a collection of single dimensional sets
/// </summary>
/// <param name="intArrays">The collection of single dimentional sets</param>
/// <returns></returns>
public static int GetFinalMatrixRows(IEnumerable<int[]> intArrays)
{
int rows = 1;
foreach (int[] arr in intArrays)
{
rows = rows * arr.Length;
}
return rows;
}
//
//
/// <summary>
/// Returns a single combination from the product matrix
/// </summary>
/// <param name="row">The zero based row of the combination</param>
/// <param name="matrix">The product matrix</param>
/// <returns></returns>
public static int[] GetCombination(int row, int[,] matrix)
{
int[] combination = new int[matrix.GetLength(1)];
for (int j = 0; j < matrix.GetLength(1); j++)
{
combination[j] = matrix[row, j];
}
return combination;
}
//
public static string CombinationToString(int[] combination)
{
string combinationStr = "";
for (int i = 0; i < combination.Length-1; i++)
{
combinationStr = combinationStr + combination[ i ].ToString() + ", ";
}
combinationStr = combinationStr + combination[combination.Length - 1].ToString();
return combinationStr;
}
//
/// <summary>
/// Generates a single combination of the product set without generating the product matrix.
/// Combinations are generated lexicographically.
/// </summary>
/// <param name="row">The zero based row of the combination</param>
/// <param name="intArrays">The collection of sets</param>
/// <returns></returns>
public static int[] GenerateCombination(int row, IEnumerable<int[]> intArrays)
{
int[] combination = new int[intArrays.Count()];
//
IEnumerable<int[]> subArrays = ProductSet.GetSubArrays(intArrays);
for (int i = 0; i < intArrays.Count(); i++)
{
int subArrRows = ProductSet.GetFinalMatrixRows(subArrays);
int elIdx = row / subArrRows;
int element = intArrays.ElementAt(i)[elIdx];
combination[ i ] = element;
row = row - subArrRows * elIdx;
subArrays = ProductSet.GetSubArrays(subArrays);
if (subArrays.Count() == 0)
{
break;
}
}
combination[intArrays.Count() - 1] = intArrays.ElementAt(intArrays.Count() - 1)[row];
//
return combination;
}
private static IEnumerable<int[]> GetSubArrays(IEnumerable<int[]> intArrays)
{
List<int[]> subArrays = new List<int[]>();
//
for (int i = 1; i < intArrays.Count(); i++)
{
subArrays.Add(intArrays.ElementAt(i));
}
//
return subArrays;
}
}
Ακόμα κι ένας άνθρωπος μπορεί ν' αλλάξει τον κόσμο. Μη θέλεις να κυβερνήσεις. Απλά δείξε το μονοπάτι κι ο κόσμος θ' ακολουθήσει!!