如何平均分割一个数字数组

Question

假设我有以下数组：

array(1,1,2,1,4,5,7,2,3);

如何以最快的方式将这些数字放入x数组中？我们将使用3个数组，并使数字尽可能地平均分配，同时较大的数字放在最后。

例如：

array(1, 1, 1, 5);
array(7, 2);
array(4, 2, 3);

我担心这可能是一个P=NP问题，但它看起来很简单，不应该是。我似乎无法理解它。

类似问题：将数组分割为平衡和的P个子数组的算法

- Blakethepatton

---

“with the larger numbers at the end” 是什么意思？ - AbraCadaver

好的，如果不高效地实现它，我们会尝试让它更高效。 - AbraCadaver

类似这样的代码，但如果第4列中有大量数字，则脚本会失败。这是伪代码，但应该可以传达思想。 - Blakethepatton

@jaredk 没错。抱歉我的表述不够明确。 - Blakethepatton

不要删除并重新发布相同的问题，这很无礼。 - user557846

Answer 1

基本上您可以使用array_slice 来删除所需的块，使用asort首先将数组从最小到最大排序。

以下代码将完成此操作：

（编辑：在最近的评论之后，我很困惑，您是否意味着您希望数组中数字的总和接近？我认为您是指您希望数组分割成大小相等而不是总和？）

$arr = array(1,1,2,1,4,5,7,2,3);
asort($arr); // sort the array

$x = 3; // number of arrays
$offset = ceil(count($arr) / $x);

$newArrays = array();
for($i=0;$i<=count($arr)-1;$i+=$offset) {
  $newArrays[] = array_slice($arr,$i,$offset);
}

var_dump($newArrays);

结果：

array(3) {
  [0]=>
  array(3) {
    [0]=>
    int(1)
    [1]=>
    int(1)
    [2]=>
    int(1)
  }
  [1]=>
  array(3) {
    [0]=>
    int(2)
    [1]=>
    int(2)
    [2]=>
    int(3)
  }
  [2]=>
  array(3) {
    [0]=>
    int(4)
    [1]=>
    int(5)
    [2]=>
    int(7)
  }
}

- skrilled

---

同一个用户几个小时前问了同样的问题，就在我想回答的时候，问题被删除了...不管怎样，我使用的逻辑和你一样，只是我们可以使用array_chunk($array, $offset);代替for循环。 :) - Nikola Miljković

我实际上正在尝试让数组1-3具有相似的总数。抱歉在“较大的数字在末尾”方面造成了混淆。我的意思是对于总数为26，您将有两个总数为9的数组和一个总数为8的数组。我希望输出的方式是数组1的总数为8，数组2和3的总数为9。 - Blakethepatton

均匀分割求和。我正在尝试将一个数组分成P个子数组，使每个子数组的总和大致相等。 - Blakethepatton

Answer 2

也许不完全符合您的要求，但这应该有助于您入门：

$array = array(1,1,2,1,4,5,7,2,3);

asort($array);

$total = array_sum($array);

$array1 = array();
$array2 = array();
$array3 = array();

foreach($array as $number) {
    if(array_sum($array1) < round($total / 3)) {
        array_push($array1, $number);
    } elseif(array_sum($array2) < round($total / 3)) {
        array_push($array2, $number);
    } else {
        array_push($array3, $number);
    }
}

for($i = 1; $i <= 3; $i++) {

    switch($i) {
        case 1:
            $op1 = 2;
            $op2 = 1;
            break;
        case 2:
            $op1 = -1;
            $op2 = 1;
            break;
        case 3:
            $op1 = -2;
            $op2 = -1;
            break;
    }

    foreach(${'array' . $i} as $number) {
        if((array_sum(${'array' . ($i + $op1)}) + $number) == round($total / 3)) {
            unset(${'array' . $i}[array_search($number, ${'array' . $i})]);
            array_push(${'array' . ($i + $op1)}, $number);
        } elseif((array_sum(${'array' . ($i + $op2)}) + $number) == round($total / 3)) {
            unset(${'array' . $i}[array_search($number, ${'array' . $i})]);
            array_push(${'array' . ($i + $op2)}, $number);
        }
    }
}

print_r($array1);
print_r($array2);
print_r($array3);

新输出：

Array
(
    [0] => 1
    [1] => 1
    [2] => 1
    [4] => 2
    [5] => 3
)
Array
(
    [0] => 4
    [1] => 5
)
Array
(
    [0] => 7
    [1] => 2
)

- mattslone

---

那实际上非常接近我要找的东西。 - Blakethepatton

增加了一些排序以获得所需的结果。 - mattslone