-
Notifications
You must be signed in to change notification settings - Fork 0
/
permute.py
48 lines (38 loc) · 1.89 KB
/
permute.py
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
https://docs-python.ru/standart-library/modul-itertools-python/funktsija-permutations-modulja-itertools/
https://losst.pro/komanda-wc-v-linux
"""
import sys
from itertools import permutations
from timing import timing
@timing
def generate_permutations(N):
"""
Генерирует все возможные перестановки последовательности чисел
и нулей длины N.
## Аргументы:
N (`int`): Длина последовательности.
## Возвращает:
`Tuple`: Список строк, представляющих все возможные перестановки
последовательности.
Функция permutations() генерирует n! перестановок для списка из
n элементов. В данном случае, n = 2N, поскольку elements содержит
2N элементов и генерация будет представлять экспоненциальный рост O((2N)!).
Преобразование каждой перестановки в строку это ещё N.
Таким образом, теоретическое время выполнения алгоритма этой функции будет
примерно O((2N)! * N).
"""
zeros = ['0'] * N
numbers = [str(i) for i in range(1, N + 1)]
elements = zeros + numbers
perms = set(permutations(elements, len(elements)))
return tuple(''.join(perm) for perm in perms)
if __name__ == '__main__':
if len(sys.argv) != 2:
print('Запуск программы должен выглядеть так: "python permute.py 5"')
sys.exit(1)
N = int(sys.argv[1])
perms = generate_permutations(N)
with open('permutations.txt', 'w') as file:
for perm in perms:
file.write(perm + '\n')