排序数组以避免重复连续值

Question

我有以下数组

$categories = array("first",
"first",
"first",
"first",
"second",
"second",
"second",
"second",
"second",
"third",
"third",
"third",
"third",
"third",
"third",
"third",
"third",
"four",
"four",
"four",
"five",
"five",
"five",
"six",
"six",
"seven");

我想做的是在数组 上方排序，这样同一类别就不会一个接一个地出现在一行中。 即数组应该像

一样排序

array("first","second","third","four","five","six","seven","first","second","third"........)

我知道这可以通过 PHP 的 uasort() 函数来实现。但是我在考虑制作比较功能时遇到了麻烦。

另外，我可以采用的方法是将每个类别分块到单独的数组中，然后遍历每个数组以创建结果数组，但我不确定这是否有效。

任何提示将不胜感激。提前致谢

Answer 1

下面应该做你想做的：

$buckets = array_count_values($categories);

$results = array();

while (array_sum($buckets) > 0) {
    foreach ($buckets as $index => $value) {
        if ($value > 0) {
            $results[] = $index;
            $buckets[$index] = $value - 1;
        }
    }
}

print_r($results);

它将数组分解为唯一值和它们各自的频率，然后迭代每个值并将它们推入最终数组，直到所有值都被消耗。

结果

Array
(
    [0] => first
    [1] => second
    [2] => third
    [3] => four
    [4] => five
    [5] => six
    [6] => seven
    [7] => first
    [8] => second
    [9] => third
    [10] => four
    [11] => five
    [12] => six
    [13] => first
    [14] => second
    [15] => third
    [16] => four
    [17] => five
    [18] => first
    [19] => second
    [20] => third
    [21] => second
    [22] => third
    [23] => third
    [24] => third
    [25] => third
)

然后，需要将尾随值重新插入到最终结果中，这样就没有重复了……reader的练习:)

Answer 2

如果有人还在寻找这个，我已经创建了这个算法的工作原型。

流程图如下：

Python 实施：

import random

def randomize_list(input_list):
    randomized_list = input_list.copy()
    random.shuffle(randomized_list)
    return randomized_list


def get_repeated_items(input_list, type_key):
    repeated_items = []
    pre_sorted_list = []
    last_item = {}
    for item in input_list:
        if last_item and item[type_key] == last_item[type_key]:
            repeated_items.append(item)
            continue
        pre_sorted_list.append(item)
        last_item = item
    return repeated_items, pre_sorted_list

def recycle_repeated_items(repeated_items, pre_sorted_list, type_key):
    sorted_list = []
    last_item = {}
    changed = False
    for item in pre_sorted_list:
        filtered_types = [item[type_key]] + ([last_item[type_key]] if last_item else [])
        eligible_repeated_item = next(filter(lambda t: t[type_key] not in filtered_types, repeated_items), None)
        if eligible_repeated_item:
            changed = True
            repeated_items.remove(eligible_repeated_item)
            sorted_list.append(eligible_repeated_item)
        sorted_list.append(item)
        last_item = item
    return repeated_items, sorted_list, changed

def randomized_non_repeating_sort(input_list, type_key):
    randomized_list = randomize_list(input_list)
    repeated_items, sorted_list = get_repeated_items(randomized_list, type_key)
    repeated_items, sorted_list, changed = recycle_repeated_items(repeated_items, sorted_list, type_key)
    while repeated_items and changed:
        repeated_items, sorted_list, changed = recycle_repeated_items(repeated_items, sorted_list, type_key)
    return sorted_list + repeated_items

用法示例：

original_list = [
    {'id': 10, 'type': 'A'},
    {'id': 11, 'type': 'A'},
    {'id': 12, 'type': 'A'},
    {'id': 13, 'type': 'A'},
    {'id': 14, 'type': 'B'},
    {'id': 15, 'type': 'B'},
    {'id': 16, 'type': 'B'},
    {'id': 17, 'type': 'C'},
    {'id': 18, 'type': 'C'},
    {'id': 19, 'type': 'D'}
]

print('Original list:')
print(original_list)

print('Randomized non-repeating list (1 of 1,000,000 tests):')

for _ in range(1,1000000):
    output_list = randomized_non_repeating_sort(original_list, 'type')
    repeated_items = get_repeated_items(output_list, 'type')[0]
    if repeated_items:
        raise Exception('CONSECUTIVE REPEATED ITEM FOUND!')
    if len(output_list) != len(original_list):
        raise Exception('LIST LENGTH MISMATCH!')

print(output_list)

"""
Output:
[{'id': 15, 'type': 'B'},
 {'id': 10, 'type': 'A'},
 {'id': 17, 'type': 'C'},
 {'id': 12, 'type': 'A'},
 {'id': 19, 'type': 'D'},
 {'id': 13, 'type': 'A'},
 {'id': 18, 'type': 'C'},
 {'id': 16, 'type': 'B'},
 {'id': 11, 'type': 'A'},
 {'id': 14, 'type': 'B'}]
"""

我还写了一篇博客 post，详细介绍了该算法：https://tomaraei.com/random-sort-algorithm-without-consecutive-repeats/

排序数组以避免重复连续值

Sorting array to avoid repeating consecutive values

php

arrays

sorting

结果