algoritmo mescolamento per matrice bidimensionale con dati contigui

Question

Ho una matrice bidimensionale che presenta i seguenti valori a causa di un algoritmo ho generato,

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"} 
}; 

e desidero mescolare i dati all'interno degli array casuale così che i dati con gli stessi valori rimangono insieme ma la loro posizione cambia. per favore qualcuno può aiutare con questo.

per esempio, se la matrice è per essere mescolate dovrebbe apparire come questo,

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

ho subito scritto del codice per singola -Dimension array (anche se posso facilmente modificarlo in modo da essere in grado di lavorare con uno multi-dimensionale.). Finora sto postando e per favore fatemi sapere se sono sulla strada giusta.

UPDATE
codice aggiornato: ora funziona con Arays multidimensionali (testato).
UPDATE2
Ho trovato alcuni errori nel mio codice e li ho sistemati. Quindi ora funziona eccetto il requisito che gli stessi articoli non possano essere uno accanto all'altro non è ancora soddisfatto. Ma questo problema mi ha preso e devo risolverlo fino alla fine. Restate sintonizzati;)

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

Mi è piaciuta molto questa domanda. Ecco una soluzione di esempio. Il codice è commentato. L'ho provato sull'ingresso campione fornito nella domanda. La documentazione in codice

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; 
     } 
    } 
}