Управление расстоянием перетасовки

У меня попытался задать этот вопрос до, но он никогда не мог правильно это сформулировать. Надеюсь, на этот раз я прав:

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

Итак, например:

L = [1,2,3,4]
d = 2
answer = magicFunction(L, d)

Теперь одним возможным результатом может быть:

>>> print(answer)
[3,1,2,4]

Обратите внимание, что 3 переместило два индекса, 1 и 2 переместили один индекс, а 4 не переместился вообще. Таким образом, это действительное перетасовка, согласно моему предыдущему определению. Для подтверждения этого можно использовать следующий фрагмент кода:

old = {e:i for i,e in enumerate(L)}
new = {e:i for i,e in enumerate(answer)}
valid = all(abs(i-new[e])<=d for e,i in old.items())

Теперь я легко мог бы сгенерировать все возможные перестановки L, фильтр для действительных и выбрать один случайным образом. Но это не кажется очень изящным. Есть ли у кого-нибудь другие идеи о том, как это сделать?

Ответ 1

Это будет длительным и сухим.

У меня есть решение, которое дает равномерное распределение. Для предварительного вычисления требуется O(len(L) * d**d) время и пространство, затем выполняется тасование в O(len(L)*d) время ¹. Если равномерное распределение не требуется, предварительная компиляция не нужна, и время перетасовки может быть уменьшено до O(len(L)) из-за более быстрого случайного выбора; Я не реализовал неравномерное распределение. Оба этапа этого алгоритма значительно быстрее, чем грубая сила, но они все еще не так хороши, как хотелось бы. Кроме того, хотя концепция должна работать, я не тестировал свою реализацию так тщательно, как хотелось бы.

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

Всякий раз, когда отставание d, мы вынуждены помещать следующий элемент в первое незаполненное положение, даже если на расстоянии d могут быть другие пустые точки. Если мы это сделаем, отставание не может превысить d, мы всегда будем иметь место, чтобы поместить каждый элемент, и мы будем генерировать действительное перетасование списка. Таким образом, мы имеем общее представление о том, как создавать перетасовки; однако, если мы сделаем наш выбор равномерно случайным, общее распределение не будет равномерным. Например, при len(L) == 3 и d == 1 существует 3 возможных перетасовки (по одному для каждой позиции среднего элемента), но если мы выбираем положение первого элемента равномерно, одна тасовка становится в два раза более вероятной, чем любая из другие.

Если мы хотим равномерного распределения по допустимым перетасовкам, нам нужно сделать взвешенный случайный выбор для положения каждого элемента, где вес позиции основан на количестве возможных тасований, если мы выберем эту позицию. Сделанный наивно, это потребовало бы, чтобы мы генерировали все возможные перетасовки, чтобы считать их, что займет время O(d**len(L)). Однако количество возможных перетасовки, оставшихся после любого шага алгоритма, зависит только от того, какие пятна мы заполнили, а не в том порядке, в котором они были заполнены. Для любой картины заполненных или незаполненных пятен количество возможных тасований - это сумма количество возможных перетасовки для каждого возможного размещения следующего элемента. На любом этапе существует не более d возможных положений для размещения следующего элемента, и есть O(d**d) возможные шаблоны незаполненных пятен (так как любое пятно, превышающее d за текущим элементом, должно быть заполнено, а любое пятно d или еще впереди должно быть пустым). Мы можем использовать это для генерации цепочки Markov размером O(len(L) * d**d), принимая O(len(L) * d**d) время для этого, а затем используем эту цепочку Маркова для выполнения тасования в O(len(L)*d) времени.

Пример кода (в настоящее время не совсем O(len(L)*d) из-за неэффективного цепного представления Маркова):

import random

# states are (k, filled_spots) tuples, where k is the index of the next
# element to place, and filled_spots is a tuple of booleans
# of length 2*d, representing whether each index from k-d to
# k+d-1 has an element in it. We pretend indices outside the array are
# full, for ease of representation.

def _successors(n, d, state):
    '''Yield all legal next filled_spots and the move that takes you there.

    Doesn't handle k=n.'''
    k, filled_spots = state
    next_k = k+1

    # If k+d is a valid index, this represents the empty spot there.
    possible_next_spot = (False,) if k + d < n else (True,)

    if not filled_spots[0]:
        # Must use that position.
        yield k-d, filled_spots[1:] + possible_next_spot
    else:
        # Can fill any empty spot within a distance d.
        shifted_filled_spots = list(filled_spots[1:] + possible_next_spot)
        for i, filled in enumerate(shifted_filled_spots):
            if not filled:
                successor_state = shifted_filled_spots[:]
                successor_state[i] = True
                yield next_k-d+i, tuple(successor_state)
                # next_k instead of k in that index computation, because
                # i is indexing relative to shifted_filled_spots instead
                # of filled_spots


def _markov_chain(n, d):
    '''Precompute a table of weights for generating shuffles.

    _markov_chain(n, d) produces a table that can be fed to
    _distance_limited_shuffle to permute lists of length n in such a way that
    no list element moves a distance of more than d from its initial spot,
    and all permutations satisfying this condition are equally likely.

    This is expensive.

    '''

    if d >= n - 1:
        # We don't need the table, and generating a table for d >= n
        # complicates the indexing a bit. It too complicated already.
        return None

    table = {}
    termination_state = (n, (d*2 * (True,)))
    table[termination_state] = 1

    def possible_shuffles(state):
        try:
            return table[state]
        except KeyError:
            k, _ = state
            count = table[state] = sum(
                    possible_shuffles((k+1, next_filled_spots))
                    for (_, next_filled_spots) in _successors(n, d, state)
            )
            return count

    initial_state = (0, (d*(True,) + d*(False,)))
    possible_shuffles(initial_state)
    return table

def _distance_limited_shuffle(l, d, table):
    # Generate an index into the set of all permutations, then use the
    # markov chain to efficiently find which permutation we picked.

    n = len(l)

    if d >= n - 1:
        random.shuffle(l)
        return

    permutation = [None]*n
    state = (0, (d*(True,) + d*(False,)))
    permutations_to_skip = random.randrange(table[state])

    for i, item in enumerate(l):
        for placement_index, new_filled_spots in _successors(n, d, state):
            new_state = (i+1, new_filled_spots)
            if table[new_state] <= permutations_to_skip:
                permutations_to_skip -= table[new_state]
            else:
                state = new_state
                permutation[placement_index] = item
                break
    return permutation

class Shuffler(object):
    def __init__(self, n, d):
        self.n = n
        self.d = d
        self.table = _markov_chain(n, d)
    def shuffled(self, l):
        if len(l) != self.n:
            raise ValueError('Wrong input size')
        return _distance_limited_shuffle(l, self.d, self.table)
    __call__ = shuffled

¹ Мы могли бы использовать алгоритм взвешенного случайного выбора на основе дерева, чтобы улучшить время перетасовки до O(len(L)*log(d)), но так как таблица становится настолько огромной для даже умеренно больших d, это не означает, Кажется целесообразным. Кроме того, коэффициенты d**d в границах завышены, но фактические факторы по-прежнему по крайней мере экспоненциальны в d.

Ответ 2

Это очень трудная проблема, но оказывается, что в научной литературе есть решение в влиятельной статье Марка Жерума, Алистера Синклера и Эрика Вигоды, Алгоритм приближения многочленовременного времени для константы матрицы с неотрицательными записями, журнал ACM, Vol. 51, № 4, июль 2004 г., стр. 671-697. http://www.cc.gatech.edu/~vigoda/Permanent.pdf.

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

Теперь подключите node слева к node справа, если сопоставление от числа слева от позиции справа разрешено ограничениями на месте. Так, если d = 1, то 1 слева соединяется с 1 и 2 справа, 2 слева соединяется с 1, 2, 3 справа, 3 слева соединяется с 2, 3, 4 справа и 4 слева подключается к 3, 4 справа.

Полученный граф двудольный. Допустимая перестановка соответствует идеальному совпадению в двудольном графе. Идеальное соответствие, если оно существует, можно найти в O (VE) времени (или несколько лучше, для более сложных алгоритмов).

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

Что это связано с перманентами? Рассмотрим матричное представление нашего двудольного графа, где 1 означает ребро, а 0 означает отсутствие ребра:

permanent матрицы, как определитель, кроме отрицательных знаков в определении. Поэтому мы берем ровно один элемент из каждой строки и столбца, умножаем их вместе и складываем по всем вариантам строки и столбца. Термины перманента соответствуют перестановкам; член равен 0, если любой коэффициент равен 0, другими словами, если перестановка недопустима в соответствии с представлением матрицы/двудольного графа; этот термин равен 1, если все факторы равны 1, другими словами, если перестановка действительна в соответствии с ограничениями. Таким образом, постоянная матрицы учитывает все перестановки, удовлетворяющие ограничению, представленному матричным/двудольным графом.

Оказывается, что в отличие от расчетных детерминант, которые могут быть выполнены в O (n ^ 3), вычисление перманентов # P-complete поэтому найти точный ответ вообще не представляется возможным. Однако, если мы можем оценить количество допустимых перестановок, мы можем оценить постоянное. Jerrum et. и др. подошел к вопросу о подсчете допустимых перестановок, порождая допустимые перестановки равномерно (в пределах определенной ошибки, которую можно контролировать); оценка значения константы может быть получена достаточно сложной процедурой (раздел 5 упомянутой статьи), но нам не нужно, чтобы ответить на вопрос.

Время работы алгоритма Jerrum для вычисления константы равно O (n ^ 11) (игнорируя логарифмические факторы). Я не могу сразу сказать из статьи время работы части алгоритма, которая равномерно генерирует двудольные соответствия, но, по-видимому, она выше O (n ^ 9). Однако другая бумага уменьшает время работы для постоянного до O (n ^ 7): http://www.cc.gatech.edu/fac/vigoda/FasterPermanent_SODA.pdf; в этой статье они утверждают, что теперь можно получить хорошую оценку константы матрицы 100 × 100 0-1. Таким образом, должно быть возможно (почти) равномерно создавать ограниченные перестановки для списков из 100 элементов.

Там могут быть дополнительные улучшения, но я устал смотреть.

Если вы хотите реализовать, я начну с версии O (n ^ 11) в документе Jerrum, а затем взглянем на улучшения, если исходный алгоритм не достаточно быстр.

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

Ответ 3

Короче говоря, список, который нужно перетасовать, упорядочивается по сумме индекса и случайного числа.

import random
xs = range(20) # list that should be shuffled
d = 5          # distance
[x for i,x in sorted(enumerate(xs), key= lambda (i,x): i+(d+1)*random.random())]

Из:

[1, 4, 3, 0, 2, 6, 7, 5, 8, 9, 10, 11, 12, 14, 13, 15, 19, 16, 18, 17]

В основном это. Но это выглядит немного подавляющим, поэтому...

Алгоритм более подробно

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

import random
sorted(range(10), key = lambda x: random.random())

Из:

[2, 6, 5, 0, 9, 1, 3, 8, 7, 4]

Чтобы ограничить расстояние, мы должны реализовать альтернативную функцию ключа сортировки, которая зависит от индекса элемента. За это отвечает функция sort_criterion.

import random

def exclusive_uniform(a, b):
    "returns a random value in the interval  [a, b)"
    return a+(b-a)*random.random()

def distance_constrained_shuffle(sequence, distance,
                                 randmoveforward = exclusive_uniform):
    def sort_criterion(enumerate_tuple):
        """
        returns the index plus a random offset,
        such that the result can overtake at most 'distance' elements
        """
        indx, value = enumerate_tuple
        return indx + randmoveforward(0, distance+1)

    # get enumerated, shuffled list
    enumerated_result = sorted(enumerate(sequence), key = sort_criterion)
    # remove enumeration
    result = [x for i, x in enumerated_result]
    return result

С аргументом randmoveforward вы можете передать генератор случайных чисел с другой функцией плотности вероятности (pdf), чтобы изменить распределение расстояний.

Остальное - это тестирование и оценка распределения расстояний.

Функция тестирования

Вот реализация тестовой функции. Функция validate фактически взята из OP, но я удалил создание одного из словарей по причинам производительности.

def test(num_cases = 10, distance = 3, sequence = range(1000)):
    def validate(d, lst, answer):
        #old = {e:i for i,e in enumerate(lst)}
        new = {e:i for i,e in enumerate(answer)}
        return all(abs(i-new[e])<=d for i,e in enumerate(lst))
        #return all(abs(i-new[e])<=d for e,i in old.iteritems())


    for _ in range(num_cases):
        result = distance_constrained_shuffle(sequence, distance)
        if not validate(distance, sequence, result):
            print "Constraint violated. ", result
            break
    else:
        print "No constraint violations"


test()

Из:

No constraint violations

Распределение расстояний

Я не уверен, есть ли способ сделать равномерное распределение расстоянием, но вот функция для проверки распределения.

def distance_distribution(maxdistance = 3, sequence = range(3000)):
    from collections import Counter

    def count_distances(lst, answer):
        new = {e:i for i,e in enumerate(answer)}
        return Counter(i-new[e] for i,e in enumerate(lst))    

    answer = distance_constrained_shuffle(sequence, maxdistance)
    counter = count_distances(sequence, answer)

    sequence_length = float(len(sequence))

    distances = range(-maxdistance, maxdistance+1)
    return distances, [counter[d]/sequence_length for d in distances]

distance_distribution()

Из:

([-3, -2, -1, 0, 1, 2, 3],
 [0.01,
  0.076,
  0.22166666666666668,
  0.379,
  0.22933333333333333,
  0.07766666666666666,
  0.006333333333333333])

Или для случая с большим максимальным расстоянием:

distance_distribution(maxdistance=9, sequence=range(100*1000))

Ответ 4

Я не уверен, насколько это хорошо, но может быть что-то вроде:

создать список той же длины, что и исходный список L; каждый элемент этого списка должен быть приведен в список индексов разрешенных начальных индексов; например [[0,1,2],[0,1,2,3],[0,1,2,3],[1,2,3]], если я правильно понимаю ваш пример;
возьмите самый маленький подсписок (или любой из самых маленьких подсписков, если несколько списков имеют одинаковую длину);
выберите в нем случайный элемент с random.choice, этот элемент является индексом элемента в исходном списке, который будет отображен в текущее местоположение (используйте другой список для создания нового списка);
удалить случайно выбранный элемент из всех подписок

Например:

L = [ "A", "B", "C", "D" ]
i = [[0,1,2],[0,1,2,3],[0,1,2,3],[1,2,3]]
# I take [0,1,2] and pick randomly 1 inside
# I remove the value '1' from all sublists and since
# the first sublist has already been handled I set it to None
# (and my result will look as [ "B", None, None, None ]
i = [None,[0,2,3],[0,2,3],[2,3]]
# I take the last sublist and pick randomly 3 inside
# result will be ["B", None, None, "D" ]
i = [None,[0,2], [0,2], None]
etc.

Я еще не пробовал. С наилучшими пожеланиями.

Ответ 5

Вот два эскиза в Python; одна своп-база, другая не-swap-based. Во-первых, идея состоит в том, чтобы отслеживать, куда переместились индексы, и проверить, будет ли следующий своп действительным. Добавлена дополнительная переменная для количества свопов.

from random import randint

def swap(a,b,L):
  L[a], L[b] = L[b], L[a]

def magicFunction(L,d,numSwaps):
  n = len(L)
  new = list(range(0,n))
  for i in xrange(0,numSwaps):
    x = randint(0,n-1)
    y = randint(max(0,x - d),min(n - 1,x + d))
    while abs(new[x] - y) > d or abs(new[y] - x) > d:
      y = randint(max(0,x - d),min(n - 1,x + d))
    swap(x,y,new)
    swap(x,y,L)
  return L

print(magicFunction([1,2,3,4],2,3)) # [2, 1, 4, 3]
print(magicFunction([1,2,3,4,5,6,7,8,9],2,4)) # [2, 3, 1, 5, 4, 6, 8, 7, 9]

Используя print(collections.Counter(tuple(magicFunction([0, 1, 2], 1, 1)) for i in xrange(1000))), мы обнаруживаем, что перестановка тождеств становится тяжелой с этим кодом (причина, по которой это остается для упражнения для читателя).

В качестве альтернативы мы можем думать об этом как поиск матрицы перестановок с интервальными ограничениями, где abs(i - j) <= d where M(i,j) would equal 1. Мы можем построить одноразовый случайный путь, выбрав случайную j для каждой строки из доступных. x в следующем примере представляют собой ячейки матрицы, которые лишат права решения (северо-западная юго-восточная диагональ будет представлять собой перестановку идентичности), restrictions представляет, сколько i все еще доступно для каждого j. (Адаптировано из моей предыдущей версии, чтобы выбрать как следующий i, так и следующий j случайным образом, вдохновленный ответом user2357112):

n = 5, d = 2

Start:

0 0 0 x x
0 0 0 0 x
0 0 0 0 0
x 0 0 0 0
x x 0 0 0

restrictions = [3,4,5,4,3]  # how many i are still available for each j

1.

0 0 1 x x  # random choice
0 0 0 0 x
0 0 0 0 0
x 0 0 0 0
x x 0 0 0

restrictions = [2,3,0,4,3] # update restrictions in the neighborhood of (i ± d)

2.

0 0 1 x x 
0 0 0 0 x  
0 0 0 0 0
x 0 0 0 0
x x 0 1 0  # random choice

restrictions = [2,3,0,0,2] # update restrictions in the neighborhood of (i ± d)

3.

0 0 1 x x
0 0 0 0 x
0 1 0 0 0  # random choice
x 0 0 0 0
x x 0 1 0

restrictions = [1,0,0,0,2] # update restrictions in the neighborhood of (i ± d)

only one choice for j = 0 so it must be chosen

4.

0 0 1 x x  
1 0 0 0 x  # dictated choice
0 1 0 0 0
x 0 0 0 0
x x 0 1 0

restrictions = [0,0,0,0,2] # update restrictions in the neighborhood of (i ± d)

Solution:

0 0 1 x x
1 0 0 0 x
0 1 0 0 0
x 0 0 0 1  # dictated choice
x x 0 1 0

[2,0,1,4,3]

Код Python (адаптированный из моей предыдущей версии, чтобы выбрать как следующий i, так и следующий j случайным образом, на основе ответа user2357112):

from random import randint,choice
import collections

def magicFunction(L,d):
  n = len(L)
  restrictions = [None] * n
  restrict = -1
  solution = [None] * n
  for i in xrange(0,n):
    restrictions[i] = abs(max(0,i - d) - min(n - 1,i + d)) + 1
  while True:
    availableIs = filter(lambda x: solution[x] == None,[i for i in xrange(n)]) if restrict == -1 else filter(lambda x: solution[x] == None,[j for j in xrange(max(0,restrict - d),min(n,restrict + d + 1))])
    if not availableIs:
      L = [L[i] for i in solution]
      return L
    i = choice(availableIs)
    availableJs = filter(lambda x: restrictions[x] <> 0,[j for j in xrange(max(0,i - d),min(n,i + d + 1))])
    nextJ = restrict if restrict != -1 else choice(availableJs)
    restrict = -1
    solution[i] = nextJ
    restrictions[ nextJ ] = 0
    for j in xrange(max(0,i - d),min(n,i + d + 1)):
      if j == nextJ or restrictions[j] == 0:
        continue
      restrictions[j] = restrictions[j] - 1
      if restrictions[j] == 1:
        restrict = j

print(collections.Counter(tuple(magicFunction([0, 1, 2], 1)) for i in xrange(1000)))

Используя print(collections.Counter(tuple(magicFunction([0, 1, 2], 1)) for i in xrange(1000))), мы обнаруживаем, что подстановка этого символа становится понятной с помощью этого кода (почему это остается для упражнения для читателя).

Ответ 6

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

Мы можем генерировать перестановки, которые быстро перемещаются на 1 шаг быстрее с помощью следующей рекурсивной процедуры: рассмотрим перестановку {1,2,3,..., n}. Последний элемент n может перемещаться либо на 0, либо на 1 место. Если он перемещает 0 мест, n фиксируется, и мы сведем задачу к созданию перестановки {1,2,..., n-1}, в которой каждый элемент перемещается не более чем на одно место.

С другой стороны, если n перемещает 1 место, оно должно занимать позицию n-1. Тогда n-1 должно занимать позицию n (если любое меньшее число занимает позицию n, оно будет перемещено более чем на 1 место). Другими словами, мы должны иметь своп n и n-1, а после замены мы сведем проблему к нахождению такой перестановки остальной части массива {1,..., n-2}.

Такие перестановки можно построить в O (n) времени, очевидно.

Эти два варианта следует выбирать с взвешенными вероятностями. Поскольку я не знаю веса (хотя у меня есть теория, см. Ниже), возможно, выбор должен быть 50-50... но см. Ниже.

Более точная оценка весов может быть следующей: обратите внимание, что число таких перестановок следует за рекурсией, которая совпадает с последовательностью Фибоначчи: f (n) = f (n-1) + f (n- 2). Имеем f (1) = 1 и f (2) = 2 ({1,2} переходит в {1,2} или {2,1}), поэтому числа действительно являются числами Фибоначчи. Поэтому я предполагаю, что вероятность выбора n фиксированного vs-подкачки n и n-1 будет f (n-1)/f (n) против f (n-2)/f (n). Так как отношение последовательных чисел Фибоначчи быстро приближается к Золотому Соотношение, разумное приближение к вероятностям состоит в том, чтобы оставить n фиксированным 61% времени и заменить n и n-1 39% времени.

Чтобы построить перестановки, когда элементы перемещаются в большинстве мест d, мы просто повторяем процесс d раз. Время работы: O (nd).

Вот схема алгоритма.

arr = {1,2,...,n};
for (i = 0; i < d; i++) {
  j = n-1;
  while (j > 0) {
    u = random uniform in interval (0,1)
    if (u < 0.61) { // related to golden ratio phi; more decimals may help
      j -= 1;
    } else {
      swap items at positions j and j-1 of arr // 0-based indexing
      j -= 2;
    }
  }
}

Поскольку каждый проход перемещает элементы не более 1-го места с самого начала, d-pass перемещает предметы не более d-мест. Единственный вопрос - это равномерное распределение перестановок. Вероятно, это было бы длинным доказательством, если бы оно было правдой, поэтому я предлагаю собрать эмпирические доказательства для разных n и d's. Вероятно, чтобы доказать утверждение, нам пришлось бы перейти от использования приближения золотого отношения к f (n-1)/f (n-2) вместо 0,61.

Там может быть даже какая-то странная причина, почему некоторые перестановки могут быть пропущены этой процедурой, но я уверен, что этого не произойдет. Однако на всякий случай было бы полезно иметь полную инвентаризацию таких перестановок для некоторых значений n и d, чтобы проверить правильность предложенного нами алгоритма.

Обновление

Я обнаружил ошибку "один за другим" в моем "псевдокоде", и я исправил ее. Затем я реализовал на Java, чтобы понять смысл распространения. Код ниже. Распределение далеко не единообразно, я думаю, потому что есть много способов получить ограниченные перестановки с короткими максимальными расстояниями (двигаться вперед, двигаться назад или двигаться назад, двигаться вперед, например), но несколько способов получить большие расстояния (двигаться вперед, двигаться вперед). Я не могу придумать способ решения проблемы однородности с помощью этого метода.

import java.util.Random;
import java.util.Map;
import java.util.TreeMap;

class RestrictedPermutations {
  private static Random rng = new Random();

  public static void rPermute(Integer[] a, int d) {
    for (int i = 0; i < d; i++) {
      int j = a.length-1;
      while (j > 0) {
        double u = rng.nextDouble();
        if (u < 0.61) { // related to golden ratio phi; more decimals may help
          j -= 1;
        } else {
          int t = a[j];
          a[j] = a[j-1];
          a[j-1] = t;
          j -= 2;
        }
      }
    }
  }

  public static void main(String[] args) {
    int numTests = Integer.parseInt(args[0]);
    int d = 2;
    Map<String,Integer> count = new TreeMap<String,Integer>();
    for (int t = 0; t < numTests; t++) {
      Integer[] a = {1,2,3,4,5};
      rPermute(a,d);
      // convert a to String for storage in Map
      String s = "(";
      for (int i = 0; i < a.length-1; i++) {
        s += a[i] + ",";
      }
      s += a[a.length-1] + ")";
      int c = count.containsKey(s) ? count.get(s) : 0;
      count.put(s,c+1);
    }
    for (String k : count.keySet()) {
      System.out.println(k + ": " + count.get(k));
    }
  }

}

Ответ 7

Здесь приведена адаптация кода @גלעד ברקן, который принимает только один проход по списку (в случайном порядке) и свопирует только один раз (используя случайный выбор возможных позиций):

from random import choice, shuffle

def magicFunction(L, d):
  n = len(L)
  swapped = [0] * n     # 0: position not swapped, 1: position was swapped
  positions = list(xrange(0,n))         # list of positions: 0..n-1
  shuffle(positions)                    # randomize positions
  for x in positions:
    if swapped[x]:      # only swap an item once
      continue
    # find all possible positions to swap
    possible = [i for i in xrange(max(0, x - d), min(n, x + d)) if not swapped[i]]
    if not possible:
      continue
    y = choice(possible)        # choose another possible position at random
    if x != y:
      L[y], L[x] = L[x], L[y]   # swap with that position
      swapped[x] = swapped[y] = 1       # mark both positions as swapped
  return L

Вот уточнение вышеприведенного кода, который просто находит все возможные смежные позиции и выбирает один:

from random import choice

def magicFunction(L, d):
  n = len(L)
  positions = list(xrange(0, n))        # list of positions: 0..n-1
  for x in xrange(0, n):
    # find all possible positions to swap
    possible = [i for i in xrange(max(0, x - d), min(n, x + d)) if abs(positions[i] - x) <= d]
    if not possible:
      continue
    y = choice(possible)        # choose another possible position at random
    if x != y:
      L[y], L[x] = L[x], L[y]   # swap with that position
      positions[x] = y
      positions[y] = x
  return L