Unstable permutation

sujithra baskaran

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.

Stuart

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.

Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.

Bei Verstößen wenden Sie sich bitte [email protected] Löschen.

bearbeiten am
0

Lass mich ein paar Worte sagen

0Kommentare
LoginNach der Teilnahme an der Überprüfung

Verwandte Artikel

TOP Liste

  1. 1

    Wie aktualisiere ich ein Feld in einer Raumdatenbank mit einem Repository und einem Ansichtsmodell?

  2. 2

    Wie füge ich mehrere Spalten in einer Spalte mit derselben Tabelle in SQL Server zusammen?

  3. 3

    Wie kann man Gitterquadrate dazu bringen, die Farbe zu ändern?

  4. 4

    Ich kann nicht verstehen, wie man Go-Code in mehreren Dateien kompiliert

  5. 5

    Zählen Sie die Vorkommen jedes Werts in einem Tupel in Python

  6. 6

    Gibt es eine sauberere Möglichkeit, Konstruktorargumente und Instanzeigenschaften einer Klasse in Typescript zu definieren?

  7. 7

    So implementieren Sie Pushwoosh mit ionic 2

  8. 8

    Wie wird der Wert im Dropdown-Menü basierend auf den ausgewählten Daten / IDs angezeigt?

  9. 9

    Tomcat - Leiten Sie den alten Kontextstamm zum neuen Kontextstamm um

  10. 10

    Ändern Sie den Knotenpfad in das aktuelle Verzeichnis

  11. 11

    So erstellen Sie ein Array von Objekten aus zwei Arrays von Objekten mit einem gemeinsamen Schlüssel - JavaScript

  12. 12

    Rufen Sie die ID aus der Datagrid-Ansicht ab und zeigen Sie die Daten in Textfeldern einem anderen Formular an

  13. 13

    base js: Wie füge ich einem Objekt eine Eigenschaft auf die 'alte' Weise hinzu?

  14. 14

    Ersetze einen Teil einer Zeichenfolge durch eine Pandas-Spalte als Muster

  15. 15

    Blättern Sie auf Radio Click zur Abschnitts-ID

  16. 16

    CBCentralManager wird nach dem Verbinden neu gestartet

  17. 17

    Scherz, wie man eine Funktion verspottet, die von einer verspotteten Funktion zurückgegeben wird

  18. 18

    django-allauth Empfängersignal zum Hinzufügen einer Gruppenberechtigung zum Benutzer bei der Anmeldung

  19. 19

    Tic Tac Toe-Spiel im React-Reset-Button funktioniert nicht

  20. 20

    AQL: Teilweise Übereinstimmung in einer Reihe von Zeichenfolgen

  21. 21

    So summieren Sie die Werte zweier Tabellen und gruppieren sie nach Datum

heißlabel

Archiv