DjangoBB LoFi version

Начало » Python для новичков » Алгоритм Фишера - Йейтса

Dispa

Окт. 2, 2022 21:20:17

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

 from random import randrange
def swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp
def split(s):
    return [char for char in s]
def shuffle(A):
    for i in range(len(A) - 1):
        j = randrange(i, len(A))
        swap(A, i, j)
if __name__ == '__main__':
    s = input()
    A = split(s)
    shuffle(A)
    print(A)

py.user.next

Окт. 2, 2022 23:44:33

wiki. алгоритм Фишера-Йетса

Dispa

  
def split(s):
    return [char for char in s]

Это делается вот так

  
list(s)

Dispa
нужет вывод удаления каждой буквы из списка типо:
п,р,и,в,е,т
рандобно взялась буква ‘в’ к примеру
п,р,и,е,т - в
потом буква ‘р’
п,и,е,т - в,р и так до полностью перетасованного списка

Возьми список, заполни его и удаляй из него по одному элементу, добавляя в другой список. Для этого используй методы list.pop(index) и list.append(item). Заодно сможешь выводить промежуточные результаты.

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

Dispa
так же нужен обратный алгоритм чтобы получить исходный текст

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

xam1816

Окт. 3, 2022 07:06:26

  
import random
#
def fisher_yates_shuffle(some_lst: list, logging=False):
	some_lst_enum = list(enumerate(some_lst))
	if logging:
		print(some_lst)
		print('==========')
	out = []
	indexes = []
	while some_lst_enum:
		i = random.randint(0, len(some_lst_enum) - 1)
		elem = some_lst_enum.pop(i)
		indexes.append(elem[0])
		out.append(elem[1])
		if logging:
			print(','.join(i for n, i in some_lst_enum), '-', ','.join(out))
			print('>')
	return out, indexes
#
def restore_lst(some_lst, key):
	out = [None] * len(some_lst)
	for n, i in zip(key, some_lst):
		out[n] = i
	return out
#
res = fisher_yates_shuffle(list('трактор'), logging=True)
print(res)
#
restore_res = restore_lst(*res)
print(restore_res)