Подтвердить что ты не робот

Создайте случайный порядок (x, y) пар, не повторяя/последующие x

Скажем, у меня есть список допустимых X = [1, 2, 3, 4, 5] и список допустимых Y = [1, 2, 3, 4, 5].

Мне нужно сгенерировать все комбинации каждого элемента в X и каждый элемент из Y (в данном случае, 25) и получить эти комбинации в случайном порядке.

Это само по себе было бы простым, но есть дополнительное требование: в этом случайном порядке не может быть повторения одного и того же X подряд. Например, это нормально:

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

Это не:

[1, 3]
[1, 2]  <== the "1" cannot repeat, because there was already one before
[2, 5]
...
[1, 4]

Теперь наименее эффективной идеей было бы просто рандомизировать полный набор, если повторений больше нет. Мой подход был несколько иным, неоднократно создавая перетасованный вариант X и список всех Y * X, а затем выбирал из него случайный следующий. До сих пор я придумал это:

import random

output = []
num_x  = 5
num_y  = 5

all_ys = list(xrange(1, num_y + 1)) * num_x

while True:
    # end if no more are available
    if len(output) == num_x * num_y:
        break

    xs = list(xrange(1, num_x + 1))
    while len(xs):
        next_x = random.choice(xs)
        next_y = random.choice(all_ys)

        if [next_x, next_y] not in output:
            xs.remove(next_x)
            all_ys.remove(next_y)
            output.append([next_x, next_y])

print(sorted(output))

Но я уверен, что это можно сделать еще более эффективно или более лаконично?

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

4b9b3361

ОТВЕТЫ

Ответ 1

Интересный вопрос! Вот мое решение. Он обладает следующими свойствами:

  • Если нет правильного решения, оно должно обнаружить это и сообщить вам
  • Итерация гарантированно завершается, поэтому она никогда не должна застревать в бесконечном цикле
  • Любое возможное решение доступно с ненулевой вероятностью

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

import random

def random_without_repeats(xs, ys):
    pairs = [[x,y] for x in xs for y in ys]
    output = [[object()], [object()]]
    seen = set()
    while pairs:
        # choose a random pair from the ones left
        indices = list(set(xrange(len(pairs))) - seen)
        try:
            index = random.choice(indices)
        except IndexError:
            raise Exception('No valid solution exists!')
        # the first element of our randomly chosen pair
        x = pairs[index][0]
        # search for a valid place in output where we slot it in
        for i in xrange(len(output) - 1):
            left, right = output[i], output[i+1]
            if x != left[0] and x != right[0]:
                output.insert(i+1, pairs.pop(index))
                seen = set()
                break
        else:
            # make sure we don't randomly choose a bad pair like that again
            seen |= {i for i in indices if pairs[i][0] == x}
    # trim off the sentinels
    output = output[1:-1]
    assert len(output) == len(xs) * len(ys)
    assert not any(L==R for L,R in zip(output[:-1], output[1:]))
    return output


nx, ny = 5, 5       # OP example
# nx, ny = 2, 10      # output must alternate in 1st index
# nx, ny = 4, 13      # shuffle 'deck of cards' with no repeating suit
# nx, ny = 1, 5       # should raise 'No valid solution exists!' exception

xs = range(1, nx+1)
ys = range(1, ny+1)

for pair in random_without_repeats(xs, ys):
    print pair

Ответ 2

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

import random

num_x = 5
num_y = 5

all_ys = range(1,num_y+1)*num_x
all_xs = sorted(range(1,num_x+1)*num_y)

output = []

last_x = -1

for i in range(0,num_x*num_y):

    #get list of possible tuple to place    
    all_ind    = range(0,len(all_xs))
    all_ind_ok = [k for k in all_ind if all_xs[k]!=last_x]

    ind = random.choice(all_ind_ok)

    last_x = all_xs[ind]
    output.append([all_xs.pop(ind),all_ys.pop(ind)])


    if(all_xs.count(last_x)==len(all_xs)):#if only last_x tuples,
        break  

if len(all_xs)>0: # if there are still tuples they are randomly placed
    nb_to_place = len(all_xs)
    while(len(all_xs)>0):
        place = random.randint(0,len(output)-1)
        if output[place]==last_x:
            continue
        if place>0:
            if output[place-1]==last_x:
                continue
        output.insert(place,[all_xs.pop(),all_ys.pop()])

print output

Ответ 3

Простое решение для обеспечения усреднения O(N*M):

def pseudorandom(M,N):
    l=[(x+1,y+1) for x in range(N) for y in range(M)]
    random.shuffle(l)
    for i in range(M*N-1):
            for j in range (i+1,M*N): # find a compatible ...
                if l[i][0] != l[j][0]:
                    l[i+1],l[j] = l[j],l[i+1]
                    break  
            else:   # or insert otherwise.
                while True:
                    l[i],l[i-1] = l[i-1],l[i]
                    i-=1
                    if l[i][0] != l[i-1][0]: break  
    return l

Некоторые тесты:

In [354]: print(pseudorandom(5,5))
[(2, 2), (3, 1), (5, 1), (1, 1), (3, 2), (1, 2), (3, 5), (1, 5), (5, 4),\
(1, 3), (5, 2), (3, 4), (5, 3), (4, 5), (5, 5), (1, 4), (2, 5), (4, 4), (2, 4),\ 
(4, 2), (2, 1), (4, 3), (2, 3), (4, 1), (3, 3)]

In [355]: %timeit pseudorandom(100,100)
10 loops, best of 3: 41.3 ms per loop

Ответ 4

Здесь решение с использованием NumPy

def generate_pairs(xs, ys):
    n = len(xs)
    m = len(ys)
    indices = np.arange(n)

    array = np.tile(ys, (n, 1))
    [np.random.shuffle(array[i]) for i in range(n)]

    counts = np.full_like(xs, m)
    i = -1

    for _ in range(n * m):
        weights = np.array(counts, dtype=float)
        if i != -1:
            weights[i] = 0
        weights /= np.sum(weights)

        i = np.random.choice(indices, p=weights)
        counts[i] -= 1
        pair = xs[i], array[i, counts[i]]
        yield pair

Здесь блокнот Jupyter, в котором объясняется, как он работает

Внутри цикла нам нужно скопировать весы, добавить их и выбрать случайный индекс, используя веса. Все они линейны в n. Таким образом, общая сложность генерации всех пар O(n^2 m)

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

Ответ 5

Это должно делать то, что вы хотите.

rando никогда не будет генерировать один и тот же X два раза подряд, но я понял, что это возможно (хотя кажется маловероятным, поскольку я никогда не замечал, что это произошло в 10 или около того раз, когда я бежал без дополнительной проверки), что из-за потенциального выброса повторяющихся пар это может произойти при предыдущем X. О! Но я думаю, что понял... обновит свой ответ через минуту.

import random

X = [1,2,3,4,5]
Y = [1,2,3,4,5]


def rando(choice_one, choice_two):
    last_x = random.choice(choice_one)
    while True:
        yield last_x, random.choice(choice_two)
        possible_x = choice_one[:]
        possible_x.remove(last_x)
        last_x = random.choice(possible_x)


all_pairs = set(itertools.product(X, Y))
result = []
r = rando(X, Y)
while set(result) != all_pairs:
    pair = next(r)
    if pair not in result:
        if result and result[-1][0] == pair[0]:
            continue
        result.append(pair)

import pprint
pprint.pprint(result)

Ответ 6

Равномерно распределите значения x (5 раз каждое значение) по вашему результату:

import random

def random_combo_without_x_repeats(xvals, yvals):
    # produce all valid combinations, but group by `x` and shuffle the `y`s
    grouped = [[x, random.sample(yvals, len(yvals))] for x in xvals]
    last_x = object()  # sentinel not equal to anything
    while grouped[0][1]:  # still `y`s left
        for _ in range(len(xvals)):
            # shuffle the `x`s, but skip any ordering that would
            # produce consecutive `x`s.
            random.shuffle(grouped)
            if grouped[0][0] != last_x:
                break
        else:
            # we tried to reshuffle N times, but ended up with the same `x` value
            # in the first position each time. This is pretty unlikely, but
            # if this happens we bail out and just reverse the order. That is
            # more than good enough.
            grouped = grouped[::-1]
        # yield a set of (x, y) pairs for each unique x
        # Pick one y (from the pre-shuffled groups per x
        for x, ys in grouped:
            yield x, ys.pop()
        last_x = x

Сначала сначала перемещается значения y на x, затем вы получаете комбинацию x, y для каждого x. Порядок, в котором даны x, перетасовывается на каждую итерацию, где вы проверяете ограничение.

Это случайное значение, но вы получите все числа от 1 до 5 в позиции x, прежде чем снова увидите тот же номер:

>>> list(random_combo_without_x_repeats(range(1, 6), range(1, 6)))
[(2, 1), (3, 2), (1, 5), (5, 1), (4, 1),
 (2, 4), (3, 1), (4, 3), (5, 5), (1, 4),
 (5, 2), (1, 1), (3, 3), (4, 4), (2, 5),
 (3, 5), (2, 3), (4, 2), (1, 2), (5, 4),
 (2, 2), (3, 4), (1, 3), (4, 5), (5, 3)]

(Я вручную сгруппировал это в набор из 5). В целом, это приводит к довольно хорошему случайному перетасовке фиксированного набора входных данных с вашим ограничением.

Это тоже эффективно; потому что есть только шанс 1-в-N, что вам нужно повторно перетасовать порядок x, вы должны увидеть только одну перестановку в среднем во время полного запуска алгоритма. Весь алгоритм остается в пределах O (N * M) границ, поэтому он идеально подходит для чего-то, производящего N раз M элементов вывода. Поскольку мы ограничиваем перестановку максимум N раз, прежде чем вернуться к простому обратному пути, мы избегаем (крайне маловероятной) возможности бесконечной перестановки.

Единственным недостатком тогда является то, что он должен создать N копий значений M y спереди.

Ответ 7

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

import itertools
import random

x = range(5)  # this is a list in Python 2
y = range(5)
all_pairs = list(itertools.product(x, y))

s = list(all_pairs)  # make a working copy
while any(s[i][0] == s[i + 1][0] for i in range(len(s) - 1)):
    random.shuffle(s)
print s

Как отмечалось, для небольших значений x и y (особенно y!) это на самом деле достаточно быстрое решение. Ваш пример из 5 для каждого заканчивается в среднем времени "сразу". Пример колоды карт (4 и 13) может занять гораздо больше времени, потому что обычно требуется сотни тысяч перетасовки. (И снова, не гарантируется прекращение вообще.)

Ответ 8

Вот эволюционный алгоритм. Сначала он развивает список, в котором элементы X повторяются len(Y) раз, а затем он случайным образом заполняет каждый элемент Y len (X) раз. Полученные порядки кажутся довольно случайными:

import random

#the following fitness function measures
#the number of times in which
#consecutive elements in a list
#are equal

def numRepeats(x):
    n = len(x)
    if n < 2: return 0
    repeats = 0
    for i in range(n-1):
        if x[i] == x[i+1]: repeats += 1
    return repeats

def mutate(xs):
    #swaps random pairs of elements
    #returns a new list
    #one of the two indices is chosen so that
    #it is in a repeated pair
    #and swapped element is different

    n = len(xs)
    repeats = [i for i in range(n) if (i > 0 and xs[i] == xs[i-1]) or (i < n-1 and xs[i] == xs[i+1])]
    i = random.choice(repeats)
    j = random.randint(0,n-1)
    while xs[j] == xs[i]: j = random.randint(0,n-1)
    ys = xs[:]
    ys[i], ys[j] = ys[j], ys[i]
    return ys

def evolveShuffle(xs, popSize = 100, numGens = 100):
    #tries to evolve a shuffle of xs so that consecutive
    #elements are different
    #takes the best 10% of each generation and mutates each 9
    #times. Stops when a perfect solution is found
    #popsize assumed to be a multiple of 10

    population = []

    for i in range(popSize):
        deck = xs[:]
        random.shuffle(deck)
        fitness = numRepeats(deck)
        if fitness == 0: return deck
        population.append((fitness,deck))

    for i in range(numGens):
        population.sort(key = (lambda p: p[0]))
        newPop = []
        for i in range(popSize//10):
            fit,deck = population[i]
            newPop.append((fit,deck))
            for j in range(9):
                newDeck = mutate(deck)
                fitness = numRepeats(newDeck)
                if fitness == 0: return newDeck
                newPop.append((fitness,newDeck))
        population = newPop
    #if you get here :
    return [] #no special shuffle found

#the following function takes a list x
#with n distinct elements (n>1) and an integer k
#and returns a random list of length nk
#where consecutive elements are not the same

def specialShuffle(x,k):
    n = len(x)
    if n == 2:
        if random.random() < 0.5:
            a,b = x
        else:
            b,a = x
        return [a,b]*k
    else:
        deck = x*k
        return evolveShuffle(deck)

def randOrder(x,y):
    xs = specialShuffle(x,len(y))
    d = {}
    for i in x:
        ys = y[:]
        random.shuffle(ys)
        d[i] = iter(ys)

    pairs = []
    for i in xs:
        pairs.append((i,next(d[i])))
    return pairs

например:

>>> randOrder([1,2,3,4,5],[1,2,3,4,5])
[(1, 4), (3, 1), (4, 5), (2, 2), (4, 3), (5, 3), (2, 1), (3, 3), (1, 1), (5, 2), (1, 3), (2, 5), (1, 5), (3, 5), (5, 5), (4, 4), (2, 3), (3, 2), (5, 4), (2, 4), (4, 2), (1, 2), (5, 1), (4, 1), (3, 4)]

При увеличении len(X) и len(Y) это затрудняет поиск решения (и предназначено для возврата пустого списка в этом случае), и в этом случае параметры popSize и numGens могут быть увеличены. Как и в случае, он может быстро найти решения 20х20. Требуется около минуты, когда X и Y имеют размер 100, но даже тогда могут найти решение (в то время, когда я его запустил).

Ответ 9

Интересное ограничение! Я, вероятно, задумался над этим, решая более общую проблему: перетасовывание произвольного списка последовательностей, для которых (если возможно) никакие две соседние последовательности не разделяют первый элемент.

from itertools import product
from random import choice, randrange, shuffle

def combine(*sequences):
    return playlist(product(*sequences))

def playlist(sequence):
    r'''Shuffle a set of sequences, avoiding repeated first elements.
    '''#"""#'''
    result = list(sequence)
    length = len(result)
    if length < 2:
        # No rearrangement is possible.
        return result
    def swap(a, b):
        if a != b:
            result[a], result[b] = result[b], result[a]
    swap(0, randrange(length))
    for n in range(1, length):
        previous = result[n-1][0]
        choices = [x for x in range(n, length) if result[x][0] != previous]
        if not choices:
            # Trapped in a corner: Too many of the same item are left.
            # Backtrack as far as necessary to interleave other items.
            minor = 0
            major = length - n
            while n > 0:
                n -= 1
                if result[n][0] == previous:
                    major += 1
                else:
                    minor += 1
                if minor == major - 1:
                    if n == 0 or result[n-1][0] != previous:
                        break
            else:
                # The requirement can't be fulfilled,
                # because there are too many of a single item.
                shuffle(result)
                break

            # Interleave the majority item with the other items.
            major = [item for item in result[n:] if item[0] == previous]
            minor = [item for item in result[n:] if item[0] != previous]
            shuffle(major)
            shuffle(minor)
            result[n] = major.pop(0)
            n += 1
            while n < length:
                result[n] = minor.pop(0)
                n += 1
                result[n] = major.pop(0)
                n += 1
            break
        swap(n, choice(choices))
    return result

Это начинается просто, но когда он обнаруживает, что он не может найти элемент с другим первым элементом, он выясняет, как далеко назад ему нужно идти, чтобы чередовать этот элемент с чем-то другим. Поэтому основной цикл пересекает массив не более трех раз (один раз назад), но обычно один раз. Конечно, каждая итерация первого прямого прохода проверяет каждый оставшийся элемент в массиве, а сам массив содержит каждую пару, поэтому общее время выполнения O((NM)**2).

Для вашей конкретной проблемы:

>>> X = Y = [1, 2, 3, 4, 5]
>>> combine(X, Y)
[(3, 5), (1, 1), (4, 4), (1, 2), (3, 4),
 (2, 3), (5, 4), (1, 5), (2, 4), (5, 5),
 (4, 1), (2, 2), (1, 4), (4, 2), (5, 2),
 (2, 1), (3, 3), (2, 5), (3, 2), (1, 3),
 (4, 3), (5, 3), (4, 5), (5, 1), (3, 1)]

Кстати, это сравнивает значения x по равенству, а не по положению в массиве X, что может иметь значение, если массив может содержать дубликаты. Фактически, повторяющиеся значения могут инициировать резервный случай перетасовки всех пар вместе, если более половины значений X одинаковы.