Создайте последовательность из двух элементов, удовлетворяющих определенным критериям расстояния

Question

Учитывая последовательность отдельных элементов Sa, мы хотим создать последовательность Sb (составленную из тех же элементов в Sa, но в другом порядке), такую, что последовательность S = Sa + Sb (последовательность Sb добавляется сразу после последовательности Sa) удовлетворяет следующим свойствам:

• Расстояние (количество позиций) между двумя вхождениями элемента I в S составляет по меньшей мере некоторое число T для всех элементов I.
• Если элементыЯ и J находятся в пределах N позиций в Sa, тогда я и J не находятся в N позициях в Sb.

Мне удалось довольно просто запрограммировать первое условие в Python.Тем не менее, второй, где я борюсь.По сути, я просто хочу эти две вещи:

• Я хочу, чтобы во второй последовательности ее элементы находились «достаточно далеко» от их появления в первой последовательности.
• Я надеваюне хочу, чтобы соседи первой последовательности также были соседями во второй последовательности (причем N относится к расстоянию, на котором элементы считаются соседями).

Вот что у меня так далеко:

import random

clips = list(range(10)) # arbitrary items
choice_pool = clips[:]
Sa = clips[:]
random.shuffle(Sa)
Sb = []
count = len(Sa)

threshold = 0.5*len(clips) # the minimum distance the item has to be away from itself in the concatenated sequence
while len(Sb) != len(Sa):
    jj = random.randint(0, len(choice_pool) - 1)
    # we want clip a1 to be at least threshold away from clip b1
    if count - Sa.index(choice_pool[jj]) >= threshold:
        Sb.append(choice_pool[jj])
        del choice_pool[jj]
        count += 1

print("Sa:", Sa)
print("Sb:", Sb)
print("S :", Sa + Sb)

Есть ли у вас какие-либо советы о том, как также выполнить второе условие, при этом всегда гарантируя, что такая последовательность существует (не заканчиваясь в бесконечном цикле)?Благодаря.

Answer 1

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

import itertools as it

def filter_criteria(sequence):
    #put your filters here return True if you find a sequence that works
    pass 

for sb_try in it.permutations(sa, len(sa)):
   if filter_criteria(sa+sb_try):
       return sb_try

return "no permutation matches"