Unstable permutation
Today, I tried to solve this question:
A permutation P is called unstable if it keeps changing every second based on the rule below. -Every element of the permutation is changing every second
independently following a rule, i.e., after one second every P[i] becomes P[P[i]]
Given a permutation, find the minimum time after which it will become stable. If it will never become stable, return -1.
For example, given N = 3 and P[3,2,1], In one second it will become [P[P[3]], P[P[2]], P[P[1]] ] = [1, 2, 3]. The permutation [1,2,3] is stable as it will not change further after applying the same rule again.
Function Description Complete the function solve the editor below. The function should return a single integer as stated above.
solve has the following parameter: P[P[1],...P[n]]: an array of integers
Constraints
1 <= n <= 10^5
1 <= P[i] <= n
The first line contains n that denotes the length of Permutation.
The following line contains permutation P of n distinct space-separated integers.
Sample Case 0: Sample Input For Custom Testing
[1,3,2,5,6,7,4]
Sample Output
2
Explanation After one second, the permutation will become [1,2,3,6,7,4,5]
. After two seconds, the permutation will become [1,2,3,4,5,6,7]
.
Sample Case 1: Sample Input For Custom Testing
[2,3,1,5,6,7,4]
Sample Output
-1
Explanation: The permutation never becomes stable, thus the answer is -1.
My Code:
p=[2, 3, 1, 5, 6, 7, 4]
n=len(p)
if all(p)<=n and all(p)>=1:
length=0
pz=p
#pz.sort()
p.insert(0,0)
print(p)
n=len(p)
p1=[0]*(n)
print(p,p1)
for i in range(1,n):
print(i,p[i],p1[i])
j=p[i]
p1[i]=p[j]
length+=1
if p==pz:return length
#else:
print(len(p))
print(len(p1))
print(p,p1)
else:
return -1
Output:
[0, 1, 3, 2, 5, 6, 7, 4]
[0, 1, 3, 2, 5, 6, 7, 4] [0, 0, 0, 0, 0, 0, 0, 0]
1 1 0
2 3 0
3 2 0
4 5 0
5 6 0
6 7 0
7 4 0
8
8
[0, 1, 3, 2, 5, 6, 7, 4] [0, 1, 2, 3, 6, 7, 4, 5]
Can anyone help me how to proceed further and explain if I approached it in wrong way.
Your approach is okay for counting how many changes are needed for the permutation to become stable, but does not seem to have a way of recognizing a permutation that will never become stable.
Your condition all(p)<=n and all(p)>=1
seems to be in error. all(p)
is always True
and True<=n and True>=1
also evaluates as True
, so you will never return -1. Even if you fixed this to something like all(1 <= i <= n for i in p)
, it would still always return True
, as the values in p
are between 1 and n even after rearranging them. A condition like this is not going to help us spot a never-stable permutation.
One way to recognize a permutation that will never become stable is to spot when it returns to an order we have already seen - that means we are stuck in a loop and will never reach the goal of [1,2,3, ..., n]
. That can be done by saving the permutations as tuples in a set and checking whether each new one has been seen already.
from itertools import count
def stability(p, numbering=0):
p = tuple(n - numbering for n in p) # simpler to adjust the list to zero-based numbering
goal = tuple(range(len(p))) # (0, 1, 2, ..., n-1)
seen = set()
for tries in count():
if p == goal:
return tries
elif p in seen: # We have been here before, so we must be stuck in a loop and will never reach the goal
return -1
seen.add(p)
p = tuple(p[n] for n in p)
print(stability([1,3,2,5,6,7,4], numbering=1)) # 2
print(stability([2,3,1,5,6,7,4], numbering=1)) # -1
When n
is large, the storing of long lists in seen
and looking them up will become slow. There might be a faster way to recognize a permutation that will never become stable using smarter maths.