将数组项均匀排列/分配

Question

将数组项均匀排列/分配

phparrayssortingmathmultidimensional-array

24

我有一个多维关联数组，其中有一个名为type的属性。它看起来像这样：

$data = array(
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "C"),
  array( "name" => "SomeName", "type" => "C")
);

我希望重新排列它，使物品更平均地分布（如果可能的话，减少重复类型的数量）。它应该看起来像这样：

array(
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "C"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "C"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B")
);

到目前为止，我尝试的是找到每种类型和总数的计数：

$count_a = 5;
$count_b = 3;
$count_c = 2;
$total = 10;

并且每种类型的比率比：

$ratio_a = 0.5; //(5/10)
$ratio_b = 0.3; //(3/10)
$ratio_c = 0.2; //(2/10)

我现在卡住了。我应该尝试创建一个名为index的数字属性，然后根据它进行排序吗？还是可以使用模运算符？如果可能的话，我也尝试将项目分成3个不同的数组。

- Miro

如果第一个是正确的，那么这是一种贪心算法，按比率排序，使用最大比率元素直到没有该类型的元素，然后继续下一个最大比率并迭代所有元素。 - Mohsen_Fatemi

1

呃，让我在回答中把它写下来... - Mohsen_Fatemi

1

如果“ababacabac”对您也适用，您可以尝试像“从最大堆中选择一个，与上次选择不同”的规则。 - RST

4

问题需要更精确。问题中说“如果可能，最小化重复类型”，但在评论中，您表示愿意付出重复类型的代价来获得重复的模式。您应该在问题中澄清什么是最佳解决方案，消除所有歧义。 - trincot

1

请检查答案并给予一些反馈。 - AbraCadaver

显示剩余11条评论

10个回答

5

算法：

function distribute($data) {
    $groups = [];
    foreach ($data as $row) {
        $groups[$row['type']][] = $row;
    }
    $groupSizes = array_map('count', $groups);
    asort($groupSizes);

    $result = [];
    foreach ($groupSizes as $type => $groupSize) {
        if (count($result) == 0) {
            $result = $groups[$type];
        } elseif (count($result) >= count($groups[$type])) {
            $result = merge($result, $groups[$type]);
        } else {
            $result = merge($groups[$type], $result);
        }
    }
    return $result;
}

function merge($a, $b) {
    $c1 = count($a);
    $c2 = count($b);
    $result = [];
    $i1 = $i2 = 0;
    while ($i1 < $c1) {
        $result[] = $a[$i1++];
        while ($i2 < $c2 && ($i2+1)/($c2+1) < ($i1+1)/($c1+1)) {
            $result[] = $b[$i2++];
        }
    }
    return $result;
}

主要思想是将数据分成组，并将下一个最小的组合并到结果中（从空结果开始）。

在合并两个数组时，项目按浮点键排序，该键在此行中计算（在流中）。

while ($i2 < $c2 && ($i2+1)/($c2+1) < ($i1+1)/($c1+1))

作为

floatKey = (index + 1) / (groupSize + 1)

然而，这一部分可以改进，使得到“角落”(0和1)的距离是两个项目之间距离的一半。

在并列时，来自较大组的项目先出现。

例如：合并AAAA和BB，A的键为0.2, 0.4, 0.6, 0.8，B的键为0.33, 0.66。结果将是

A(0.2), B(0.33), A(0.4), A(0.6), B(0.66), A(0.8)

测试：

$testData = [
    'AAAAABBBCC',
    'AAAAABBBCCC',
    'ABBCCC',
    'AAAAAABBC',
    'AAAAAABBBBCCD',
    'AAAAAAAAAABC',
    'hpp',
    'stackoverflow',
    'ACCD', // :-)
];

$results = [];

foreach ($testData as $dataStr) {
    $a = str_split($dataStr);
    $data = [];
    foreach ($a as $type) {
        $data[] = ['type' => $type];
    }
    $result = distribute($data);
    $resultStr = implode(array_column($result, 'type'));
    $results[$dataStr] = $resultStr;
}
var_export($results);

测试结果：

'AAAAABBBCC' => 'BACABACABA',
'AAAAABBBCCC' => 'CABACABACAB',
'ABBCCC' => 'BCACBC',
'AAAAAABBC' => 'ABAACAABA',
'AAAAAABBBBCCD' => 'BACABADABACAB',
'AAAAAAAAAABC' => 'AAACAAAABAAA',
'hpp' => 'php',
'stackoverflow' => 'sakeofwlrovct',
'ACCD' => 'ACDC',

测试演示: http://rextester.com/BWBD90255

您可以轻松地向演示中添加更多的测试用例。

- Paul Spiegel

4

你需要拿到一个已排序的类型数组，逐步迭代地遍历它，将选择的类型每次改变一个。

$data = array(
  array( "name" => "SomeName1", "type" => "A"),
  array( "name" => "SomeName2", "type" => "A"),
  array( "name" => "SomeName3", "type" => "A"),
  array( "name" => "SomeName4", "type" => "A"),
  array( "name" => "SomeName5", "type" => "A"),
  array( "name" => "SomeName6", "type" => "B"),
  array( "name" => "SomeName7", "type" => "B"),
  array( "name" => "SomeName8", "type" => "B"),
  array( "name" => "SomeName9", "type" => "C"),
  array( "name" => "SomeName0", "type" => "C")
);

$dataSorted = array();
$counts = array();

foreach($data as $elem) {
    // just init values for a new type
    if(!isset($counts[$elem['type']])) {
        $counts[$elem['type']] = 0;
        $dataByType[$elem['type']] =  array();
    }

    // count types
    $counts[$elem['type']]++;

    // save it to grouped array
    $dataByType[$elem['type']][] =  $elem;
}

// sort it to A=>5, B=>3 C=>2
arsort($counts, SORT_NUMERIC);

// get sorted types as an array
$types = array_keys($counts);

// index will be looped 0 -> count($types) - 1 and then down to 0 again
$currentTypeIndex = 0;

// make a walk on sorted array. First get the most popular, then less popular etc.
// when all types are added, repeat
while(count($dataSorted) < count($data)) {
    $currentType = $types[$currentTypeIndex];

    // skip adding if we ran out this type
    if($counts[$currentType]) {
        // pop an element of selected type
        $dataSorted[] = array_pop($dataByType[$currentType]);

        // decrease counter
        $counts[$currentType]--;
    }

    // choose next type
    $currentTypeIndex = (++$currentTypeIndex)%count($types);
}

print_r($dataSorted);

这段代码按照ABCABCABAA的顺序输出元素。

更新：如果count(maxtype) > count(nexttype) + 1，则会出现尾部重复。

- shukshin.ivan

1

伊万，也许我错过了什么，但你的解决方案在这里显示了双倍的 A：https://3v4l.org/uS5ru。如果我们增加它们的数量，它甚至会显示更多。 - wersoo

1

对于作者的评论，“abcabcaa会更好，因为重复模式更长”。看起来模式的长度比双 A 更重要。如果“count(maxtype)”>“count(nexttype) + 1”，则会进行加倍。目的不清楚。 - shukshin.ivan

非常感谢。这个很好用！一开始的混淆很抱歉。 - Miro

3

$data = array(
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "C"),
  array( "name" => "SomeName", "type" => "C")
);

//make seperate arrays
echo "<pre>";
foreach($data as $val){

    ${$val["type"]}[]=$val["name"];
    $types[]=$val['type'];
}

$types=array_unique($types);

//make ratio
foreach($types as $val){
    $cnt[]=count($$val);
}
//find maximum from ratio
echo $max=max($cnt);
echo $min=min($cnt);


for($i=0;$i<$max;$i++){
    foreach($types as $val){

            if(isset($$val[$i])){
                $new_array[]=array("name"=>$$val[$i],"type"=>$val);
            }
        }
}

print_r($new_array);

Fiddle: http://phpfiddle.org/main/code/ju2k-abte

简介

     - Step 1: Make separate array   

     - Step 2: Count all array and find out the ratio



     - Step 3: Iterate with array with maximum ratio value
     - Step 4: Make array with same index together  and merge them in multidimensional
       array

- sumit

2

你可以像这样使用。

<?php
     $data = array(
        array( "name" => "SomeName 1", "type" => "A"),
        array( "name" => "SomeName 2", "type" => "A"),
        array( "name" => "SomeName 3", "type" => "A"),
        array( "name" => "SomeName 4", "type" => "A"),
        array( "name" => "SomeName 5", "type" => "A"),
        array( "name" => "SomeName 6", "type" => "B"),
        array( "name" => "SomeName 7", "type" => "B"),
        array( "name" => "SomeName 8", "type" => "B"),
        array( "name" => "SomeName 9", "type" => "C"),
        array( "name" => "SomeName 10", "type" => "C")
        );
        $result     = array();
        $typeArr    = array();
        $countArr   = array();
        $ratioArr   = array();

        foreach($data as $t){
           $typeArr[$t['type']][]   = $t;
           $countArr[$t['type']]    = count($typeArr[$t['type']]);
           $ratioArr[$t['type']]        = $countArr[$t['type']]/ count($data);
         }

        arsort($countArr);
        $countArrIndex = array_keys($countArr);
        $maxKeyCount = 0 ;$exceptMaxKey = 1;
        $exceptMaxKeyCount=0;
        for($i = 0; $i<count($data); $i++){
            if($i%2 != 0 ){
                 $result[$i]    =  $typeArr[$countArrIndex[$exceptMaxKey]][$exceptMaxKeyCount];
                 if($exceptMaxKey == (count($typeArr)-1)){
                     $exceptMaxKey  = 1;
                     $exceptMaxKeyCount++;
                 }else{
                     $exceptMaxKey++;
                 }

           }else{
               $result[$i]  =  $typeArr[$countArrIndex[0]][$maxKeyCount];
              $maxKeyCount ++;
           }
           }
        echo "<pre>";
        print_r($result);
        $countArr['total'] = count($data);
        print_r($countArr);
        print_r($ratioArr);

Thanks,

- Tonmoy Nandy

1

检查你想要的确切输出，

$data = array(
    array("name" => "SomeName", "type" => "A"),
    array("name" => "SomeName1", "type" => "A"),
    array("name" => "SomeName2", "type" => "A"),
    array("name" => "SomeName3", "type" => "A"),
    array("name" => "SomeName4", "type" => "A"),
    array("name" => "SomeName5", "type" => "B"),
    array("name" => "SomeName6", "type" => "B"),
    array("name" => "SomeName7", "type" => "B"),
    array("name" => "SomeName8", "type" => "C"),
    array("name" => "SomeName9", "type" => "C"),
);
// getting all counts
$type = [];
foreach ($data as $key => $value) {
    if (empty($type) || $type != $value['type']) {
        $type    = $value['type'];
        $counter = 0;
    }
    $temp[$value['type']] = ++$counter;
}
/**
 * array search with multiple values
 *
 * @param  array  $parents  input array
 * @param  array  $searched search array
 *
 * @return int    key of found items
 */
function multidimensional_search($parents, $searched)
{
    if (empty($searched) || empty($parents)) {
        return false;
    }
    foreach ($parents as $key => $value) {
        $exists = true;
        foreach ($searched as $skey => $svalue) {
            $exists = ($exists && isset($parents[$key][$skey]) && $parents[$key][$skey] == $svalue);
        }
        if ($exists) {return $key;}
    }
    return false;
}
$output_array = [];
$first_value  = current($temp);
$first_key    = key($temp);
$flag         = 0;
$junkArr      = array_column($data, 'type', 'name');
$remember_me  = 0;
$incr         = 0;
end($temp);
$end_item = key($temp);
reset($temp);
$remember_index = 0;
for ($i = 0; $i < count($data); $i++) {
    $output_array[] = $data[multidimensional_search($data, ['name' => key($junkArr), 'type' => current($junkArr)])];
    if ($temp[$first_key] > 0) {
        $temp[$first_key] = --$first_value;
    }
    $direction = (empty($direction) || $direction == 'reverse' ? "forward" : "reverse");
    for ($k = 0; $k <= $remember_me; $k++) {
        if ($direction == 'forward') {
            next($temp);
        } else {
            prev($temp);
            if ($k == 0) {
                $incr = $remember_me + 1;
            }
        }
    }
    $remember_me = $incr;
    if ($remember_me == count($temp) - 1) {
        $remember_me = 0;
    }
    $first_key   = key($temp);
    $first_value = current($temp);
    if (in_array($first_key, $junkArr)) {
        $saved_key = key($junkArr);
        reset($junkArr);
        while ($first_key !== current($junkArr)) {
            next($junkArr);
        }
        unset($junkArr[$saved_key]);
    }
}
pr($output_array);
die;

按照您的喜好进行映射。

试一试，它会起作用的。

我想做的是：

获取所有类型的所有计数器
然后将其与名称和类型映射，以便我们可以通过名称进行唯一识别
然后我在temp上使用指针变量来跟踪每种类型剩余的计数情况
我正在从上到下为每种类型填充输出数组中的唯一键值对。
我使用junkarray来移动指针以帮助计算剩余数量。

- Rahul

快到了：} - user7435409

0

这是另一种基于naktinis优秀答案思路的实现：

// split data into arrays of distinct type
$buckets = array_reduce($data, function($result, $item) {
    $type = $item["type"];
    if (!isset($result[$type])) {
        $result[$type] = [];
    }
    array_push($result[$type], $item);
    return $result;
}, []);
// sort buckets by size
usort($buckets, function($a, $b) {
    return count($b) - count($a);
});
// merge buckets to single array sorted by type
// and split to chunks of size of the largest bucket
$table = array_chunk(array_merge(...$buckets), count($buckets[0]));
// compute final array by merging each column
$result = [];
foreach (array_keys($table[0]) as $i) {
    $result = array_merge($result, array_column($table, $i));
}

在线尝试

。

- Joe

0

我不确定我的脚本使用方法是否正确，请检查一下

<?php

/* multidimensional array */
$data = array(
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "C"),
  array( "name" => "SomeName", "type" => "C")
);

/* Assign blank arrays for further use */
$a_array = $b_array = $c_array = $returnArray = array();

$count = count($data); // count array 

$x = $y = $z = $m = $a = $b = $c = 0;   // assiging variable with value 0 

for($i = 0; $i < $count; $i++)
{
    if($data[$i]['type'] == "A")
    {
        $a_array[$x]["name"] = $data[$i]["name"];
        $a_array[$x]["type"] = $data[$i]["type"];
        $x++ ;
    }
    elseif($data[$i]['type'] == "B")
    {
        $b_array[$y]["name"] = $data[$i]["name"];
        $b_array[$y]["type"] = $data[$i]["type"];
        $y++ ;
    }
    elseif($data[$i]['type'] == "C")
    {
        $c_array[$z]["name"] = $data[$i]["name"];
        $c_array[$z]["type"] = $data[$i]["type"];
        $z++ ;
    }
}

for($j = 0; $j < $count; $j++)
{
    if($j == 0 || $j % 2 == 0)
    {
        $returnArray[$m]["name"] = $a_array[$a]["name"];
        $returnArray[$m]["type"] = $a_array[$a]["type"];
        $a++ ;
    }
    else
    {
        if($j == 3 || $j == 7)
        {
            $returnArray[$m]["name"] = $c_array[$c]["name"];
            $returnArray[$m]["type"] = $c_array[$c]["type"];
            $c++ ;
        }
        else
        {
            $returnArray[$m]["name"] = $b_array[$b]["name"];
            $returnArray[$m]["type"] = $b_array[$b]["type"];
            $b++ ;
        }
    }

    $m++ ;
}

echo "<pre>";
print_R($returnArray);

?>

谢谢：）

- Aman Kumar

0

哇塞，这里有那么多庞大的函数。

请求 ABAC ABAC ... 完成：

function sortTypes(array $data, array $types)
{
    $result = [];
    while (!empty($data)) {
        $currentType = current($types);
        if (!next($types)) {
            reset($types);
        }
        foreach ($data as $key => $array) {
            if ($array['type'] === $currentType) {
                $result[$key] = $array;
                unset($data[$key]);
                break;
            }
        }
    }
    return $result;
}

$types = ['A', 'B', 'A', 'C']; // gets sorted by this pattern
$result = sortTypes($data, $types);

测试：

var_export($result);
// OUT: 
[
    0 => [
        'name' => 'SomeName',
        'type' => 'A',
    ],
    5 => [
        'name' => 'SomeName',
        'type' => 'B',
    ],
    1 => [
        'name' => 'SomeName',
        'type' => 'A',
    ],
    8 => [
        'name' => 'SomeName',
        'type' => 'C',
    ],
    2 => [
        'name' => 'SomeName',
        'type' => 'A',
    ],
    6 => [
        'name' => 'SomeName',
        'type' => 'B',
    ],
    3 => [
        'name' => 'SomeName',
        'type' => 'A',
    ],
    9 => [
        'name' => 'SomeName',
        'type' => 'C',
    ],
    4 => [
        'name' => 'SomeName',
        'type' => 'A',
    ],
    7 => [
        'name' => 'SomeName',
        'type' => 'B',
    ],
]

- cottton

0

如果你只想重新排列列表以最小化重复，一旦你有了每种类型的计数，就像这样

$count_a = 5;
$count_b = 3;
$count_c = 2;
$total = 10;

然后你可以选择最多的类型，从该类型中选择一行，并将其放置在正在创建的列表的位置0。然后递减该类型的计数，从未刚刚被选择的最流行类型中进行选择。继续执行，直到仅剩一种类型，然后将它们放置在列表末尾。

- E.D.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- naktinis · Accepted Answer

这里有一个尽可能避免重复模式的解决方案。

对于AAAAABBBCC，它将生成ABABABACAC;

对于AAAAABBBCCC，它将生成ABCABABACAC;

除了按类型计数排序之外，它在线性时间内运行（它接受未排序的数据数组）。结果保存在$distributed_data中。有关说明，请参见下文。

代码：

$data = array(
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "A"),
  array( "name" => "SomeName", "type" => "B"),
  array( "name" => "SomeName", "type" => "B"),
);

$distributed_data = array();
$counts = array();
$size = sizeof($data);

// Count values
foreach ($data as $entry) {
  $counts[$entry["type"]] = isset($counts[$entry["type"]]) ? $counts[$entry["type"]] + 1 : 1;
}

// Set counter
for ($i = 0; $i < $size; $i++) {
  $data[$i]["count"] = $counts[$data[$i]["type"]];
}

// Sort by count
usort($data, function($entry1, $entry2) {
    return $entry2["count"] <=> $entry1["count"];
});

// Generate the distributed array
$max_length = $data[0]["count"];
$rows = ceil($size / $max_length);
$last_row = ($size - 1) % $max_length + 1;
$row_cycle = $rows;

$row = 0;
$col = 0;
for ($i = 0; $i < $size; $i++) {
  if ($i == $rows * $last_row) {
    $row_cycle -= 1;
  }

  $distributed_data[$i] = $data[$row * $max_length + $col];

  $row = ($row + 1) % $row_cycle;
  if ($row == 0) {
    $col++;
  }
}

解释

首先，按每种类型的重复次数对条目进行排序。例如 CBBCAAB 变成了 BBBAACC。

然后想象一张表，它有最频繁出现的次数那么多列（例如如果你有 AAAABBCC，最频繁出现的次数将是 4，表将有 4 列）。

然后将所有条目从左到右写入表格，必要时跳到新行。

例如对于 AAAAABBBCCC，你会得到这样的表格：

为了生成最终分布式数组，只需从上往下读取条目，必要时向右移动到新列。

在上面的例子中，你会得到 ABCABABACAC。

要获得重复条目的唯一方法是在一列中有两个相同的字符，或者在向右移动到一列时遇到相同的字符。

第一种情况不可能发生，因为一个字符组需要环绕，而这是不可能的，因为没有字符组长度大于列数（这就是我们定义表格的方式）。

第二种情况只能发生在第二行没有填满的情况下。例如 AAAABB 会使第二行留下两个空单元格。