Problem:

Permutation

 

  For given a sequence $A = \{a_0, a_1, ..., a_{n-1}\}$, print the previous permutation and the next permutation in lexicographic order.

Input

  A sequence is given in the following format.

$n$
$a_0 \; a_1 \; ... \; a_{n-1}$

Output

  Print the previous permutation, the given sequence and the next permutation in the 1st, 2nd and 3rd lines respectively.
  Separate adjacency elements by a space character. Note that if there is no permutation, print nothing in the corresponding line.

Constraints

  
$1 \leq n \leq 9$

  
$a_i$ consist of $1, 2, ..., n$

Sample Input 1

3
2 1 3

Sample Output 1

1 3 2
2 1 3
2 3 1

Sample Input 2

3
3 2 1

Sample Output 2

3 1 2
3 2 1



Sample input:
3
2 1 3


Sample output:
1 3 2
2 1 3
2 3 1

Submission status: Accepted

Solution code:
import itertools

def print_elements(a):
    print(' '.join(list(map(str, a))))

n = int(input())
a = tuple(map(int, input().split(' ')))

permutations = list(itertools.permutations([i+1 for i in range(n)]))
for i, per in enumerate(permutations):
    if per == a:
        if i != 0: print_elements(permutations[i-1])
        print_elements(a)
        if i != len(permutations)-1: print_elements(permutations[i+1])

Submission status: Accepted

Solution code:

import operator


def permutations(li):
    """Returns a list of previous, current, and
    next permutations of li.

    >>> permutations([1, 2])
    [[1, 2], [2, 1]]
    >>> permutations([1, 3, 2])
    [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
    """
    def perm(op):
        def func(xs):
            i = len(xs) - 1
            while i > 0 and op(xs[i-1], xs[i]):
                i -= 1
            if i > 0:
                i -= 1
                j = i + 1
                while j < len(xs) and op(xs[j], xs[i]):
                    j += 1
                xs[i], xs[j-1] = xs[j-1], xs[i]
                return xs[:i+1] + list(reversed(xs[i+1:]))
            else:
                return None
        return func

    prev_perm = perm(operator.lt)
    next_perm = perm(operator.gt)

    ps = []

    pp = prev_perm(li[:])
    if pp is not None:
        ps.append(pp)

    ps.append(li[:])

    np = next_perm(li[:])
    if np is not None:
        ps.append(np)
    return ps


def run():
    n = int(input())
    li = [int(x) for x in input().split()]
    assert(n == len(li))

    for ps in permutations(li):
        print(" ".join([str(x) for x in ps]))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# AOJ ITP2_5_C: Permutation
# Python3 2018.6.24 bal4u

def next_permutation(a):
    # if list has less than two elements, has no next permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] > a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] >= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] > a[i]
    k = len(a) - 1
    while a[i] >= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True

def prev_permutation(a):
    # if list has less than two elements, has no prev permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] < a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] <= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] < a[i]
    k = len(a) - 1
    while a[i] <= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True
            
n = int(input())
a = list(map(int, input().split()))
n, p = list(a), list(a)
if prev_permutation(p): print(*p)
print(*a)
if next_permutation(n): print(*n)

Submission status: Accepted

Solution code:
def next_permutation(a):
    # if list has less than two elements, has no next permutation
    if len(a) < 2:
        return False

    # step1 : find max i for a[i] > a[i+1]
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i+1]:
        i -= 1
    if i < 0:
        return False
    j = i + 1

    # step2 : find max k for a[k] > a[i]
    k = len(a) - 1
    while a[i] >= a[k]:
        k -= 1

    # step3 : swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step4 : reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True


def prev_permutation(a):
    # if list has less than two elements, has no prev permutation
    if len(a) < 2:
        return False

    # step1 : find max i for a[i] < a[i+1]
    i = len(a) - 2
    while i >= 0 and a[i] <= a[i+1]:
        i -= 1
    if i < 0:
        return False
    j = i + 1

    # step2 : find max k for a[k] < a[i]
    k = len(a) - 1
    while a[i] <= a[k]:
        k -= 1

    # step3 : swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step4 : reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True


n = int(input())
a = list(map(int, input().split()))
n, p = list(a), list(a)
if prev_permutation(p):
    print(*p)
print(*a)
if next_permutation(n):
    print(*n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	permutation
# CreatedDate:  2020-07-08 19:01:42 +0900
# LastModified: 2020-07-08 19:17:50 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import permutations as nPr
from copy import deepcopy


def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = sorted(deepcopy(a))
    p = list(nPr(s))
    inde = p.index(tuple(a))
#    print(p)
#    print(inde)
    if inde!=0:
        print(p[inde-1][0], end="")
        for i in range(1, n):
            print(" {}".format(p[inde-1][i]), end="")
        print()
    print(p[inde][0], end="")
    for i in range(1, n):
        print(" {}".format(p[inde][i]), end="")
    print()
    if inde!=len(p)-1:
        print(p[inde+1][0], end="")
        for i in range(1, n):
            print(" {}".format(p[inde+1][i]), end="")
        print()
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    n = int(input())
    target = tuple(int(i) for i in input().split())
    before = None
    found = False
    for a in sorted(itertools.permutations(target)):
        if found:
            print(*a)
            return
        elif a == target:
            if before is not None:
                print(*before)
            print(*target)
            found = True
        else:
            before = a


resolve()

Submission status: Accepted

Solution code:

import itertools
import copy
n = int(input())
l = list(map(int,input().split()))
l2 = copy.deepcopy(l)
l.sort()
ans = []
for i in itertools.permutations(l,n):
    ans.append(list(i))

for i in range(len(ans)):
    if ans[i] == l2:
        if i - 1 >= 0:
            print(' '.join(map(str,(ans[i - 1]))))
        print(' '.join(map(str,(ans[i]))))
        if i != len(ans) - 1:
            print(' '.join(map(str,(ans[i + 1]))))
        break

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
a = list(map(int,input().split()))

s = []
for i in permutations(sorted(a)):
    s.append(list(i))

for i in range(len(s)):
    if s[i] == a:
        if i > 0:
            print(*s[i-1])
        print(*s[i])
        if i < len(s)-1:
            print(*s[i+1])
        break

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
arr = tuple(map(int, input().split()))
p = list(permutations(sorted(arr)))
idx = p.index(arr)
for i in range(max(0, idx - 1), min(len(p), idx + 2), 1):
    print(*p[i])

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
A = tuple(map(int,input().split()))
res = [p for p in permutations(sorted(A),n)]
i = res.index(A)
for a in res[max(0,i-1):i+2]:
    print(*a)

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
a = tuple(map(int, input().split()))
p = [i for i in permutations(sorted(a))]
i = p.index(a)
for a in p[max(0, i-1):i+2]:
    print(*a)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    perm = list(permutations(sorted(a)))

    for i in range(len(perm)):
        if a == list(perm[i]):
            if 0<i:print (' '.join(map(str,perm[i-1])))
            print (' '.join(map(str,perm[i])))
            if i<len(perm)-1:print (' '.join(map(str,perm[i+1])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n = int(input())
A = list(map(int, input().split()))

p = list(itertools.permutations(A))
A2 = sorted(p)

index = A2.index(tuple(A))
if index - 1 >= 0:
    print(*A2[index - 1])

print(*A2[index])

if index + 1 < len(A2):
    print(*A2[index + 1])

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = input()
b = range(1,n+1)

prev = ""
ans1 = ""
ans2 = ""
flag = False
for x in itertools.permutations(b):
	y = " ".join(list(map(str, x)))
	if flag:
		ans2 = y
		break
	if a==y:
		ans1 = prev
		flag = True
	prev = y
	
if ans1 != "":
	print(ans1)
print(a)
if ans2 != "":
	print(ans2)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
a=[int(i) for i in input().split(" ")]

perms=list(itertools.permutations([i+1 for i in range(n)]))
for i,p in enumerate(perms):
    if list(p)==a:
        break

if i>0:
    print(" ".join([str(j) for j in perms[i-1]]))
print(" ".join([str(j) for j in perms[i]]))
try:
    print(" ".join([str(j) for j in perms[i+1]]))
except IndexError:
    pass

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


N = int(input())

table = [None] * N
check = [False] * (N+1)
MAP = {}
rev_MAP = {}
perm_index = 0


def recursive(index):
    global perm_index
    if index == N:
        tmp = 0
        for i in range(N):
            tmp = 10*tmp+table[i]

        MAP[perm_index] = tmp
        rev_MAP[tmp] = perm_index
        perm_index += 1
        return

    for i in range(1,(N+1)):
        if check[i]:
            continue
        check[i] = True
        table[index] = i
        recursive(index+1)
        check[i] = False


def outPut(num):
    S = deque()
    while True:
        S.appendleft(num%10)
        num //= 10
        if num == 0:
            break
    print("%d"%(S.popleft()),end="")
    while len(S) > 0:
        print(" %d"%(S.popleft()),end="")
    print()



recursive(0)

tmp = 0

for i in list(map(int,input().split())):
    tmp = 10*tmp+i

index = rev_MAP[tmp]
if index > 0:
    outPut(MAP[index-1])

outPut(tmp)

if index+1 in MAP:
    outPut(MAP[index+1])

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
a = tuple(map(int, input().split()))
p = list(permutations(sorted(a), n))

for i in p:
    if a == i:
        j = p.index(i)
        if j != 0:print(*p[j-1])
        print(*i)
        if j+1 < len(p):print(*p[j+1])

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    n = int(f_i.readline())
    A_s = f_i.readline().rstrip()
    
    if n == 1:
        print(A_s)
    else:
        A = tuple(map(int, A_s.split()))
        
        from itertools import permutations
        lex = tuple(permutations(range(1, n + 1), n))
        
        from bisect import bisect_left
        idx = bisect_left(lex, A)
        if idx == 0:
            print(A_s)
            print(' '.join(map(str, lex[idx+1])))
        elif idx == len(lex) - 1:
            print(' '.join(map(str, lex[idx-1])))
            print(A_s)
        else:
            print(' '.join(map(str, lex[idx-1])))
            print(A_s)
            print(' '.join(map(str, lex[idx+1])))

solve()

Submission status: Accepted

Solution code:

from itertools import permutations
input()
L = [int(x) for x in input().split()]
k = tuple(L)
prev = None
L.sort()
f = 0
for s in permutations(L):
    if s == k:
        if prev:
           print(*prev)
        print(*s)
        f += 1
    else:
        if f > 0:
            print(*s)
            break
    prev = s

Submission status: Accepted

Solution code:
import itertools
from typing import List, Tuple


def print_elems(elems):
    print(" ".join([str(elem) for elem in elems]))


if __name__ == "__main__":
    n = int(input())
    nums = tuple(map(lambda x: int(x), input().split()))
    nums_permutated = list(itertools.permutations(sorted(nums)))

    if (1 == len(nums_permutated)):
        print(nums[0])
        exit(0)

    for idx in range(1, len(nums_permutated)):
        if (nums == nums_permutated[idx - 1]):
            print_elems(nums_permutated[idx - 1])
            print_elems(nums_permutated[idx])
            exit(0)
        if (nums == nums_permutated[idx]):
            print_elems(nums_permutated[idx - 1])
            print_elems(nums_permutated[idx])
            if (idx != len(nums_permutated) - 1):
                print_elems(nums_permutated[idx + 1])
            exit(0)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
A = tuple(map(int, input().split()))

*PS, = permutations(range(1, N+1), r=N)
i = PS.index(A)
if i > 0:
    print(*PS[i-1])
print(*A)
if i < len(PS)-1:
    print(*PS[i+1])

Submission status: Accepted

Solution code:
import itertools

n = int(input())
num = list(map(int, input().split()))
per = list(itertools.permutations(num))

per.sort()
index = per.index(tuple(num))

if index != 0:
    print(' '.join(str(n) for n in per[index-1]))
print(' '.join(str(n) for n in per[index]))
if index != len(per)-1:
    print(' '.join(str(n) for n in per[index+1]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Permutation - Permutation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_C&lang=jp

"""
from itertools import permutations

n = int(input())
A = tuple(map(int, input().split()))
res = [p for p in permutations(sorted(A), n)]
i = res.index(A)
for a in res[max(0, i-1):i+2]:
    print(*a)

Submission status: Accepted

Solution code:
import itertools

if __name__ == '__main__':

	n = int(input())

	now = tuple(map(int,input().split()))

	seq = [i+1 for i in range(n)]
	seq2 = list(itertools.permutations(seq))

	ind = 0
	for j,k in enumerate(seq2):
		if k == now:
			ind = j

	if ind == 0:
		print(*seq2[ind])
		if len(seq2) != 1:
			print(*seq2[ind+1])
	elif ind+1 == len(seq2):
		print(*seq2[ind-1])
		print(*seq2[ind])
	else:
		print(*seq2[ind-1])
		print(*seq2[ind])
		print(*seq2[ind+1])

Submission status: Accepted

Solution code:
from itertools import permutations



# INPUT
n = int(input())

A = tuple(input().split())


# PROCESS, OUTPUT
str_num = ""

for num in range(1, n + 1):
    str_num += str(num)


flag_break = False
list_num_previous = None

for list_num in permutations(str_num):
    if flag_break:
        # next
        print(*list_num)
        break

    if list_num == A:
        if list_num_previous != None:
            # previous
            print(*list_num_previous)

        # now
        print(*list_num)
        flag_break = True

    list_num_previous = list_num

Submission status: Accepted

Solution code:
import itertools
n = input()
a = tuple(map(int, input().split()))
p = sorted(list(itertools.permutations(a)))

i = p.index(a)

if i > 0:
    print(*p[i-1])
print(*p[i])
if i < len(p)-1:
    print(*p[i+1])

Submission status: Accepted

Solution code:
import sys;
import itertools;

n = int(sys.stdin.readline())
a = tuple(map(int, sys.stdin.readline().split()))

prev=()
for l in itertools.permutations(sorted(a), n):
    if a==l:
        if len(prev)>0:
            print(' '.join(map(str,prev)))
        print(' '.join(map(str,a)))
    if prev==a:
        print(' '.join(map(str,l)))
    prev=l

Submission status: Accepted

Solution code:
def rec(lst,d):
    for i in range(1,len(lst)+1):
        if i not in lst:
            lst[d]  = i
            if d+1 == len(lst):
                a = list(lst)
                P.append(a)
                lst[d] = 0
                return
            else:
                rec(lst,d+1)
                lst[d] = 0

N = int(input())
S = list(map(int,input().split()))

P = []

lst = []
for i in range(N):
    lst.append(0)

rec(lst,0)

for i in range(len(P)):
    if S == P[i]:
        if i != 0:
            print(*P[i-1])
        print(*P[i])
        if i+1 != len(P):
            print(*P[i+1])

Submission status: Accepted

Solution code:
import itertools

n=int(input())
a=tuple(map(int,input().split()))
if n==1:
    print(a[0])
else:
    b=tuple(sorted(a))
    A=list(itertools.permutations(b))
    count=len(A)-1

    if A.index(a)==count:
        print(' '.join(map(str,A[count-1])))
        print(' '.join(map(str,a)))
    elif A.index(a)==0:
        print(' '.join(map(str,b)))
        print(' '.join(map(str,A[1])))
    else:
        print(' '.join(map(str,A[A.index(a)-1])))
        print(' '.join(map(str,a)))
        print(' '.join(map(str,A[A.index(a)+1])))

Submission status: Accepted

Solution code:
import itertools

n = input();
a = tuple(map(int, input().split()))
p = sorted(list(itertools.permutations(a)))

i = p.index(a)

if i > 0:
    print(*p[i-1])

print(*p[i])

if i < len(p)-1:
    print(*p[i+1])

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_C&lang=jp
#  Enumeration : python3
#  2018.12.01 yonezawa

import sys
input = sys.stdin.readline
from collections import deque

class enumeration:
    def __init__(self,n):
        self.n = n
        self.depth = 0
        self.wnum = 0
        self.nq = []
        self.bits = [ pow(2,i) for i in range(n+1) ]
        self.mk_permutation(0,0,0)

    def mk_permutation(self,depth,bflag,wnum):
        if self.n == depth:
            self.nq.append(wnum)
            return
        for i in range(1,self.n+1):
            if bflag & self.bits[i-1] != 0:
                continue
            self.mk_permutation(depth + 1,bflag + self.bits[i-1],wnum*10+i)  
            
    def printList(self):
        l = self.nq
        self.nq.sort()
        for i in l:
            self.printInttoStr(i)
            
    def printInttoStr(self,i):
        c = ""
        for j in str(i):
            c += j + " "
        print(c.strip())

    def solve(self,tc):
        pos = self.nq.index(tc)
        if (pos != 0 ):
            self.printInttoStr(self.nq[pos-1])
        self.printInttoStr(tc)
        if (pos + 1 != len(self.nq) ):
            self.printInttoStr(self.nq[pos+1])
            
def main():
    n = int(input())
    tc = 0
    for i in list(map(int,input().split())):
        tc = tc * 10 + i
    e = enumeration(n)
    e.solve(tc)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
p = list(permutations([str(x) for x in range(1, n+1)], n))
arr = tuple(input().split())
idx = p.index(arr)

[print(' '.join(p[idx+i])) for i in range(-1, 2) if 0 <= (idx+i) < len(p)]

Submission status: Accepted

Solution code:
import itertools

n = int(input())
num = list(map(int, input().split()))
per = list(itertools.permutations(num))

per.sort()
index = per.index(tuple(num))

if index != 0:
    print(' '.join(str(n) for n in per[index-1]))
print(' '.join(str(n) for n in per[index]))
if index != len(per)-1:
    print(' '.join(str(n) for n in per[index+1]))

Submission status: Accepted

Solution code:
from itertools import permutations
input(); A = tuple(map(int, input().split()))
p = sorted(list(permutations(A)))
index = p.index(A)
if index > 0: print(*p[index-1])
print(*A)
if index < len(p)-1: print(*p[index+1])

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
a = list(map(int, input().split()))
b = list(permutations(range(1, n+1)))
for i in range(len(b)):
  if b[i]==tuple(a):
    if i==0:
      pass
    else:
      print(" ".join(map(str, b[i-1])))
    print(" ".join(map(str, a)))
    if i==len(b)-1:
      pass
    else:
      print(" ".join(map(str, b[i+1])))
    break