Хороший алгоритм для объединения элементов из N списков в один со сбалансированным распределением?

Question

Допустим, у меня есть три следующих списка

A1
A2
A3

B1
B2

С1 * +1010 * С2
C3
C4
C5

Я бы хотел объединить их в один список, чтобы элементы из каждого списка были как можно более равномерно распределены, как это:

С1
A1
С2
B1
C3
A2
C4
B2
A3
C5

Я использую .NET 3.5 / C #, но я больше смотрю на то, как к нему подойти, а не на конкретный код.

РЕДАКТИРОВАТЬ: мне нужно сохранить порядок элементов из исходных списков.

Answer 1

1. Возьмите копию списка с большинством участников. Это будет список назначения.

2. Затем возьмите список со следующим наибольшим числом.

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

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

5. Повторите шаги 2-5 для всех списков.

РЕДАКТИРОВАТЬ: Преимущество в том, что O (n), что всегда приятно:)

Answer 2

Реализация Ответ Эндрю Роллингса:

public List<String> equimix(List<List<String>> input) {

  // sort biggest list to smallest list
  Collections.sort(input, new Comparator<List<String>>() {
     public int compare(List<String> a1, List<String> a2) {
        return a2.size() - a1.size();
     }
  });

  List<String> output = input.get(0);

  for (int i = 1; i < input.size(); i++) {
     output = equimix(output, input.get(i));
  }

  return output;
}

public List<String> equimix(List<String> listA, List<String> listB) {

  if (listB.size() > listA.size()) {
     List<String> temp;
     temp = listB;
     listB = listA;
     listA = temp;
  }

  List<String> output = listA;

  double shiftCoeff = (double) listA.size() / listB.size();
  double floatCounter = shiftCoeff;

  for (String item : listB) {
     int insertionIndex = (int) Math.round(floatCounter);
     output.add(insertionIndex, item);
     floatCounter += (1+shiftCoeff);
  }

  return output;
}

Answer 3

Во-первых, этот ответ - скорее ход мыслей, чем конкретное решение.

ОК, у вас есть список из 3 элементов (A1, A2, A3), где вы хотите, чтобы A1 находился где-то в первой 1/3 списка целей, A2 - во второй 1/3 списка целей. и А3 в третьем 1/3. Точно так же вы хотите, чтобы B1 был в первой половине, и т. Д ...

Таким образом, вы выделяете свой список из 10 в виде массива, а затем начинаете со списка, содержащего наибольшее количество элементов, в данном случае C. Вычислите место, где должен упасть C1 (1.5) Удалите C1 в ближайшем месте (в этом случае либо 1, либо 2), затем рассчитайте, где должен упасть C2 (3,5), и продолжайте процесс до тех пор, пока не исчезнет Cs.

Затем перейдите к списку со вторым по величине количеством предметов. В этом случае A. Рассчитайте, куда идет A1 (1.66), поэтому сначала попробуйте 2. Если вы уже положили туда C1, попробуйте 1. Сделайте то же самое для A2 (4.66) и A3 (7.66). Наконец, мы делаем список B. B1 должен пойти на 2,5, поэтому попробуйте 2 или 3. Если оба взяты, попробуйте 1 и 4 и продолжайте двигаться радиально, пока не найдете пустое место. Сделайте то же самое для B2.

Вы получите что-то подобное, если выберете меньшее число:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

или это, если вы выберете верхнее число:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

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

Answer 4

• Составить хеш-таблицу из списков.
• Для каждого списка сохраните n-й элемент в списке под ключом (/ n (+ (length list) 1))
• При желании можно перемешать списки под каждым ключом в хэш-таблице или отсортировать их каким-либо образом
• Объединить списки в хэше по отсортированному ключу

Answer 5

Я думаю о подходе «разделяй и властвуй». На каждой итерации вы разбиваете все списки с элементами> 1 пополам и повторяете. Когда вы попадаете в точку, где все списки, кроме одного, состоят из одного элемента, вы можете случайным образом комбинировать их, поднимать уровень и случайным образом комбинировать списки, удаленные из того кадра, где длина была одна ... и так далее.

Я думаю о чем-то вроде следующего:

- filter lists into three categories
    - lists of length 1
    - first half of the elements of lists with > 1 elements
    - second half of the elements of lists with > 1 elements
- recurse on the first and second half of the lists if they have > 1 element
    - combine results of above computation in order
- randomly combine the list of singletons into returned list 

Answer 6

Быстрое предложение в псевдокоде python-ish:

merge = list()
lists = list(list_a, list_b, list_c)
lists.sort_by(length, descending)

while lists is not empty:
    l = lists.remove_first()
    merge.append(l.remove_first())
    if l is not empty:
        next = lists.remove_first()
        lists.append(l)
        lists.sort_by(length, descending)
        lists.prepend(next)

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

Answer 7

Вы можете просто объединить три списка в один список, а затем ОТМЕНИТЬ этот список. Несортированный список должен выполнить ваше требование «равномерно распределенного» без особых усилий.

Вот реализация несортировки: http://www.vanheusden.com/unsort/.