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

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

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

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

@eaa · 13.09.2021, 16:45

Python    
        
    Скопировано
1
2
3
4
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    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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, спасибо вам большое!)

Новые блоги и статьи Все статьи Все блоги /
Обмен данными в микросервисной архитектуре ArchitectMsa 06.04.2025 Когда разработчики начинают погружаться в мир микросервисов, они часто сталкиваются с парадоксальным правилом: "два сервиса не должны делить один источник данных". Эта мантра звучит повсюду в. . .	PostgreSQL в Kubernetes: Автоматизация обслуживания с CNPG Mr. Docker 06.04.2025 Администраторы баз данных сталкиваются с целым рядом проблем при обслуживании PostgreSQL в Kubernetes: как обеспечить правильную репликацию данных, как настроить автоматическое переключение при. . .	Async/await в TypeScript run.dev 06.04.2025 Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .	Многопоточность в C#: Синхронизация потоков UnmanagedCoder 06.04.2025 Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .	TypeScript: Классы и конструкторы run.dev 06.04.2025 TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .
Многопоточное программирование: Rust против C++ golander 06.04.2025 C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .	std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .	Реляционная модель и правила Кодда: фундамент современных баз данных Codd 05.04.2025 Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .	Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33

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

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

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

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

@Аня хукер 1 / 1 / 0 Регистрация: 06.06.2018 Сообщений: 33
	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-ному числу) 0

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

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

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

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

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

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

Решение