Как перемешать массив чисел без повторения двух последовательных элементов?

Question

Я сейчас пытаюсь получить массив чисел, подобный этому, случайным образом перемешанный:

label_array = np.repeat(np.arange(6), 12)

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

# Check if there are any occurrences of two consecutive 
# elements being of the same category (same number)
num_occurrences = np.sum(np.diff(label_array) == 0)

# While there are any occurrences of this...
while num_occurrences != 0:
    # ...shuffle the array...
    np.random.shuffle(label_array)

    # ...create a flag for occurrences...
    flag = np.hstack(([False], np.diff(label_array) == 0))
    flag_array = label_array[flag]

    # ...and shuffle them.
    np.random.shuffle(flag_array)

    # Then re-assign them to the original array...
    label_array[flag] = flag_array

    # ...and check the number of occurrences again.
    num_occurrences = np.sum(np.diff(label_array) == 0)

Хотя это работает для массива такого размера, я не знаю, будет ли он работать для гораздо больших массивов.И даже в этом случае это может занять много времени.

Итак, есть ли лучший способ сделать это?

Answer 1

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

import numpy as np
def generate_random_array(block_length, block_count):
    for blocks in range(0, block_count):
        nums = np.arange(block_length)
        np.random.shuffle(nums)
        try:
            if nums[0] == randoms_array [-1]:
                nums[0], nums[-1] = nums[-1], nums[0]
        except NameError:
            randoms_array = []
        randoms_array.extend(nums)
    return randoms_array


generate_random_array(block_length=1000, block_count=1000)

Answer 2

Вот способ сделать это для Python> = 3.6, используя random.choices , что позволяет выбирать из совокупности с весами.

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

Как должным образом заметил @roganjosh, у нас возникает проблема в конце, когда у нас остается более одного экземпляра последнего значения - и это может быть очень часто, особенно при небольшом количестве значений и большомчисло повторений.

Я использовал решение, чтобы вставить эти значения обратно в список, где они не создают конфликт, с помощью функции short send_back.

import random

def send_back(value, number, lst):
    idx = len(lst)-2
    for _ in range(number):
        while lst[idx] == value or lst[idx-1] == value:
            idx -= 1
        lst.insert(idx, value)


def shuffle_without_doubles(nb_values, repeats):
    population = list(range(nb_values))
    weights = [repeats] * nb_values
    out = []
    prev = None
    for i in range(nb_values * repeats):
        if prev is not None:
            # remove prev from the list of possible choices
            # by turning its weight temporarily to zero
            old_weight = weights[prev]
            weights[prev] = 0    

        try:
            chosen = random.choices(population, weights)[0]
        except IndexError:
            # We are here because all of our weights are 0,
            # which means that all is left to choose from
            # is old_weight times the previous value
            send_back(prev, old_weight, out)
            break

        out.append(chosen)
        weights[chosen] -= 1
        if prev is not None:
            # restore weight
            weights[prev] = old_weight
        prev = chosen
    return out

---

print(shuffle_without_doubles(6, 12))

[5, 1, 3, 4, 3, 2, 1, 5, 3, 5, 2, 0, 5, 4, 3, 4, 5,
 3, 4, 0, 4, 1, 0, 1, 5, 3, 0, 2, 3, 4, 1, 2, 4, 1,
 0, 2, 0, 2, 5, 0, 2, 1, 0, 5, 2, 0, 5, 0, 3, 2, 1,
 2, 1, 5, 1, 3, 5, 4, 2, 4, 0, 4, 2, 4, 0, 1, 3, 4,
 5, 3, 1, 3]

Некоторая грубая синхронизация: генерация (shuffle_without_doubles(600, 1200)) занимает около 30 секунд, то есть 720000 значений.