Ответ 1
Повторите попытку.
Несколько наблюдений.
- Первое значение всегда будет равно нулю в отсортированном массиве ваших кортежей.
- Длина массива всегда будет до тех пор, пока количество кортежей, существующих в вашем массиве.
- Вы хотите, чтобы они генерировались случайным образом.
- Кортежи производятся в порядке сортировки.
Основываясь на этих спецификациях, мы можем придумать процедурный метод;
- Сгенерируйте 2 списка последовательных целых чисел, один из которых выбирается, а другой - для семени.
- Для каждого номера в списке семян
[0, 1, 2, 3], произвольно добавьте и удалите номер, который еще не находится в элементе.[01, 13, 20, 32] - Создайте еще один список последовательных целых чисел и повторите.
[012, 130, 203, 321]
Но это не работает. Для некоторых итераций он вернется в угол и не сможет генерировать число. Например, [01, 13, 20, 32].. appending [3, 0, 1... crap, I'm stuck.
Единственный способ исправить это - сделать истинную перетасовку по всей строке и перетасовать до тех пор, пока не пригодится. Это может занять довольно много времени и будет только более болезненным, поскольку наборы будут больше.
Итак, процедурно говоря:
Решение 1: Случайное поколение
- Заполните список своим диапазоном. [0, 1, 2, 3]
- Создайте еще один список. [0, 1, 2, 3]
- Перемешать список. [1, 0, 2, 3]
- Перемешать, пока не найдете тот, который подходит... [1, 2, 3, 0]
- Повторите с третьим элементом.
С помощью этой процедуры, хотя компьютер может быстро проверять решения, он не может быстро генерировать решения. Однако это всего лишь один из двух способов генерации действительно случайного ответа.
Поэтому самый быстрый гарантированный метод будет использовать использование процедуры проверки, а не процедуру генерации. Прежде всего, сгенерируйте все возможные перестановки.
from itertools import permutations
n = 4
candidates = [i for i in permutations(xrange(n),3)]
Тогда.
Решение 2: Случайная проверка
- Выберите триплет, начинающийся с 0.
- Поп, случайно, триплет, который не начинается с 0.
- Проверьте, является ли случайно выбранный триплет промежуточным решением.
- Если нет, добавьте еще один триплет.
- Если да, добавьте триплет и REPOPULATE TRIPLET QUEUE.
- Повторите n раз. # или пока вы не исчерпаете очередь, после чего повторите n раз, естественно, станет TRUE
Решение для следующего триплета математически гарантировано находится в наборе решений, поэтому, если вы просто позволяете ему исчерпать себя, должно появиться рандомизированное решение. Проблема с этим подходом заключается в том, что нет никакой гарантии, что каждый возможный результат имеет равную вероятность.
Решение 3: Итеративная проверка
Для результатов с равной вероятностью избавитесь от рандомизации и сгенерируйте каждую возможную комбинацию из трех кортежей, n-списки long - и проверьте каждый из этих кандидатов.
Напишите функцию для проверки над списком потенциальных решений для создания каждого решения, а затем случайным образом вытащите решение из этого списка.
from itertools import combinations
results = [verify(i) for i in combinations(candidates, n)]
# this is 10626 calls to verify for n=4, 5 million for n=5
# this is not an acceptable solution.
Ни одно решение 1 или 3 не очень быстро, O (n ** 2), но, учитывая ваши критерии, возможно, это будет так же быстро, как это получится, если вы хотите действительно случайное решение. Решение 2 будет гарантировано быть самым быстрым из этих трех, часто раз превышая 1 или 3, решение 3 имеет наиболее стабильные результаты. Какой из этих подходов вы выберете, будет зависеть от того, что вы хотите делать с выходом.
После:
В конечном счете скорость кода будет зависеть от того, насколько случайным вы хотите, чтобы ваш код был. Алгоритм для выдачи ОЧЕНЬ первого (и только самого первого) экземпляра серии кортежей, который удовлетворяет вашим требованиям, может работать в высшей степени быстро, поскольку он просто атакует перестановки по порядку один раз и будет работать в O (n) времени, Тем не менее, он ничего не сделает случайно...
Кроме того, здесь можно найти быстрый код для проверки (i). Это основано на наблюдении, что два кортежа могут не иметь одинакового числа в одном и том же индексе.
def verify(t):
""" Verifies that a set of tuples satisfies the combinations without duplicates condition. """
zipt = zip(*t)
return all([len(i) == len(set(i)) for i in zipt])
n = 4 Полный набор решений
((0, 1, 2), (1, 0, 3), (2, 3, 0), (3, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 1), (3, 2, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1))
((0, 1, 2), (1, 3, 0), (2, 0, 3), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 0), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 1), (3, 2, 0))
((0, 1, 3), (1, 2, 0), (2, 3, 1), (3, 0, 2))
((0, 1, 3), (1, 3, 2), (2, 0, 1), (3, 2, 0))
((0, 2, 1), (1, 0, 3), (2, 3, 0), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 0, 3), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 1, 3), (3, 0, 2))
((0, 2, 1), (1, 3, 2), (2, 0, 3), (3, 1, 0))
((0, 2, 3), (1, 0, 2), (2, 3, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 0), (2, 0, 1), (3, 1, 2))
((0, 2, 3), (1, 3, 2), (2, 0, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 2), (2, 1, 0), (3, 0, 1))
((0, 3, 1), (1, 0, 2), (2, 1, 3), (3, 2, 0))
((0, 3, 1), (1, 2, 0), (2, 0, 3), (3, 1, 2))
((0, 3, 1), (1, 2, 0), (2, 1, 3), (3, 0, 2))
((0, 3, 1), (1, 2, 3), (2, 1, 0), (3, 0, 2))
((0, 3, 2), (1, 0, 3), (2, 1, 0), (3, 2, 1))
((0, 3, 2), (1, 2, 0), (2, 1, 3), (3, 0, 1))
((0, 3, 2), (1, 2, 3), (2, 0, 1), (3, 1, 0))
((0, 3, 2), (1, 2, 3), (2, 1, 0), (3, 0, 1))
n = 5 имеет 552 уникальных решения. Вот первые 20.
((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 0), (4, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 1), (4, 2, 0))
((0, 1, 2), (1, 0, 3), (2, 4, 0), (3, 2, 4), (4, 3, 1))
((0, 1, 2), (1, 0, 3), (2, 4, 1), (3, 2, 4), (4, 3, 0))
((0, 1, 2), (1, 0, 4), (2, 3, 0), (3, 4, 1), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 3, 1), (3, 4, 0), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 0), (4, 3, 1))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 0), (2, 3, 4), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 0), (2, 4, 3), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 0), (4, 0, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 0), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 1), (3, 0, 4), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 3, 0), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 3, 1), (3, 4, 0), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 4, 3), (3, 0, 1), (4, 3, 0))
Итак, вы можете создавать такие решения, но это требует времени. Если вы собираетесь использовать это, я буду кэшировать созданные решения, как есть, а затем случайным образом извлекать из них, когда вам это нужно, для любого числа n. Кстати, n = 5 потребовалось немного меньше минуты, чтобы закончить грубую силу. Поскольку решение O (n ** 2), я ожидаю, что n = 6 займет более часа, n = 7 в течение дня. Единственный способ вернуть истинное рандомизированное решение - это сделать так.
Отредактировано: Случайное решение без равного распределения:
Ниже приведен код, который я написал в попытке решить эту проблему, реализацию Решение 2. Я решил, что я опубликую его, поскольку это частичное, равноценное решение распределения и генерирует все возможные решения, гарантированные, учитывая достаточное время.
def seeder(n):
""" Randomly generates the first element in a solution. """
seed = [0]
a = range(1, n)
for i in range(1, 3):
seed.append(a.pop(random.randint(0,len(a)-1)))
return [seed]
def extend_seed(seed, n):
""" Semi-Randomly generates the next element in a solution. """
next_seed = [seed[-1][0] + 1]
candidates = range(0, n)
for i in range(1, 3):
c = candidates[:]
for s in next_seed:
c.remove(s)
for s in seed:
try:
c.remove(s[i])
except ValueError:
pass
next_seed.append(c.pop(random.randint(0,len(c)-1)))
seed.append(next_seed)
return seed
def combo(n):
""" Extends seed until exhausted.
Some random generations return results shorter than n. """
seed = seeder(n)
while True:
try:
extend_seed(seed, n)
except (ValueError, IndexError):
return seed
def combos(n):
""" Ensures that the final return is of length n. """
while True:
result = combo(n)
if len(result) == n:
return result