Алгоритм распределения предметов «равномерно»

25

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

Итак, для списка:

[1, 1, 2, 2, 3, 3]

Один из лучших результатов после перераспределения значений:

[1, 2, 3, 1, 2, 3]

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

Вот как измерить, если результат лучше, чем другие:

  1. Подсчитайте расстояния между каждым предметом и следующим предметом с одинаковым значением.

  2. Рассчитайте стандартное отклонение для этого набора расстояний. Более низкая дисперсия означает лучший результат.

Замечания:

  • При расчете расстояния и достижении конца списка без нахождения элемента с таким же значением мы возвращаемся к началу списка. Таким образом, самое большее, тот же элемент будет найден, и расстояние для этого элемента будет длиной списка. Это означает, что список циклический ;
  • Типичный список содержит ~ 50 наименований с ~ 15 различными значениями в разных количествах.

Так:

  • В результате [1, 2, 3, 1, 2, 3]расстояния равны [3, 3, 3, 3, 3, 3], а стандартное отклонение равно 0;
  • В результате [1, 1, 2, 2, 3, 3]расстояния равны [1, 5, 1, 5, 1, 5], а стандартное отклонение равно 2;
  • Что делает первый результат лучше второго (чем меньше отклонение, тем лучше).

Учитывая эти определения, я спрашиваю, какие алгоритмы или стратегии мне следует искать.

Moraes
источник
Похоже, что вы хотите решить (вариант оптимизации) проблему разделения , по крайней мере, приблизительно. Там, вероятно, много алгоритмов для этого!
Рафаэль
Перечитывая это, почему подсчет вхождений всех значений и затем циклическое размещение значений не всегда дает оптимальное решение?
Рафаэль

Ответы:

8

Я столкнулся с этим вопросом, исследуя аналогичную проблему: оптимальное добавление жидкостей для уменьшения расслоения. Похоже, мое решение будет применимо и к вашей ситуации.

Если вы хотите смешать жидкости A, B и C в пропорции 30,20,10 (то есть 30 единиц A, 20 единиц B и 10 единиц C), вы получите стратификацию, если добавите все A, затем все B, а затем все C. Вам лучше смешивать меньшие единицы. Например, делайте единичные добавления в последовательности [A, B, A, C, B, A]. Это полностью предотвратит расслоение.

Я нашел способ сделать это, рассматривая это как некое слияние, используя очередь с приоритетами. Если я создаю структуру для описания дополнений:

MergeItem
    Item, Count, Frequency, Priority

Частота выражается как «один на каждый N». Таким образом, А, который добавляется три раза из шести, имеет частоту 2 (6/3).

И инициализировать кучу, которая изначально содержит:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Теперь я удаляю первый элемент из кучи и выводю его. Затем уменьшите его количество на 1, увеличьте приоритет по частоте и добавьте его обратно в кучу. В результате получается куча:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Затем удалите B из кучи, выведите и обновите ее, затем добавьте обратно в кучу:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

Если я продолжу в том же духе, я получу желаемую смесь. Я использую пользовательский компаратор, чтобы гарантировать, что при вставке в кучу равных элементов Приоритета в первую очередь упорядочивается элемент с наибольшим значением частоты (т. Е. С наименьшей частотой).

Я написал более полное описание проблемы и ее решения в своем блоге и представил некоторый работающий код C #, который иллюстрирует ее. См. Равномерное распределение предметов в списке .

Обновление после комментариев

Я думаю, что моя проблема похожа на проблему ОП, и поэтому мое решение потенциально полезно. Я прошу прощения за то, что не сформулировал мой ответ больше в терминах вопроса ОП.

Первое возражение, что мое решение использует A, B и C, а не 0, 1 и 2, легко исправить. Это просто вопрос номенклатуры. Мне легче и менее запутанно думать и говорить «два А», а не «два 1». Но для целей этого обсуждения я изменил свои выводы ниже, чтобы использовать номенклатуру ОП.

Конечно, моя проблема связана с понятием расстояния. Если вы хотите «распределить вещи равномерно», подразумевается расстояние. Но, опять же, это был мой провал из-за того, что я не смог адекватно показать, насколько моя проблема похожа на проблему ОП.

Я провел несколько тестов с двумя примерами, которые предоставил ОП. То есть:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

В моей номенклатуре они выражены как [2,2,2] и [4,3,2,1] соответственно. То есть в последнем примере «4 элемента типа 0, 3 элемента типа 1, 2 элемента типа 2 и 1 элемент типа 3».

Я запустил свою тестовую программу (как описано ниже) и опубликовал свои результаты. При отсутствии данных от ОП я не могу сказать, похожи ли мои результаты, хуже или лучше его. Также я не могу сравнить свои результаты с результатами кого-либо еще, потому что никто другой не опубликовал их.

Однако я могу сказать, что алгоритм обеспечивает хорошее решение моей проблемы устранения стратификации при смешивании жидкостей. И, похоже, это дает разумное решение проблемы ОП.

Для результатов, показанных ниже, я использовал алгоритм, который я подробно описал в своей записи в блоге, с начальным приоритетом, установленным на Frequency/2, и модификатором кучи, измененным для более частого элемента. Здесь показан измененный код с комментариями к измененным строкам.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Запустив мою тестовую программу с первым примером OP, я получаю:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

Так что мой алгоритм работает для тривиальной задачи, при которой все числа равны.

За вторую проблему, которую опубликовал ОП, я получил:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

Я не вижу очевидного способа улучшить это. Его можно переставить, чтобы сделать расстояния для элемента 0 [2,3,2,3] или некоторого другого расположения 2 и 3, но это изменит отклонения для элементов 1 и / или 2. Я действительно не знаю, что «оптимальный» в этой ситуации. Лучше иметь большее отклонение по более частым или менее частым предметам?

Не имея других проблем в OP, я использовал его описания, чтобы составить несколько своих собственных. Он сказал в своем посте:

Типичный список содержит ~ 50 наименований с ~ 15 различными значениями в разных количествах.

Итак, мои два теста были:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

И мои результаты:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

И для второго примера:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0
Джим Мишель
источник
@DW Пожалуйста, смотрите мое обновление. Я считаю, что я показываю, как моя проблема похожа на проблему ОП, и как мой алгоритм обеспечивает решение проблемы ОП.
Джим Мишель
Хорошая вещь! Спасибо за отличное обновление. Upvoted.
DW
Довольно интересно, как я уже говорил ранее. Простота идеи привлекательна. Я не успел все это внимательно прочитать. Действительно ли ваше решение учитывает цикличность исходного вопроса? Может быть, есть способ адаптировать его для этой цели, но я не совсем уверен.
Бабу
@babou: Мои расчеты расстояний, как вы можете видеть из результатов, действительно оборачиваются, но сам алгоритм не учитывает циклический характер проблемы ОП. Я также не вижу способа, которым я мог бы адаптировать алгоритм для этого. Или, в этом отношении, как учет циклической природы улучшил бы результаты. Хотя интересно рассмотреть возможность удвоения всех значений (т. Е. Изменения [3,2,1] на [6,4,2]), что фактически будет одним и тем же. Я подозреваю, что алгоритм будет давать идентичные результаты.
Джим Мишель
6

Это "пахнет", как будто это может быть NP-трудно. Итак, что вы делаете, когда у вас NP-трудная проблема? Добавьте к этому эвристику, или алгоритм приближения, или используйте SAT-решатель.

В вашем случае, если вам не нужно абсолютно оптимальное решение, одной разумной отправной точкой может быть попытка смоделированного отжига . Существует естественный способ взять любое решение-кандидат и переместить его в соседнее решение-кандидат: случайным образом выбрать два элемента в списке и поменять их местами. Имитация отжига итеративно попытается улучшить решение. Вы можете найти много ресурсов по моделированию отжига, если вы не знакомы с ним. Вы также можете поэкспериментировать с другими наборами «локальных перемещений», которые вносят небольшие изменения в возможное решение, в надежде постепенно улучшить его (т. Е. Уменьшить стандартное отклонение расстояний).

ttt2xi,jxi,jijt2

Но я бы посоветовал вам начать с имитации отжига. Это первое, что я бы попробовал, потому что я думаю, что это может сработать.

DW
источник
Являются ли ваши предложения стандартным способом решения подобных задач планирования? Я предполагаю, что есть некоторое коммерческое программное обеспечение для этого. Как они справляются с этим?
Бабу
@babou, отличный вопрос - понятия не имею!
DW
Я дополнительно разработал детали моего алгоритма, но я сомневаюсь, что очень существующие приложения будут использовать это. На самом деле, мне даже интересно, решают ли приложения планирования проблему такого рода. Я просил информацию о SE.softwarerecs, так как я не вижу, как задать вопрос здесь, кроме как комментарий, как я только что сделал.
Бабу
Оптимальное решение может быть NP-трудной. Но вполне работоспособным решением является O (n log k), где n - общее количество элементов, а k - количество типов элементов. Смотрите мой ответ и мой связанный пост в блоге.
Джим Мишель
2

Эскиз эвристического алгоритма

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

vN[1 ..N]яNя

NvNvN/Nv

v

яN/NяNмодификацияNяN/Nя

Это будет направлять наш алгоритм.

N

я|N/Nя-v|

Это может быть значение с очень многими из очень немногих случаев вначале. Я думаю, что на самом деле это не имеет значения, так как ограничения, создаваемые занятыми слотами, пропорциональны количеству размещенных значений (?).

Первое рассматриваемое значение может быть размещено без каких-либо ограничений. Затем остальные значения должны быть размещены таким образом, чтобы минимизировать их вклад в стандартное отклонение, но только в слоты, оставленные свободными от любых значений, которые были размещены ранее.

Размещение вхождений значения в оставшиеся слоты может быть выполнено с помощью алгоритма динамического программирования, чтобы объединить вычисления, которые размещают одинаковое количество значений между двумя позициями, оставляя только те, которые имеют минимальный вклад в стандартное отклонение (т.е. минимальное значение для суммы квадратов их отклонений).

v

J|N/NJ-v|

Затем вы помещаете значения синглтона в оставшиеся слоты.

Я считаю, что в целом это должно дать разумное решение, но я пока не знаю, как это доказать или оценить разрыв с оптимальным решением.

Babou
источник
У меня такое же впечатление, что не имеет значения, если мы начнем с самых или наименее распространенных, оставляя синглтоны в стороне. Стратегия, которая, по- видимому, дала мне лучшие результаты, начинает сортировать значения по вхождению и размещать их в порядке, начиная с тех, которые встречаются чаще всего. Это естественно оставляет синглтоны до конца.
Мораес
vN/vВ
Вы имеете в виду, что для списка с 10 значениями [0, 0, 0, 0, 1, 1, 1, 2, 2, 3]и v 4мы бы поместили сначала значения 1( 10/3 = 3.33ближайший к v), затем 2( 10/2 = 5следующий ближайший), затем 0( 10/4 = 2.5)? Или: не могли бы вы привести пример «уменьшения среднего отклонения расстояния от значения v»?
Мораес
1
Нет, я делаю только наоборот. Если взять ваш пример, порядок позиционирования сначала O, поскольку его среднее расстояние 2,5 больше всего отклоняется от v = 4, затем 2, затем 1 и синглтона 3. - - - Предлагаете ли вы, чтобы я переписал более четко некоторые часть моего объяснения этой стратегии?
Бабу
Нет, все хорошо. Я попробую кое-что по этой идее и доложу.
Мораес
1

Похоже, я очень опаздываю на вечеринку, но отправляю сообщения на случай, если кто-то столкнется с этим снова. Мое решение похоже на плюс @ babou. Ранее сегодня у меня была проблема планирования во встроенной системе, которая привела меня к этой теме. У меня есть реализация, специфичная для моей проблемы в C, но я решил опубликовать более общее решение в Python здесь (версия C усложняется тем, что я ограничился небольшим стеком фиксированного размера и без памяти распределения, поэтому я выполняю весь алгоритм на месте). Используемая ниже методика сглаживания - это то, что вы можете использовать для рисования линии на экране с 2-битным цветом. Алгоритм здесь достигает более низкого балла (то есть лучше), когда измеряется с использованием суммы стандартного отклонения для входов, используемых Джимом Мишелем, чем это конкретное решение.

def generate(item_counts):
'''item_counts is a list of counts of "types" of items. E.g., [3, 1, 0, 2] represents
   a list containing [1, 1, 1, 2, 4, 4] (3 types of items/distinct values). Generate
   a new list with evenly spaced values.'''
# Sort number of occurrences by decreasing value.
item_counts.sort(reverse=True)
# Count the total elements in the final list.
unplaced = sum(item_counts)
# Create the final list.
placements = [None] * unplaced

# For each type of item, place it into the list item_count times.
for item_type, item_count in enumerate(item_counts):
    # The number of times the item has already been placed
    instance = 0
    # Evenly divide the item amongst the remaining unused spaces, starting with
    # the first unused space encountered.
    # blank_count is the number of unused spaces seen so far and is reset for each
    # item type.
    blank_count = -1
    for position in range(len(placements)):
        if placements[position] is None:
            blank_count += 1
            # Use an anti-aliasing technique to prevent bunching of values.
            if blank_count * item_count // unplaced == instance:
                placements[position] = item_type
                instance += 1
    # Update the count of number of unplaced items.
    unplaced -= item_count

return placements

Результаты для

Input counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sum of stddev: 16.8 (vs. 22.3 via Jim Mischel)

Input of counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sum of stddev: 18.0 (vs. 19.3 via Jim Mischel)

Если заданы входные данные в форме, заданной @moraes, можно преобразовать ее в форму, используемую этой функцией, за O (n) шагов, используя биты большой омега (n * log (n)) памяти, где n - количество элементов ( в списке с 255 элементами вам не понадобится больше 255 дополнительных байтов), если хранить параллельный массив с количеством повторений. Альтернативно, можно выполнить пару сортировок на месте с O (1) дополнительной памятью.

PS

import numpy
import collections

def evaluate(l):
    '''Given a distribution solution, print the sum of stddevs for each type in the solution.'''
    l2 = l * 2
    distances = [None] * len(l)
    distance_dict = collections.defaultdict(list)
    for i in range(len(l)):
        distances[i] = l2.index(l[i], i + 1) - i
        distance_dict[l[i]].append(l2.index(l[i], i + 1) - i)

    keys = list(distance_dict.keys())
    keys.sort()
    score = 0
    # Calculate standard deviations for individual types.
    for key in keys:
        sc = numpy.std(distance_dict[key])
        score += sc
    print('Stddev sum: ', score)

Редактировать: я знаю, что это решение не дает оптимальный результат по контрпримеру. Вход [6, 2, 1]производит [0, 1, 0, 0, 2, 0, 0, 1, 0]; лучшее решение есть [0, 0, 1, 0, 2, 0, 0, 1, 0].

lungj
источник
Я полагаю, что я объяснил свой алгоритм в комментариях к коду и основу для алгоритма в преамбуле.
Lungj
Я бы предпочел увидеть отдельное описание идей вашего алгоритма и краткий псевдокод для алгоритма. В настоящее время я вижу во вводном тексте (1) ваш подход похож на @ babou и (2) он использует технику сглаживания (каким-то образом). Кроме того, не все здесь читают Python. В любом случае, это старый ответ, поэтому я понимаю, если вы не хотите его улучшать, но я просто отмечаю наши ожидания на этом сайте - не только для вас, но и для других, которые могут натолкнуться на эту страницу в будущее и будьте склонны отвечать.
DW
0

Этот алгоритм работает с массивом целых чисел, где каждое целое представляет отдельную категорию. Он создает отдельные массивы для каждой категории. Например, если начальный массив [1, 1, 1, 2, 2, 3], он создаст три массива, [3], [2, 2], [1, 1, 1].

Оттуда он рекурсивно комбинирует два наименьших массива (в этом примере, [3] и [2,2]) и размещает элементы меньшего массива во втором наименьшем массиве, основываясь в основном на соотношении числа случаев большего против меньших категорий. В этом примере мы получим [2,3,2]. Затем он будет использовать этот массив в качестве меньшего массива, который будет объединен в следующий больший массив, пока не останется только один массив.

<?php
/**
 *This will separete the source array into separate arrays for each category
 */
function splitArrayByCategory($source) {

    //  index is the category, value is the tally
    $categoryCounts  = array_count_values($source);

    // Sort that list, keep index associations
    asort($categoryCounts);

    // build separate arrays for each category
    // index = order, smaller index = smaller category count
    // value = array of each category
    $separated = array();
    foreach ($categoryCounts as $category => $tally)
        $separated[] = array_fill(0, $tally, $category);

    return $separated;
}

/**
 * Will take the array of arrays generated by splitArrayByCategory, and merge
 * them together so categories are evenly distributed
 */
function mergeCategoryArrays($categoryArray) {

    // How many entries are there, for the smallest & second smallest categories
    $smallerCount = count($categoryArray[0]);
    $largerCount  = count($categoryArray[1]);

    // Used to determine how much space there should be between these two categories
    $space = $largerCount/$smallerCount;

    // Merge the array of the smallest category into the array of the second smallest
    foreach ($categoryArray[0] as $domIndex => $domain) {
        // Where should we splice the value into the second array?
        $location = floor($domIndex*$space+$domIndex+($space/2));
        // actually perform the splice
        array_splice($categoryArray[1], $location, 0, $domain);
    }

    // remove the smallest domain we just spliced into the second smallest
    unset($categoryArray[0]);

    // reset the indexes
    $categoryArray = array_values($categoryArray);

    // If we have more than one index left in the categoryArray (i.e. some things
    // still need to get merged), let's re-run this function,
    if (count($categoryArray)>1)
        $categoryArray = mergeCategoryArrays($categoryArray);

    return $categoryArray;
}

// The sample list we're working with.
// each integer represents a different category
$listSample = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,6,6,7,7,7,7];

// Split the sample list into separate arrays for each category
$listSplitByCategory = splitArrayByCategory($listSample);

// If there are not at least two categories, what's the point?
if (count($listSplitByCategory) < 2) throw new Exception("You need at least two categories");

// perform the actual distribution of categories.
$listEvenlyDistributed = mergeCategoryArrays($listSplitByCategory)[0];

// Display the array before and after the categories are evenly distributed
for ($i=0; $i<count($listSample); $i++) {
    print $listSample[$i].",";
    print $listEvenlyDistributed[$i]."\n";
}
vtim
источник
2
Это не сайт кодирования. Пожалуйста, не публикуйте ответы только по коду. Вместо этого мы хотели бы, чтобы вы объяснили идеи, лежащие в основе вашего ответа, и предоставили краткий псевдокод для вашего алгоритма.
DW
Добро пожаловать в информатику ! На тот случай, если вы не знали об этом или забыли на мгновение, чтение кода на одном конкретном языке обычно является одной из самых сложных задач, которые мы можем выполнить, иногда даже если код был написан нами. Это одна из причин, почему мы не очень ценим настоящий код на этом сайте, хотя он может представлять гораздо больше работы, чем свободно написанный псевдокод. Конечно, я ценю весь действующий рабочий код, который может быть запущен или мгновенно воспроизведен.
Apass.Jack
Объяснение есть. в прокомментированном демонстрационном коде; что не в некотором архаическом синтаксисе, таком как APL, но в простом для понимания синтаксисе, достаточно близком к псевдокоду. Поможет ли это, если мое объяснение будет написано не моноширинным шрифтом?
Вт
Да. Это помогает. Не все читают PHP, может быть, не все могут определить, что такое комментарий (может быть, это аргумент соломенного человека) или просто не хотят читать блок кода и интерпретировать его, а читать идею, которую вы включили сверху и это говорит обо всем. +1 от меня. Ваш код чистый и хорошо документированный, но мы просто не кодируем сайт, поэтому здесь важно текстовое описание. Спасибо за ваше редактирование.
Зло
-1

Код ANSI C

Этот код работает, представляя прямую линию в n-мерном пространстве (где n - количество категорий), проходящую через начало координат с вектором направления (v1, v2, ..., vi, ... vn), где vi - это число предметы в категории i. Начиная с начала координат, цель состоит в том, чтобы найти следующую ближайшую точку к линии. На примере [0 0 0 0 0 1 1 1 2 2 2 3] получается результат [0 1 2 0 3 1 0 2 0 1 2 0]. Используя пример Лунджа [0 0 0 0 0 0 1 1 2], мы получаем [0 1 0 0 2 0 0 1 0], что в точности совпадает с результатом Лунджа.

Алгоритм стал более эффективным за счет использования только целочисленной арифметики и учета только разницы между расстояниями от каждой точки до прямой.

#define MAXCATEGORIES 100

int main () {int i = 0; int j = 0; int catsize = 0; int vector [MAXCATEGORIES]; int point [MAXCATEGORIES]; int category = 0; int totalitems = 0; int best = 0; длинный d2 = 0L; длинный vp = 0L; long v2 = 0L; длинная дельта = 0L; длинная бета = 0L;

printf("Enter the size of each category (enter 0 to finish):\r\n");
do
{
    catsize = 0;
    #ifdef _MSVC_LANG
            scanf_s("%d", &catsize);
    #else
            scanf("%d", &catsize)
    #endif
    if (catsize > 0)
    {
        vector[categories] = catsize;
        totalitems += catsize;
        categories++;
    }
} while (catsize > 0);

for (i = 0; i < categories; i++)
{
    v2 += vector[i] * vector[i];
    point[i] = 0;
}

for (i = 0; i < totalitems; i++)
{
    for (j = 0; j < categories; j++)
    {
        delta = (2 * point[j] + 1)*v2 - (2 * vp + vector[j])*vector[j];
        if (j == 0 || delta < beta)
        {
            best = j;
            beta = delta;
        }
    }
    point[best]++;
    vp += vector[best];
    printf("%c ", best + '0');  // Change '0' to 'A' if you like letters instead
}
return 0;

}

дрх
источник
1
Добро пожаловать на сайт! Что касается форматирования, вам нужно сделать отступ для каждой строки кода с четырьмя пробелами, чтобы система правильно разметила. В общем, мы не ищем большие блоки кода в качестве ответов на вопросы, и, в частности, ваши процедуры ввода данных здесь ничего не добавляют. У вас есть некоторые объяснения в верхней части вашего поста, но было бы лучше остановиться на этом и сократить код.
Дэвид Ричерби
Это не сайт кодирования. Пожалуйста, не публикуйте ответы только по коду. Вместо этого мы хотели бы, чтобы вы объяснили идеи, лежащие в основе вашего ответа, и предоставили краткий псевдокод для вашего алгоритма.
DW
-1

мое решение:

    vc = train['classes'].value_counts()
    vc = dict(sorted(vc.items()))
    df = pd.DataFrame()
    train['col_for_sort'] = 0.0

    i=1
    for k,v in vc.items():
        step = train.shape[0]/v
        indent = train.shape[0]/(v+1)
        df2 = train[train['classes'] == k].reset_index(drop=True)
        for j in range(0, v):
        df2.at[j, 'col_for_sort'] = indent + j*step + 0.0001*i   
    df= pd.concat([df2,df])
    i+=1

    train = df.sort_values('col_for_sort', ascending=False).reset_index(drop=True)
    del train['col_for_sort']
Александр Косолапов
источник
Пожалуйста, используйте псевдокод (с некоторыми необходимыми комментариями), чтобы описать ваш алгоритм.
xskxzr
Это не сайт кодирования. Пожалуйста, не публикуйте ответы только по коду. Вместо этого мы хотели бы, чтобы вы объяснили идеи, лежащие в основе вашего ответа, и предоставили краткий псевдокод для вашего алгоритма.
DW