基于项索引将数组拆分为N组的算法(应该简单)

时间:2022-04-19 22:06:53

I feel that it should be something very simple and obvious but just stuck on this for the last half an hour and can't move on.

我觉得这应该是非常简单明了的事情,但是在过去的半个小时内就停留在这个问题上并且无法继续前进。

All I need is to split an array of elements into N groups based on element index.

我只需要根据元素索引将元素数组拆分为N组。

For example we have an array of 30 elements [e1,e2,...e30], that has to be divided into N=3 groups like this:

例如,我们有一个包含30个元素[e1,e2,... e30]的数组,必须分成N = 3个组,如下所示:

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

I came up with nasty mess like this for N=3 (pseudo language, I left multiplication on 0 and 1 just for clarification):

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

But what would be the proper general solution?

但是什么是适当的一般解决方案?

Thanks.

9 个解决方案

#1


8  

What about something like this?

这样的事情怎么样?

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

#2


3  

Here's a little function which will do what you want - it presumes you know the number of groups you want to make:

这里有一个小功能可以做你想做的事 - 它假设你知道你想要制作的团体数量:

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

And you use it like:

你使用它像:

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

var herbGroups = arrayToGroups(herbs, 3);

which returns:

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

It doesn't do any sanity checking to make sure you pass in an array and a number, but you could add that easily enough. You could probably prototype it into the Javascript's object type, too, which would give you a handy 'toGroups' method on Arrays.

它不会进行任何健全性检查以确保传入数组和数字,但您可以轻松地添加它。您可以将它原型化为Javascript的对象类型,这将为您提供一个方便的'toGroups'方法在数组上。

#3


2  

I modified Beejamin's function above and just wanted to share it.

我上面修改了Beejamin的功能,只是想分享它。

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

This asks how many items to have per group instead of how many groups total. PHP.

这会询问每组有多少项,而不是总共有多少组。 PHP。

#4


1  

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

#5


1  

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

#6


1  

There's probably an infinite number of ways of do this. I'd suggest: for each group, create a base pointer and count.

可能有无数种方法可以做到这一点。我建议:对于每个组,创建一个基指针和计数。

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;

#7


1  

Using a vector language makes this task simple, right tool and all that. Just thought I'd throw this out there to let folks check out an alternative methodology.

使用矢量语言使这项任务变得简单,正确的工具和所有这些。我以为我会把它扔到那里让人们检查另一种方法。

The explained version in K (an APL descendent):

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

yields the expected output:

产生预期的输出:

(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)

The short version in K :

K中的简短版本:

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

yields the same output:

产生相同的输出:

(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)

#8


0  

I think the problem is a little more complicated; and considering that your only look at group as a 1 dimensional problem your going to get a very odd view of what groups actually are.

我认为这个问题有点复杂;并且考虑到你只将组视为一维问题,你会得到一个非常奇怪的视图,看看组实际上是什么。

Firstly the problem is dimensional according to the number of group primes, and group combinations you are dealing with. In Mathematics; this is represented as n to the power of n or n^n which can be translated to !n (factor of n).

首先,问题是根据群体素数的数量和您正在处理的群组合来维度。在数学方面;这被表示为n到n或n ^ n的幂,其可以被转换为!n(因子n)。

If I have 5 groups arrayed as (1, 2, 3, 4, 5) then I wanted to represent it as certain groups or combonations of groups according to a factorial expression then the combonations get bigger

如果我5组排列成(1,2,3,4,5),那么我想它表示为某些组或根据阶乘表达式组combonations则combonations得到更大

Group 1x1 = 1,2,3,4,5
Group 2x1 = 12, 23, 45, 13, 14, 15, 21, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54
so the strategy creates a branch systematic branch (easy enough)
12, 13, 14, 15
21, 22, 23, 24
31, 32, 34, 35
41, 42, 43, 45
51, 52, 53, 55
Group 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), ... etc

组1x1 = 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),......等

As you can see when you begin to add factorial sets the comboniations become not so easy to create a mathematic reference to express the terms. It gets worst when you get up into a base set > 3 or 4 length.

正如您在开始添加阶乘集时所看到的那样,组合变得不那么容易创建表达术语的数学参考。当你进入长度> 3或4的基础时,它会变得更糟。

If I am understanding your question: you want to expressing in a generic terms an algorythm which allows you to create grouping strategies programmatically?

如果我理解你的问题:你想用通用术语表达一个允许你以编程方式创建分组策略的算法吗?

This is a complicated set; and is represented best in calculus; as set theory. Otherwise all your doing is a two dimensional array handling.

这是一个复杂的集合;并且在微积分中表现得最好;作为集合论。否则你所做的一切都是二维数组处理。

the first Array expresses the grouping strategy; the second Array expresses the grouping elements.

第一个Array表示分组策略;第二个数组表示分组元素。

I don't think this is what your being asked to do, because the term "GROUP" in mathematics has a very specific allocation for the term. You should not use the term group; rather express it as a set; set1, set2 if that is what you are doing.

我不认为这是你被要求做的事情,因为数学中的术语“GROUP”对这个术语有一个非常具体的分配。你不应该使用术语组;而是将其表达为一组; set1,set2如果你正在做的那样。

Set1 contains elements of set2; and therefor this is handled with the same mathematics as Sets and unions are expressed. Lookup "Vin Diagrams" and "Union"; avoid using the term group unless you are representing the factor of a set.
http://en.wikipedia.org/wiki/Group_(mathematics)

I think what you are trying to express is the groups within a known set or table; This is on the wikipedia.org example D2.

In which case that means you have to look at the problem like a rubik's cube; and it gets complicated.

I'm working the same problem in javascript; when I am done I might publish it ;). It's very complicated.

Set1包含set2的元素;因此,这是用与表示集合和联合的相同数学来处理的。查找“Vin Diagrams”和“Union”;除非您表示集合的因子,否则请避免使用术语组。 http://en.wikipedia.org/wiki/Group_(mathematics)我想你要表达的是已知集合或表格中的组;这是在wikipedia.org示例D2上。在这种情况下,这意味着你必须像rubik的立方体一样看待问题;它变得复杂了。我在javascript中工作相同的问题;当我完成时,我可能会发布它;)。这很复杂。

#9


0  

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

To Add to what I was saying; here is the Equation to represent permutations of grouping orders.

加上我说的话;这里是表示分组顺序排列的等式。

#1


8  

What about something like this?

这样的事情怎么样?

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

#2


3  

Here's a little function which will do what you want - it presumes you know the number of groups you want to make:

这里有一个小功能可以做你想做的事 - 它假设你知道你想要制作的团体数量:

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

And you use it like:

你使用它像:

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

var herbGroups = arrayToGroups(herbs, 3);

which returns:

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

It doesn't do any sanity checking to make sure you pass in an array and a number, but you could add that easily enough. You could probably prototype it into the Javascript's object type, too, which would give you a handy 'toGroups' method on Arrays.

它不会进行任何健全性检查以确保传入数组和数字,但您可以轻松地添加它。您可以将它原型化为Javascript的对象类型,这将为您提供一个方便的'toGroups'方法在数组上。

#3


2  

I modified Beejamin's function above and just wanted to share it.

我上面修改了Beejamin的功能,只是想分享它。

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

This asks how many items to have per group instead of how many groups total. PHP.

这会询问每组有多少项,而不是总共有多少组。 PHP。

#4


1  

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

#5


1  

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

#6


1  

There's probably an infinite number of ways of do this. I'd suggest: for each group, create a base pointer and count.

可能有无数种方法可以做到这一点。我建议:对于每个组,创建一个基指针和计数。

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;

#7


1  

Using a vector language makes this task simple, right tool and all that. Just thought I'd throw this out there to let folks check out an alternative methodology.

使用矢量语言使这项任务变得简单,正确的工具和所有这些。我以为我会把它扔到那里让人们检查另一种方法。

The explained version in K (an APL descendent):

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

yields the expected output:

产生预期的输出:

(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)

The short version in K :

K中的简短版本:

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

yields the same output:

产生相同的输出:

(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)

#8


0  

I think the problem is a little more complicated; and considering that your only look at group as a 1 dimensional problem your going to get a very odd view of what groups actually are.

我认为这个问题有点复杂;并且考虑到你只将组视为一维问题,你会得到一个非常奇怪的视图,看看组实际上是什么。

Firstly the problem is dimensional according to the number of group primes, and group combinations you are dealing with. In Mathematics; this is represented as n to the power of n or n^n which can be translated to !n (factor of n).

首先,问题是根据群体素数的数量和您正在处理的群组合来维度。在数学方面;这被表示为n到n或n ^ n的幂,其可以被转换为!n(因子n)。

If I have 5 groups arrayed as (1, 2, 3, 4, 5) then I wanted to represent it as certain groups or combonations of groups according to a factorial expression then the combonations get bigger

如果我5组排列成(1,2,3,4,5),那么我想它表示为某些组或根据阶乘表达式组combonations则combonations得到更大

Group 1x1 = 1,2,3,4,5
Group 2x1 = 12, 23, 45, 13, 14, 15, 21, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54
so the strategy creates a branch systematic branch (easy enough)
12, 13, 14, 15
21, 22, 23, 24
31, 32, 34, 35
41, 42, 43, 45
51, 52, 53, 55
Group 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), ... etc

组1x1 = 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),......等

As you can see when you begin to add factorial sets the comboniations become not so easy to create a mathematic reference to express the terms. It gets worst when you get up into a base set > 3 or 4 length.

正如您在开始添加阶乘集时所看到的那样,组合变得不那么容易创建表达术语的数学参考。当你进入长度> 3或4的基础时,它会变得更糟。

If I am understanding your question: you want to expressing in a generic terms an algorythm which allows you to create grouping strategies programmatically?

如果我理解你的问题:你想用通用术语表达一个允许你以编程方式创建分组策略的算法吗?

This is a complicated set; and is represented best in calculus; as set theory. Otherwise all your doing is a two dimensional array handling.

这是一个复杂的集合;并且在微积分中表现得最好;作为集合论。否则你所做的一切都是二维数组处理。

the first Array expresses the grouping strategy; the second Array expresses the grouping elements.

第一个Array表示分组策略;第二个数组表示分组元素。

I don't think this is what your being asked to do, because the term "GROUP" in mathematics has a very specific allocation for the term. You should not use the term group; rather express it as a set; set1, set2 if that is what you are doing.

我不认为这是你被要求做的事情,因为数学中的术语“GROUP”对这个术语有一个非常具体的分配。你不应该使用术语组;而是将其表达为一组; set1,set2如果你正在做的那样。

Set1 contains elements of set2; and therefor this is handled with the same mathematics as Sets and unions are expressed. Lookup "Vin Diagrams" and "Union"; avoid using the term group unless you are representing the factor of a set.
http://en.wikipedia.org/wiki/Group_(mathematics)

I think what you are trying to express is the groups within a known set or table; This is on the wikipedia.org example D2.

In which case that means you have to look at the problem like a rubik's cube; and it gets complicated.

I'm working the same problem in javascript; when I am done I might publish it ;). It's very complicated.

Set1包含set2的元素;因此,这是用与表示集合和联合的相同数学来处理的。查找“Vin Diagrams”和“Union”;除非您表示集合的因子,否则请避免使用术语组。 http://en.wikipedia.org/wiki/Group_(mathematics)我想你要表达的是已知集合或表格中的组;这是在wikipedia.org示例D2上。在这种情况下,这意味着你必须像rubik的立方体一样看待问题;它变得复杂了。我在javascript中工作相同的问题;当我完成时,我可能会发布它;)。这很复杂。

#9


0  

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

To Add to what I was saying; here is the Equation to represent permutations of grouping orders.

加上我说的话;这里是表示分组顺序排列的等式。