shuffling algorithm for two-dimensional array with contiguous data

Question

i have a two dimensional array that has the following values due to an algorithm i created,

String [2,12] array = {
    {"ab","ab","ab","FREE","me","me","me","FREE","mo","mo","FREE","FREE"},
    {"so","so","FREE","no","no","FREE","to","to","to","FREE","do","do"}
};

and i wish to shuffle the data within the arrays randomly so that the data with the same values remain together but their location changes. please can someone help with this.

for example if the array is to be shuffled it should look like this,

 String [2,12] array = {
     {"me","me","me","FREE","so","so","FREE","mo","mo","FREE","do","do"},
     {"ab","ab","ab""FREE","to","to","to","FREE","no","no","FREE","FREE"}
 };

Answer 1

I quickly wrote some code for single-dimension array(though I can easily modify it to be capable for working with multi-dimensional one. ). So far I'm posting, and please let me know whether I'm on the right way.

UPDATE
Updated code: now it works with multidimensional arays(tested).
UPDATE2
I've found some bugs in my code and fixed them. So now it works except of requirement that same items can't be next to each other is not satisfied yet. But this problem got me and I gotta solve it till the end. Stay tuned ;)

 using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ShuffleTwoDimensionalArrayConsole
{
    public sealed class PackedItem
    {
        public string Value { get; private set; }
        public int Count { get; set; }

        public PackedItem(string value)
        {
            Value = value;
            Count = 1;
        }

        public string[] Expand()
        {
            string[] result = new string[Count];

            for (int i = 0; i < Count; i++)
            {
                result[i] = Value;
            }

            return result;
        }

        public override string ToString()
        {
            return string.Format("{0} - {1}", Value, Count);
        }
    }

    public static class Extensions
    {
        public static List<PackedItem> WithExcluded(this List<PackedItem> list, PackedItem item)
        {
            var list2 = list.ToList();
            list2.Remove(item);
            return list2;
        }

        public static List<PackedItem> WithIncluded(this List<PackedItem> list, PackedItem item)
        {
            var list2 = list.ToList();
            list2.Add(item);
            return list2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            string[,] input = new string[,]
            { 
                 { "ab","ab","ab","FREE","me","me","me","FREE","mo","mo","FREE","FREE"},
                 { "so","so","FREE","no","no","FREE","to","to","to","FREE","do","do"}
            };
            Console.WriteLine("Input:");
            Console.WriteLine(string.Join(", ", string.Join(", ", input.Cast<string>())));

            bool hasErrrors = false;
            int MAX_ITERATIONS = 10000;
            for (int i = 1; i <= MAX_ITERATIONS; i++)
            {
                try
                {
                    string[,] shuffled = Shuffle(input);

                    //Console.WriteLine("Shuffled:");
                    //Console.WriteLine(string.Join(", ", string.Join(", ", shuffled.Cast<string>())));
                    Verification.Verify(input, shuffled);
                    //Console.WriteLine("Verified");
                }
                catch (Exception exc)
                {
                    Console.WriteLine(exc.Message);
                    hasErrrors = true;
                }

                WriteProgress((1d * i) / MAX_ITERATIONS);
            }

            Console.WriteLine("Completed with {0}", (hasErrrors ? "errors" : "successfully"));
        }

        public static string[,] Shuffle(string[,] array)
        {
            List<PackedItem> packed = Pack(array);
            List<PackedItem> shuffled = Shuffle(packed);
            string[,] unpacked = Unpack(inputList: shuffled
                                        , rows: array.GetLength(0)
                                        , columns: array.GetLength(1));

            return unpacked;
        }

        private static List<PackedItem> Pack(string[,] array)
        {
            var list = new List<PackedItem>();



            for (int i = 0; i < array.GetLength(0); i++)
            {
                for (int j = 0; j < array.GetLength(1); j++)
                {
                    string s = array[i, j];

                    if (j == 0 || list.Count == 0)
                    {
                        list.Add(new PackedItem(s));
                        continue;
                    }

                    var last = list.Last();
                    if (s == last.Value)
                    {
                        last.Count += 1;
                        continue;
                    }
                    else
                    {
                        list.Add(new PackedItem(s));
                        continue;
                    }
                }
            }

            return list;
        }

        private static string[,] Unpack(List<PackedItem> inputList, int rows, int columns)
        {
            var list = inputList.ToList();
            string[,] result = new string[rows, columns];

            for (int i = 0; i < rows; i++)
            {
                List<PackedItem> packedRow = Pick(source: list, taken: new List<PackedItem>(), takeCount: columns);

                packedRow.ForEach(x => list.Remove(x));
                List<string> row = packedRow
                                    .Select(x => x.Expand())
                                    .Aggregate(seed: new List<string>(),
                                            func: (acc, source) => { acc.AddRange(source); return acc; });

                for (int j = 0; j < columns; j++)
                {
                    result[i, j] = row[j];
                }
            }

            return result;
        }

        private static List<PackedItem> Pick(List<PackedItem> source, List<PackedItem> taken, int takeCount)
        {
            if (taken.Sum(x => x.Count) == takeCount)
            {
                return taken;
            }
            foreach (var item in source.ToList())
            {
                var list = Pick(source.WithExcluded(item)
                                , taken.WithIncluded(item)
                                , takeCount);
                if (list != null)
                {
                    return list;
                }
            }
            return null;
        }

        private static bool HasAdjacent(List<PackedItem> taken)
        {
            PackedItem previous = null;
            foreach (var item in taken)
            {
                if (previous != null)
                {
                    if (previous.Value == item.Value)
                        return true;
                }
                previous = item;
            }
            return false;
        }

        private static List<PackedItem> Shuffle(List<PackedItem> list)
        {
            Random r = new Random();

            var result = list.ToList();

            for (int i = 0; i < list.Count; i++)
            {
                int a = r.Next(0, list.Count);
                int b = r.Next(0, list.Count);

                Swap(result, a, b);
            }

            return result;
        }

        private static void Swap(List<PackedItem> list, int a, int b)
        {
            var temp = list[b];
            list[b] = list[a];
            list[a] = temp;
        }

        private static void WriteProgress(double progress)
        {
            int oldTop = Console.CursorTop;
            int oldLeft = Console.CursorLeft;

            try
            {
                Console.CursorTop = 0;
                Console.CursorLeft = Console.WindowWidth - "xx.yy  %".Length;
                Console.WriteLine("{0:p}", progress);
            }
            finally
            {
                Console.CursorTop = oldTop;
                Console.CursorLeft = oldLeft;
            }
        }

        #region Verification

        private static class Verification
        {
            internal static void Verify(string[,] input, string[,] output)
            {
                VerifyCountsAreEqual(input, output);
                VerifySizesAreEquals(input, output);
                VerifyDoesNotHaveNulls(output);
                VerifyContainsSameItems(input, output);

                // TODO: get alrogith capable to pass next check
                // VerifyContainsNoAdjacentItems(input, output);
            }

            private static void VerifyContainsNoAdjacentItems(string[,] input, string[,] output)
            {
                var inputPacked = Pack(input);
                var outputPacked = Pack(output);

                if (inputPacked.Count() != outputPacked.Count())
                    throw new Exception("There are some adjacent items moved each other");

                foreach (var item in outputPacked)
                {
                    if (item.Count > 3)
                        Debugger.Break();
                    bool existsInOutput = inputPacked.Any(x => AreEqual(x, item));
                    if (!existsInOutput)
                    {
                        throw new Exception("There are some adjacent items moved each other");
                    }
                }
            }

            private static void VerifyContainsSameItems(string[,] input, string[,] output)
            {
                foreach (var item in Pack(input))
                {
                    bool contains = Contains(item, output);
                    if (!contains)
                    {
                        throw new Exception("output does not contain " + item);
                    }
                }
            }

            private static void VerifyCountsAreEqual(string[,] input, string[,] output)
            {
                if (input.Cast<string>().Count() != output.Cast<string>().Count())
                    throw new Exception("items count do not match");
            }

            private static void VerifyDoesNotHaveNulls(string[,] output)
            {
                if (output.Cast<string>().Any(x => x == null))
                {
                    throw new Exception("nulls found");
                }
            }

            private static void VerifySizesAreEquals(string[,] input, string[,] output)
            {
                int inputrows = input.GetLength(0);
                int inputcolumns = input.GetLength(1);

                int outputrows = output.GetLength(0);
                int outputcolumns = output.GetLength(1);

                if (inputrows != outputrows || inputcolumns != outputcolumns)
                    throw new Exception("sizes do not match");
            }

            private static bool Contains(PackedItem item, string[,] array)
            {
                int rows = array.GetLength(0);
                int columns = array.GetLength(1);

                int matchedCount = 0;
                for (int i = 0; i < rows; i++)
                {
                    for (int j = 0; j < columns; j++)
                    {
                        string value = array[i, j];
                        if (value == item.Value)
                        {
                            matchedCount++;
                            if (matchedCount == item.Count)
                            {
                                return true;
                            }
                            else
                            {
                                continue;
                            }
                        }
                        else
                        {
                            matchedCount = 0;
                        }
                    }
                }

                return false;
            }

            private static bool AreEqual(PackedItem a, PackedItem b)
            {
                return a.Count == b.Count && a.Value == b.Value;
            }
        }

        #endregion
    }
}

Answer 2

I really enjoyed this question. Here is a sample solution. Code is commented. I have tested it on the sample input provided in the question. Documentation in Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SandboxConoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            const int rowCount = 2;
            const int columnCount = 12;
            int minCount = 1;
            int maxCount = 1;
            var sourceArray = new String[rowCount, columnCount]{
                    {"ab","ab","ab","FREE","me","me","me","FREE","mo","mo","FREE","FREE"},
                    {"so","so","FREE","no","no","FREE","to","to","to","FREE","do","do"}
                       };

            var destinationArray = new String[rowCount, columnCount];

            //Print Source Array
            PrintArrayData(sourceArray, rowCount, columnCount);
            Console.WriteLine("\n\n");

            //Data Structures that store data row wise.
            var sourceRowData = new Dictionary<int,List<StringCount>>();
            var destinationRowData = new Dictionary<int, List<StringCount>>();

            //Make sourceArray more consumable. Put it into sourceRowData. See Initialize Documentation 
            Initialize(sourceArray, rowCount, columnCount, ref maxCount, sourceRowData);

            //Data Structure that stores data by count (Occurences)
            var countIndexDictionary = new Dictionary<int, List<StringCount>>();
            for (int index = minCount; index <= maxCount; index++)
            {
                countIndexDictionary.Add(index, GetDataMatchingCount(index, sourceRowData));             
            }


            //Create Destination Row Data
            var random = new Random();
            for (int row = 0; row < rowCount; row++)
            {
                var destinationList = new List<StringCount>();

                //Count List contains the order of number of within a row. for source row 0 : 3,1,3,1,2,2
                var countList = sourceRowData[row].Select(p => p.count);

                //Randomize this order.
                var randomizedCountList = countList.OrderBy(x => random.Next()).ToList();
                foreach (var value in randomizedCountList)
                {
                    //For each number (count) on the list select a random element of the same count.
                    int indextoGet = random.Next(0,countIndexDictionary[value].Count - 1);

                    //Add it to the destination List
                    destinationList.Add(countIndexDictionary[value][indextoGet]);

                    //Rempve from that string from global count list
                    countIndexDictionary[value].RemoveAt(indextoGet);
                }
                destinationRowData.Add(row, destinationList);
            }

            //Create Destination Array from Destination Row Data            
            for (int row = 0; row < rowCount; row++)
            {
                int rowDataIndex = 0;
                int value = 1;
                for (int column = 0; column < columnCount; column++)
                {
                    if (destinationRowData[row][rowDataIndex].count >= value)
                        value++;

                    destinationArray[row, column] = destinationRowData[row][rowDataIndex].value;
                    if (value > destinationRowData[row][rowDataIndex].count)
                    {
                        value = 1;
                        rowDataIndex++;
                    }
                }
            }

            //Print Destination Array
            PrintArrayData(destinationArray, rowCount, columnCount);
        }

        /// <summary>
        /// Initializes Source Array and Massages data into a more consumable form
        /// Input :{"ab","ab","ab","FREE","me","me","me","FREE","mo","mo","FREE","FREE"},
        ///         {"so","so","FREE","no","no","FREE","to","to","to","FREE","do","do"}
        ///         
        /// Output : 0, {{ab,3},{FREE,1},{me,3},{FREE,1},{mo,2},{FREE,2}}
        ///          1, {{so,2},{FREE,1},{no,2},{FREE,1},{to,3},{FREE,1},{do,2}}
        /// </summary>
        /// <param name="sourceArray">Source Array</param>
        /// <param name="rowCount">Row Count</param>
        /// <param name="columnCount">Column Count</param>
        /// <param name="maxCount">Max Count of any String</param>
        /// <param name="sourceRowData"></param>
        public static void Initialize(string[,] sourceArray, int rowCount, int columnCount, ref int maxCount, Dictionary<int, List<StringCount>> sourceRowData)
        {
            for (int row = 0; row < rowCount; row++)
            {
                var list = new List<StringCount>();
                for (int column = 0; column < columnCount; column++)
                {
                    if (list.FirstOrDefault(p => p.value == sourceArray[row, column]) == null)
                        list.Add(new StringCount(sourceArray[row, column], 1));
                    else
                    {
                        var data = list.LastOrDefault(p => p.value == sourceArray[row, column]);
                        var currentValue = sourceArray[row, column];
                        var previousValue = sourceArray[row, column - 1];

                        if (previousValue == currentValue)
                            data.count++;
                        else
                            list.Add(new StringCount(sourceArray[row, column], 1));

                        if (data.count > maxCount)
                            maxCount = data.count;
                    }
                }
                sourceRowData.Add(row, list);
            }
        }

        /// <summary>
        /// Gets List of words with similar number of occurences.
        /// input : 2
        ///         0, {{ab,3},{FREE,1},{me,3},{FREE,1},{mo,2},{FREE,2}}
        ///         1, {{so,2},{FREE,1},{no,2},{FREE,1},{to,3},{FREE,1},{do,2}}
        /// 
        /// 
        /// output : 2,{{mo,2},{FREE,2},{so,2},{no,2},{do,2}} - Not necessarily in that order.
        /// </summary>
        /// <param name="count">Occurance Count</param>
        /// <param name="rowData">Source Row Data</param>
        /// <returns></returns>
        public static List<StringCount> GetDataMatchingCount(int count, Dictionary<int, List<StringCount>> rowData)
        {
            var stringCountList = new List<StringCount>();
            var random = new Random();
            var rowList = rowData.Where(p => p.Value.FirstOrDefault(q => q.count == count) != null).OrderBy(x => random.Next());
            foreach (var row in rowList)
            {
                stringCountList.AddRange(row.Value.Where(p => p.count == count).Reverse());
            }
            return stringCountList;
        }

        /// <summary>
        /// Prints Arrays
        /// </summary>
        /// <param name="data"></param>
        /// <param name="rowCount"></param>
        /// <param name="columnCount"></param>
        public static void PrintArrayData(string[,] data,int rowCount,int columnCount) 
        {
            for (int row = 0; row < rowCount; row++)
            {
                for (int column = 0; column < columnCount; column++)
                {
                    Console.Write(data[row, column] + " ");
                }
                Console.WriteLine();
            }
        }
    }

    public class StringCount
    {
        /// <summary>
        /// Value of String
        /// </summary>
        public string value { get; set; }

        /// <summary>
        /// Count of The String
        /// </summary>
        public int count { get; set; }

        public StringCount(string _stringValue, int _count)
        {
            value = _stringValue;
            count = _count;
        }
    }
}