Упорядочить/распределить элементы массива равномерно

Ответ 1

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

$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

Ответ 2

Здесь есть решение, которое позволяет избежать повторения шаблонов, когда это возможно.

Для 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 оставляет вторую строку с двумя пустыми ячейками.

Ответ 3

Алгоритм:

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 anf для 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

Вы можете легко добавить в тестовую версию еще несколько тестовых примеров.

Ответ 4

$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

Ответ 5

Проверьте этот точный вывод того, что вы хотите,

$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 для отслеживания вокруг вещей w.r.t count left для каждого типа
• Я заполняю выходной массив с уникальной парой значений ключа для каждого типа сверху вниз.
• Я использовал junkarray для перемещения указателя с помощью оставшегося количества.

Ответ 6

Вы можете использовать это как

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

Спасибо,

Ответ 7

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

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

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

Ответ 8

Здесь другая реализация, основанная на идее 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));
}

Попробуйте в Интернете.

Ответ 9

Я не уверен, что мой метод script правильный или нет, пожалуйста, проверьте один раз

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

?>

Спасибо:)

Ответ 10

OMG так много огромных функций здесь.

запросил 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',
    ],
]