Как создать список перестановок с ограничением на значения индекса?

Question

Мне нужно создать перестановку заданного списка с таким ограничением, чтобы

given input sequence=(x_0, x_1, x_2,..) and an integer k, the output sequence=(x_perm(0), x_perm(1), x_perm(2),..) with perm(i)< i+k. 

For example for k=2 that means;

   x_perm(0) is either x_0 or x_1

   x_perm(1) is either x_0, x_1 or x_2

Another example for input=[3,4,5] and k=2 is:

output=[4,3,5] is a valid permutation, but [5,4,3] is not since x_perm(0) cannot be x_2.

def spec_perm(iterable, k):
    import random
    perm=[0]*len(iterable)
    for i in range (0,len(iterable)):
        perm[i]=random.choice(iterable[0:k+i])
    return perm

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

В конце мне нужно получить все допустимые перестановки.

Answer 1

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

def spec_perm(iterable, k):
    import random
    perm=[0]*len(iterable)
    used_index = [] #Initiate the list of used indexes.
    for i in range (0,len(iterable)):
        #Declare the possible range.
        if i+k < len(iterable):
            index_range = list(range(0, i+k))
        else:
            index_range = list(range(0, len(iterable)))
        #Get rid of the used indexes by using a list comprehension. 
        possible_index = [idx for idx in index_range if idx not in used_index] 
        #Make your random index choice AND assign it to a variable 
        #so that you can append it to used_index list later.
        random_index = random.choice(possible_index) 
        perm[i]=iterable[random_index]
        #Update the used indexes by appending the random index choice to the list.
        used_index.append(random_index) 


    return perm

Надеюсь, это поможет. Колай Желсин:)

Answer 2

Я думаю, это то, что вас интересует. Python предоставляет прямые методы для поиска перестановок. Эти методы присутствуют в пакете itertools.

Импорт пакета itertools для реализации метода перестановок в python. Этот метод принимает список в качестве входных данных и возвращает список объектов кортежей.

# import itertools
from itertools import permutations 

# Get all permutations of ['a', 'b', 'c'] 
perm = permutations(['a', 'b', 'c']) 

# Print the obtained permutations 
for i in list(perm): 
    print i 

Допустим, вы хотите получить перестановки длины n (скажем, n = 2), тогда все, что вам нужно сделать, это

#change
perm = permutations(['a', 'b', 'c']) 

#to
perm = permutations(['a', 'b', 'c'],2)