Блог

Я хочу отсортировать список целых чисел таким образом, чтобы они в конечном итоге были распределены как можно больше. Предполагая базу 8, порядок элементов от 1 до 7 должен быть: {4, 6, 2, 7, 1, 5, 3} согласно:

Конечно, существует значительная двусмысленность, поскольку и 6, и 2 одинаково далеки от 4, 0 и 8, поэтому конкретный порядок 6 и 2 не имеет значения. Чего я пытаюсь добиться, так это сначала выбрать число, наиболее удаленное от 0 и base , затем выбрать число, наиболее удаленное от 0 base и first number и т.д. Любое кратное базовому никогда не произойдет, поэтому мне все равно, как это обрабатывается.

Я могу вручную разработать порядок сортировки для любой заданной базы, но мне нужно, чтобы это работало для любого base >= 2 . Есть ли умный / быстрый способ вычислить это или мне нужно лениво создавать таблицы сопоставления сортировки и кэшировать их для будущего использования?

 int SortOrder(int radix, int value)
{
  int offset = value % radix;     
  int[] table = {int.MinValue, 4, 2, 6, 0, 5, 1, 3}; // Hand-crafted for base-8
  return table[offset];
}
  

Это определенно не ответ на вопрос, поскольку он не пытается быстро найти ответ. Скорее он создает словарь кэшированных значений сортировки для каждого основания.

 #region sorting logic
/// <summary>
/// Maintains a collection of sorting maps for all used number bases.
/// </summary>
private static readonly Dictionary<int, int[]> _sortingTable = new Dictionary<int, int[]>();
private static readonly object _sortingLock = new object();

/// <summary>
/// Compute the sorting key for a given multiple.
/// </summary>
/// <param name="radix">Radix or base.</param>
/// <param name="multiple">Multiple.</param>
/// <returns>Sorting key.</returns>
public static int ComputeSortingKey(int radix, long multiple)
{
  if (radix < 2)
    throw new ArgumentException("Radix may not be less than 2.");

  if (multiple == 0)
    return int.MinValue; // multiple=0 always needs to be sorted first, so pick the smallest possible key.

  int[] map;
  if (!_sortingTable.TryGetValue(radix, out map))
    lock (_sortingLock)
    {
      map = new int[radix];
      map[0] = -1; // Multiples of the radix are sorted first.

      int key = 0;
      HashSet<int> occupancy = new HashSet<int> { 0, radix };
      HashSet<int> collection = new HashSet<int>(1.ArrayTo(radix)); // (ArrayTo is an extension method in this project)
      while (collection.Count > 0)
      {
        int maxValue = 0;
        int maxDistance = 0;
        foreach (int value in collection)
        {
          int distance = int.MaxValue;
          foreach (int existingValue in occupancy)
            distance = Math.Min(distance, Math.Abs(existingValue - value));

          if (distance > maxDistance)
          {
            maxDistance = distance;
            maxValue = value;
          }
        }
        collection.Remove(maxValue);
        occupancy.Add(maxValue);
        map[maxValue] = key  ;
      }

      _sortingTable.Remove(radix); // Just in case of a race-condition.
      _sortingTable.Add(radix, map);
    }

  long offset = multiple % radix;
  if (offset != 0)
    if (multiple < 0)
      offset = radix - (Math.Abs(multiple) % radix);

  return map[(int)offset];
}
#endregion
  

Мой первоначальный ответ состоял в том, чтобы найти максимальную дельту. Чтобы проложить свой путь от выхода к входу, используйте одно и то же сравнение, но разные выборки:

  List<double> answer = new List<double>();
        List<double> doub = new List<double>() { 0, -1, 2, 3, 4, -5, 7 };//SORT this list for sorted results!
        List<double> lowerHalf = new List<double>();
        List<double> upperHalf = new List<double>();
        for (int i = 0; i < doub.Count; i  )
        {
            if (i <= (int)Math.Floor((double)doub.Count / 2))
                lowerHalf.Add(doub[i]);
            else
                upperHalf.Add(doub[i]);
        }

        if (upperHalf.Count < lowerHalf.Count)
        {
            upperHalf.Insert(0,lowerHalf[lowerHalf.Count-1]);
        }
        //if(upperHalf[0]==lowerHalf[lowerHalf.Count-1]){double median = lowerHalf[lowerHalf.Count-1] upperHalf[1])/2;lowerHalf[lowerHalf.Count-1] = median; upperHalf[0]=median;}//use Math.Round or Math.Floor/Ceiling if necessary
        for (int i = 0; i < lowerHalf.Count; i  )
        {
            double deltas = Math.Sqrt(Math.Pow(upperHalf[upperHalf.Count - (i   1)] - lowerHalf[i], 2));
            answer.Add(deltas);
             Console.WriteLine("The answer for {1}, {2} is: {0}", deltas, lowerHalf[i], upperHalf[upperHalf.Count - (i 1)]);
        }



        Console.ReadLine();
  

Это обеспечит:

Ответ для 0, 7: 7

Ответ для -1, -5: 4

Ответ для 2, 4: 2

Ответ для 3, 3: 0

ОБРАТИТЕ внимание, что в случае нечетного числа элементов в исходном диапазоне этот метод использует один и тот же элемент как для верхнего, так и для нижнего списков. Я добавил строку для использования «фактической» медианы в ваших интересах

Чтобы избавиться от дубликатов, используйте hashset, union или distinct()

Оригинальный ответ — найти максимальную дельту):

Вы можете использовать математику в своем Linq, например:

    List<double> doub = new List<double>() { 0, 1, 2, 3, 4, 5, 7 };
        double deltas =  doub.Select(p => p - doub.First()).OrderBy(p => p).Last();
        Console.WriteLine("The answer is: {0}",deltas);
        Console.ReadLine();
  

Если ваши значения становятся отрицательными, вам нужно будет использовать квадраты:

  double deltas = Math.Sqrt( doub.Select(p => Math.Pow(p - doub.First(), 2)).OrderBy(p => p).Last());
  

или математика.Abs или тест, чтобы увидеть, какой из них больше — но это должно дать вам представление о том, как начать. Если числа не в порядке в исходном списке, вы также можете вызвать orderby перед select .

Буквально:

          List<double> doub = new List<double>() { 0, 1, 2, 3, 4, 5, 7 };
        double deltas = Math.Sqrt( doub.Select(p => Math.Pow(p - doub.First(), 2)).OrderBy(p => p).Last());
        Console.WriteLine("The answer is: {0}",deltas);
        Console.ReadLine();
  

производит

 'OilTracker.vshost.exe' (CLR v4.0.30319: OilTracker.vshost.exe): Loaded 'C:UsersUserDocumentsVisual Studio 2015ProjectsOilTrackerOilTrackerbinDebugTDAInterface.dll'. Symbols loaded.
 'OilTracker.vshost.exe' (CLR v4.0.30319: OilTracker.vshost.exe): Loaded 'C:UsersUserDocumentsVisual Studio 2015ProjectsOilTrackerOilTrackerbinDebugBackFeeder.exe'. Symbols loaded.
  

Ответ: 7

Переходя к сортировке списка, используйте:

  List<double> answer = new List<double>();
        List<double> doub = new List<double>() { 0, 1, 2, 3, 4, 5, 7 };
        //sort doub if necessary
        foreach (double num in doub)
        {
            double deltas = Math.Sqrt(Math.Pow(doub.Select(p => p - num).OrderBy(p => p).Last(), 2));
            answer.Add(deltas);
            Console.WriteLine("The answer for {1} is: {0}", deltas,num);
        }
        Console.ReadLine();
  

(Опять же, используйте другой orderby, если список не в порядке).

Производит:

  'OilTracker.vshost.exe' (CLR v4.0.30319: OilTracker.vshost.exe): Loaded 'C:UsersUserDocumentsVisual Studio 2015ProjectsOilTrackerOilTrackerbinDebugTDA_Stream_Interface.dll'. Symbols loaded.
 The answer for 0 is: 7
 The answer for 1 is: 6
 The answer for 2 is: 5
 The answer for 3 is: 4
 The answer for 4 is: 3
 The answer for 5 is: 2
 The answer for 7 is: 0
  

Квадраты / квадратный корень помогают нам менять знаки и справляться с негативами — так

  List<double> doub = new List<double>() { 0, -1, 2, 3, 4, -5, 7 };
  

Производит:

  The answer for 0 is: 7
 The answer for -1 is: 8
 The answer for 2 is: 5
 The answer for 3 is: 4
 The answer for 4 is: 3
 The answer for -5 is: 12
 The answer for 7 is: 0
  

(которые не в порядке, потому что мне не удалось отсортировать список ни на входящей, ни на исходящей сторонах).

После запуска список «ответ» будет содержать результаты — ответы могут получить доступ к наименьшей дельте.Первый () и самый высокий по ответам.Last(). похожие дельты будут существовать для разных чисел на одинаковом расстоянии друг от друга — вы можете использовать преобразование HashSet в формуле, если хотите устранить повторяющиеся дельты. Если вам нужна помощь в этом, пожалуйста, дайте мне знать.

Если вам нужно сохранить числа, которые создали дельту, а также саму дельту, они доступны вам в цикле For / Each в качестве консоли.WriteLine() указывает.

Если вы хотите работать с диапазоном до медианы по обе стороны от медианы, вероятно, хорошей идеей будет разделить список и работать в парах. Сделайте 0 медианным в одном списке, а медиану — конечной во втором списке, отработайте в первом и во втором. Это должно привести вас к цели, но если вам нужна помощь в преодолении этого последнего горба, дайте мне знать.

Надеюсь, это поможет!!