Λοιπά θέματα

Απ: Unique combinations of vector elements...

Markos — Tue, 23 Jul 2013 07:14:52 GMT

Και για να γίνει κατανοητό το γιατί όλη αυτή η φασαρία, ο λόγος ακούει στο όνομα batch simulation/processing/testing (ό,τι σας πηγαίνει καλύτερα). Για τον ίδιο λόγο, αυτό που έχει σημασία είναι μόνο τα indexes και όχι τα types, τη στιγμή που κάθε vector μπορεί ν' αποτελείται από objects διαφορετικού type.

Παράδειγμα: Έστω ότι έχω δημιουργήσει ένα object Car και στον constructor περνάω τα εξής objects: TireType, WeatherCondition, RoadType, DriverSkill, PassengerCount. Έστω ακόμα ότι το car object έχει μόνο μία μέθοδο "Run(double miles)" που επιστρέφει το χρόνο που χρειάστηκε το όχημα για να διανύσει την απόσταση (με επάρκεια καυσίμου). Για κάθε ένα από τα objects του Constructor μπορώ να φτιάξω vectors με διαφορετικές ιδιότητες. Άλλο vector για τον τύπο του δρόμου και το πλήθος στροφών, άλλο vector για τις καιρικές συνθήκες (ήλιας, βροχή, χαλάζι), κ.λπ. Ακολούθως, κάνω generate τα combinations και λέω στο όχημα να "τρέξει", την ίδια απόσταση κάθε φορά, και συγκρίνω τους χρόνους. Μπορώ με τον τρόπο αυτό να μελετήσω πολλούς διαφορετικούς συνδυασμούς από input data γράφοντας πολύ λίγο κώδικα για τα vectors.

Νομίζω ότι τώρα η συζήτηση μπορεί να γίνει επί νέας βάσης...

Απ: Unique combinations of vector elements...

Markos — Tue, 23 Jul 2013 04:58:33 GMT

Παναγιώτη, τις βιβλιοθήκες τις είδα, έχεις κάποιο link που να οδηγεί σε κλάση που να κάνει αυτό που λέει ο τίτλος του post;

Τα generics ΔΕΝ μου κάνουν. Δε μ' ενδιαφέρουν τα original data παρά μόνο τα indexes. Αν παίρνω τους συνδυασμούς των δεικτών, όλα τα υπόλοιπα είναι straightforward...

ΠΡΟΣΘΗΚΗ: Για το IEnumerable έχεις δίκιο...

Απ: Unique combinations of vector elements...

Παναγιώτης Καναβός — Tue, 23 Jul 2013 04:44:19 GMT

Έψαξες για combinations και δεν βρήκες??

Μία αναζήτηση για c# combinations θα γυρίσει κάμποσα αποτελέσματα, ενώ υπάρχει τουλάχιστον ένα ειδικό NuGet package στο https://github.com/eoincampbell/combinatorics, υποστήριξη μεταξύ πολλών άλλων στο Math.Net Numerics package http://mathnetnumerics.codeplex.com/documentation κλπ

Όσον αφορά τον κώδικα, δεν υπάρχει λόγος να περιορίζεσαι σε int και λίστες. Τα combinations μπορούν να γίνουν για οποιοδήποτε τύπο οπότε καλύτερα είναι να χρησιμοποιήσεις generic methods. Επιπλέον από τη στιγμή που χρησιμοποιείς IEnumerable, μπορείς να χρησιμοποιήσεις iterators για να αποφύγεις τη δημιουργία μίας λίστας και να καθυστερήσεις τη δημιουργία των συνδυασμών μέχρι να ζητηθούν σε κάποιο foreach κλπ. Μπορείς επίσης να χρησιμοποιήσεις LINQ statements για τον ίδιο σκοπό.

Αν αξίζει να συζητήσει κανείς πως να δημιουργήσει combinations, αυτό είναι ίσως στο πως μπορείς να επιταχύνεις τη δημιουργεία τους παράλληλα αν μιλάμε για μεγάλο αριθμό στοιχείων

Unique combinations of vector elements...

Markos — Tue, 23 Jul 2013 01:43:47 GMT

Υπάρχουν περιπτώσεις που έχω ανύσματα διαφορετικών διαστάσεων και θέλω να πάρω όλους τους μοναδικούς συνδυασμούς των στοιχείων τους. Ένα παράδειγμα του προβλήματος μπορείτε να βρείτε εδώ. Δυστυχώς, όσο κι αν έψαξα στο 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;
        }

    }