Задача на нахождение лучшей перестановки

@Аня хукер · Регистрация: 06.06.2018

Author24 — интернет-сервис помощи студентам

Добрый день! помогите, пожалуйста, понять как в python можно для заданого числа получить все возможные варианты перестановок, при условии, что есть ограничение на количество перестановок. К примеру, есть число 4256 и к-во перестановок, что нужно сделать - 2. То есть желаемым результатом будет список вида: 2465, 5642, 6524 и тд...
Как это лучше всего сделать?

@eaa · 13.09.2021, 16:45

Python

from itertools import permutations
s = '4256'
for p in permutations(s):
    print(*p, sep='')

так?

@Аня хукер · 13.09.2021, 17:10 **[ТС]**

Спасибо, а как добавить условие на количество перестановок (то есть чтобы получить только те варианты, где числа переставлялись попарно N раз)? В этом коде ведь выводятся абсолютно все перестановки...

@Catstail · 13.09.2021, 17:15

Сообщение от Аня хукер

получить все возможные варианты перестановок

Сообщение от Аня хукер

при условии, что есть ограничение на количество перестановок.

- тебе не кажется, что одно немного противоречит другому?

eaa, Вы понимаете, что ей нужно?

Добавлено через 1 минуту

Сообщение от Аня хукер

К примеру, есть число 4256 и к-во перестановок, что нужно сделать - 2

из числа 4356 сделать -2?

@eaa · 13.09.2021, 17:21

Не по теме:

Catstail, неа)) не понимаю...

@Аня хукер · 13.09.2021, 17:44 **[ТС]**

Сообщение от Catstail

из числа 4356 сделать -2?

неее, вы меня совсем не поняли) количество перестановок - это то, сколько раз мы меняем местами пары символов.

Возьмем более наглядный пример: есть число 123 и после одной перестановки мы получим такие варианты: 213 (поменялась местами пара 1 и 2), 132 (аналогично, пара цифр "2 и 3" поменялись), 321. Применяя только одну перестановку - это все доступные варианты.

А, например, чтобы добиться числа 312, к первоначальному "123" нужно применить уже 2 перестановки - т.е. 123 -> 321 -> 312

Надеюсь теперь понятна суть.

И вот по такому принципу я хотела для 4256 сделать (при условии двух перестановок). То есть, чтобы в списке комбинаций были только те варианты, где сделано именно 2 перестановки (пример - 6524), а вариантов вида "4265" не было. (в условии самой задачи просят чтобы количество перестановок было строго равно N-ному числу)

@Gdez · 13.09.2021, 18:08

Аня хукер, символы строки перемещаются попарно строго один раз?
4256 -> 2456 (первая перестановка) -> 6452 (вторая) - такое допускается?

@Аня хукер · 13.09.2021, 18:26 **[ТС]**

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

Для того же 123, имея 2 перестановки, максимальным результатом есть 312. А для 4256 - 6524.
Если для 4256 задать 3 перестановки, то и максимальное число будет 6542.

@eaa · 13.09.2021, 18:42

мда... из пушки по воробьям...
эта задача решается по другому. сортировку проходите?

@Аня хукер · 13.09.2021, 19:12 **[ТС]**

А какой метод сортировки здесь подойдет, подскажите пожалуйста? Понимаю, что мой начальный план это скорее кощунство, но казалось неплохой идеей). На всякий случай прикреплю задание, может все совсем иначе, чем я думала

Задача на нахождение лучшей перестановки

@Gdez · 13.09.2021, 20:47

Аня хукер, попробуй:

Python

def perm(st):
    res = set()
    
    for elem in st:
        n = len(elem)
        
        for i in range(n-1):
            for j in range(i+1, n):
                
                tmp = list(elem)
                tmp[i], tmp[j] = tmp[j], tmp[i]
                res.add(''.join(tmp))
                
    return res
 
 
num = input()
k = int(input())
tmp = {num}
 
if k > 0:
    tmp = perm(tmp)
    if k > 1:
        tmp = perm(tmp)
        if k > 2:
            tmp = perm(tmp)
            if k%2 == 0:
                tmp = perm(tmp)
 
print(int(max(tmp, key=int)))

@Аня хукер · 13.09.2021, 21:03 **[ТС]**

Gdez, спасибо вам большое!)

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
		1
	Задача на нахождение лучшей перестановки 13.09.2021, 15:53. Показов 3439. Ответов 11 Метки нет (Все метки) Добрый день! помогите, пожалуйста, понять как в python можно для заданого числа получить все возможные варианты перестановок, при условии, что есть ограничение на количество перестановок. К примеру, есть число 4256 и к-во перестановок, что нужно сделать - 2. То есть желаемым результатом будет список вида: 2465, 5642, 6524 и тд... Как это лучше всего сделать? 0

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	13.09.2021, 17:10 [ТС]	3
	Спасибо, а как добавить условие на количество перестановок (то есть чтобы получить только те варианты, где числа переставлялись попарно N раз)? В этом коде ведь выводятся абсолютно все перестановки... 0

@Catstail Модератор 37303 / 20737 / 4272 Регистрация: 12.02.2012 Сообщений: 34,131 Записей в блоге: 14
	13.09.2021, 17:15	4
	Сообщение от Аня хукер получить все возможные варианты перестановок Сообщение от Аня хукер при условии, что есть ограничение на количество перестановок. - тебе не кажется, что одно немного противоречит другому? eaa, Вы понимаете, что ей нужно? Добавлено через 1 минуту Сообщение от Аня хукер К примеру, есть число 4256 и к-во перестановок, что нужно сделать - 2 из числа 4356 сделать -2? 0

@eaa
	13.09.2021, 17:21 #5
	Не по теме: Catstail, неа)) не понимаю... 0

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	13.09.2021, 17:44 [ТС]	6
	Сообщение от Catstail из числа 4356 сделать -2? неее, вы меня совсем не поняли) количество перестановок - это то, сколько раз мы меняем местами пары символов. Возьмем более наглядный пример: есть число 123 и после одной перестановки мы получим такие варианты: 213 (поменялась местами пара 1 и 2), 132 (аналогично, пара цифр "2 и 3" поменялись), 321. Применяя только одну перестановку - это все доступные варианты. А, например, чтобы добиться числа 312, к первоначальному "123" нужно применить уже 2 перестановки - т.е. 123 -> 321 -> 312 Надеюсь теперь понятна суть. И вот по такому принципу я хотела для 4256 сделать (при условии двух перестановок). То есть, чтобы в списке комбинаций были только те варианты, где сделано именно 2 перестановки (пример - 6524), а вариантов вида "4265" не было. (в условии самой задачи просят чтобы количество перестановок было строго равно N-ному числу) 0

@Gdez 8592 / 4418 / 1855 Регистрация: 27.03.2020 Сообщений: 7,251
	13.09.2021, 18:08	7
	Аня хукер, символы строки перемещаются попарно строго один раз? 4256 -> 2456 (первая перестановка) -> 6452 (вторая) - такое допускается? 0

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	13.09.2021, 18:26 [ТС]	8
	допускается, но конечный смысл всего этого заключается в том, чтобы получить наибольшее возможное число, проведя строго заданное количество перестановок. Просто я предположила что можно составить список вариаций, а из них уже выбрать максимальное число... Для того же 123, имея 2 перестановки, максимальным результатом есть 312. А для 4256 - 6524. Если для 4256 задать 3 перестановки, то и максимальное число будет 6542. 0

@eaa Status 418 4581 / 2348 / 602 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	13.09.2021, 18:42	9
	мда... из пушки по воробьям... эта задача решается по другому. сортировку проходите? 0

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	13.09.2021, 19:12 [ТС]	10
	А какой метод сортировки здесь подойдет, подскажите пожалуйста? Понимаю, что мой начальный план это скорее кощунство, но казалось неплохой идеей). На всякий случай прикреплю задание, может все совсем иначе, чем я думала 0

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	13.09.2021, 21:03 [ТС]	12
	Gdez, спасибо вам большое!) 0

Задача на нахождение лучшей перестановки

Решение