统一排列/分配数组项

Question

我有一个带有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个不同的数组,如果这样可以更容易.

Answer 1

这是一个尽可能避免重复模式的解决方案.

因为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留下第二行有两个空单元格.

Answer 2

算法：

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.8ANF为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

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

Answer 3

您应该采用排序类型的排序数组，并逐步迭代遍历它，将选定的类型更改为一个。

$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 的顺序输出元素。

UPD。尾随加倍发生在以下情况count(maxtype)>count(nexttype) + 1