Алгоритм разделения массива на N групп на основе индекса элемента (должно быть что-то простое)

Question

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

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

Например, у нас есть массив из 30 элементов [e1, e2, ... e30], который нужно разделить на N = 3 группы, например:

group1: [e1, ..., e10]
group2: [e11, ..., e20]
group3: [e21, ..., e30]

Я придумал такой неприятный беспорядок для N = 3 (псевдоязык, я оставил умножение на 0 и 1 только для пояснения):

for(i=0;i<array_size;i++) {
   if(i>=0*(array_size/3) && i<1*(array_size/3) {
      print "group1";
   } else if(i>=1*(array_size/3) && i<2*(array_size/3) {
      print "group2";
   } else if(i>=2*(array_size/3) && i<3*(array_size/3)
      print "group3";
   }
}

Но каково будет правильное общее решение?

Спасибо.

Answer 1

Как насчет этого?

for(i=0;i<array_size;i++) {
  print "group" + (Math.floor(i/(array_size/N)) + 1)
}

Answer 2

Вот небольшая функция, которая будет делать то, что вы хотите - она ​​предполагает, что вы знаете количество групп, которые вы хотите создать:

function arrayToGroups(source, groups) {  

                     //This is the array of groups to return:
                     var grouped = [];

                     //work out the size of the group
                     groupSize = Math.ceil(source.length/groups);

                     //clone the source array so we can safely splice it
                     var queue = source;

                     for (var r=0;r<groups;r++) {
                       //Grab the next groupful from the queue, and append it to the array of groups
                       grouped.push(queue.splice(0, groupSize));            
                     }       
             return grouped;
}

И вы используете это как:

var herbs = ['basil', 'marjoram', 'aniseed', 'parsely', 'chives', 'sage', 'fennel', 'oregano', 'thyme', 'tarragon', 'rosemary'];

var herbGroups = arrayToGroups(herbs, 3);

, который возвращает:

herbGroups[0] = ['basil', 'marjoram', 'aniseed', 'parsely']
herbGroups[1] = ['chives', 'sage', 'fennel', 'oregano']
herbGroups[2] = ['thyme', 'tarragon', 'rosemary']

Он не выполняет никакой проверки работоспособности, чтобы убедиться, что вы передаете массив и число, но вы можете добавить это достаточно легко. Вы, вероятно, могли бы также создать прототип в объектном типе Javascript, что даст вам удобный метод toGroups для массивов.

Answer 3

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

function arrayToGroups($source, $pergroup) {  
    $grouped = array();
    $groupCount = ceil(count($source)/$pergroup);
    $queue = $source;
    for ($r=0; $r<$groupCount; $r++) {
        array_push($grouped, array_splice($queue, 0, $pergroup));    
    }       
    return $grouped;
}

Это спрашивает, сколько элементов иметь на группу вместо общего количества групп. PHP.

Answer 4

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

Объясненная версия на K (потомок APL):

split:{[values;n]    / define function split with two parameters
  enum:!n            / ! does enumerate from 0 through n exclusive, : is assign
  floor:_(#values)%n / 33 for this sample, % is divide, _ floor, # count
  cut:floor*enum     / 0 33 66 for this sample data, * multiplies atom * vector
  :cut _ values      / cut the values at the given cutpoints, yielding #cut lists
  }

values:1+!30           / generate values 1 through 30
n:3                    / how many groups to split into
groups:split[values;n] / set the groups

дает ожидаемый результат:

(1 2 3 4 5 6 7 8 9 10
 11 12 13 14 15 16 17 18 19 20
 21 22 23 24 25 26 27 28 29 30)

Краткая версия на K:

split:{((_(#x)%y)*!y)_ x}
groups:split[1+!30;3]

дает тот же результат:

(1 2 3 4 5 6 7 8 9 10
 11 12 13 14 15 16 17 18 19 20
 21 22 23 24 25 26 27 28 29 30)

Answer 5

Вероятно, существует бесконечное количество способов сделать это. Я бы предложил: для каждой группы создайте базовый указатель и посчитайте.

struct group {foo * ptr; size_t count };
group * pgroups = new group [ngroups];
size_t objects_per_group = array_size / ngroups;
for (unsigned u = 0; u < ngroups; ++u ) {
   group & g =  pgroups[u];
   size_t index = u * objects_per_group;
   g.ptr = & array [index];
   g.count = min (objects_per_group, array_size - index);  // last group may have less!
}
...`
for (unsigned u = 0; u < ngroups; ++u) {
   // group "g" is an array at pgroups[g].ptr, dimension pgroups[g].count
   group & g =  pgroups[u];
   // enumerate the group:
   for (unsigned v = 0; v < g.count; ++v) {
      fprintf (stdout, "group %u, item %u, %s\n",
         (unsigned) u, (unsigned) v, (const char *) g.ptr[v]->somestring);
}  }

delete[] pgroups;

Answer 6

int group[3][10];
int groupIndex = 0;
int itemIndex = 0;
for(i = 0; i < array_size; i++)
{
    group[groupIndex][itemIndex] = big_array[i];
    itemIndex++;
    if (itemIndex == 10)
    {
        itemIndex = 0;
        groupIndex++;   
    }
}

Answer 7

 const int g = 3;                      // number of groups
 const int n = (array_size + g - 1)/g; // elements per group

 for (i=0,j=1; i<array_size; ++i) {
    if (i > j*n)
        ++j;
     printf("Group %d\n", j);
 }

Answer 8

http://mathworld.wolfram.com/Permutation.html

Добавить к тому, что я говорил; здесь есть уравнение для представления перестановок порядков группировки.

Answer 9

Я думаю, что проблема немного сложнее; и учитывая, что вы рассматриваете группу только как одномерную проблему, вы получите очень странное представление о том, что собой представляют группы.

Во-первых, проблема размерна в зависимости от количества групповых простых чисел и групповых комбинаций, с которыми вы имеете дело. По математике; это представляется как n в степени n или n ^ n, которые можно перевести в! n (множитель n).

Если у меня есть 5 групп, выстроенных в виде (1, 2, 3, 4, 5), то я хотел бы представить их как определенные группы или комбинации групп согласно факториальному выражению, тогда комбинации становятся больше

Группа 1х1 = 1,2,3,4,5
Группа 2x1 = 12, 23, 45, 13, 14, 15, 21, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54
таким образом стратегия создает ветку систематической ветки (достаточно просто)
12, 13, 14, 15
21, 22, 23, 24
31, 32, 34, 35
41, 42, 43, 45
51, 52, 53, 55
Группа 1 + 2x2x1 = (1, 23, 45), (2, 13, 45), (3, 12, 45), (4, 12, 35), (1, 24, 35), (1, 25, 35), (1, 32, 45), (1, 34, 25), (1, 35, 24), ... и т. Д.

Как вы можете видеть, когда вы начинаете добавлять факторные наборы, сочетания становятся не так легко создать математическую ссылку для выражения терминов. Хуже всего, когда ты встаешь в базовый набор длиной> 3 или 4.

Если я понимаю ваш вопрос: вы хотите выразить в общих выражениях алгоритм, который позволяет вам программно создавать стратегии группировки?

Это сложный набор; и представлен лучше всего в исчислении; как теория множеств. В противном случае все, что вы делаете, - это обработка двумерного массива.

первый массив выражает стратегию группировки; второй массив выражает элементы группировки.

Я не думаю, что это то, что вас просят сделать, потому что термин «ГРУППА» в математике имеет очень конкретное распределение для этого термина. Вы не должны использовать термин группа; скорее выразите это как набор; set1, set2, если вы это делаете.

Set1 содержит элементы из set2; и поэтому для этого используется та же математика, что и для множеств и выражений. Поиск "Вин Диаграммы" и "Союз"; Избегайте использования термина группа, если вы не представляете фактор набора.
http://en.wikipedia.org/wiki/Group_(mathematics)

Я думаю, что вы пытаетесь выразить это группы в известном наборе или таблице; Это на примере Wikipedia.org D2.

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

Я работаю над той же проблемой в JavaScript; когда я закончу, я могу опубликовать это;). Это очень сложно.