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.

Verwandte Artikel


Permutation des Arrays

gegebenes datuashvili: Zum Beispiel habe ich dieses Array: int a[] = new int[]{3,4,6,2,1}; Ich brauche eine Liste aller Permutationen, so dass, wenn eine so ist {3,2,1,4,6}, andere nicht gleich sein dürfen. Ich weiß, wenn die Länge des Arrays n ist, dann gibt

Permutation und Kombination in C #

Sikrigagan Bitte sagen Sie mir, wie ich Permutation und Kombination in der C # -Konsolenanwendung anwenden und Werte von N und r nehmen und Permutation und Kombination berechnen kann. Weston Ich habe es nur zum Spaß versucht, es ist tatsächlich eine kleine Her

Permutation: Gibt die k-te Permutation zurück

Prakash N. Ich weiß, dass es hier zum Beispiel eine O(n)zeitliche Komplexitätslösung für dieses Problem gibt . Ich bin nur neugierig, warum mein naiver Ansatz O(2^n)in Python nicht funktioniert. Algorithmus: Ich finde die Permutationen nur rekursiv und wenn da

Geschichtete Permutation mit Bootstrap

Giac Ich habe Probleme beim Versuch, Permutationen zu schichten. Meine Daten sehen folgendermaßen aus: gender party value 1 F Democrat 762 2 M Democrat 484 3 F Independent 327 4 M Independent 239 5

Rang einer Permutation

WhitneyChia Es gab also eine Frage, die ich hauptsächlich aufgrund von Rechenleistung oder mangelnder Rechenleistung nicht lösen konnte. Ich habe mich gefragt, wie ich das codieren soll, damit ich es tatsächlich auf meinem Computer ausführen kann. Der Kern der

Itertools Permutation mit Lambda

Mishavacic items = ['a', 'b', 'c','d'] from itertools import permutations for p in permutations(items): p1=(''.join(p)) p2=filter(lambda x: x[1]=='b',p1) Ich möchte Zeichenfolgen mit b im zweiten Index ausschließen. Wenn ich versuche, das Filterobjekt

Permutation mit Bitmaske generieren

BuggerNot Ich generiere alle Permutationen eines Strings mit Bitmaske. void recurse(string s, int mask,int taken){ if(taken == n){ cout << " "; return; } for(int i = 0; i < n; i++){ if(((1 << i) & mask) == 0){ c

Permutation Algorithm in Haskell

user2573189 I read this permutation function example in a Haskell textbook and I was wondering if someone could help me understand what is happening. Also, assume that the function delete simply deletes the first occurrence of a value from a list and returns t

Rekursive Permutation (Zählregel)

gruevy Ich habe eine Reihe von Fragen durchgesehen und diese nicht gefunden. Ich muss eine rekursive Methode schreiben, die eine Permutation P (N, K) zurückgibt. Das heißt, Pool von 20 Objekten, Zeichnung 3, wie viele Möglichkeiten gibt es für die Reihenfolge,

Permutation in JavaScript

jhone Hier ist mein Problem: Suchen Sie für einen bestimmten Satz nach Vorkommen des angegebenen Zeichensatzes. Wählen Sie gefilterte Wörter aus und generieren Sie Permutationen. (Satz und Zeichen dürfen nur Großbuchstaben enthalten.) Ausgewählte Wörter und Pe

Python, Permutation zur Permuationsindexfunktion

Fadedbee Ich habe einige Permutationen einer Liste: >>> import itertools >>> perms = list(itertools.permutations([0,1,2,3])) >>> perms [(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3)

Vektorisierende paarweise Permutation

user18764 Nehmen wir an, ich habe ohne Verlust der Allgemeinheit ein 1-D-Array X, mit dem ich ein 3-D-Array Yerstellen möchte , das alle paarweisen Permutationen von enthältX[i], X[j] Mit anderen Worten: Y = np.zeros((X.shape, X.shape,X.shape)) for i in range(

Beschleunigen Sie die Permutation

mohamadmahdi Ich habe die nächste Aufgabe. Gegebene ganze Zahlen n( 1 <= n <= 1000000) und k( 1 <= k <= n). Es ist erforderlich, eine Permutation pvon ganzen Zahlen zu finden, 1, 2, 3, ..., nso dass die absolute Differenz zwischen jeweils zwei aufeinanderfolge

Prolog: zufällige Permutation

Tofu Ich versuche eine zufällige Permutation mit Prolog zu bekommen. Aber das Problem ist ?- permutation([1,2,3,4],L). gibt immer L = [1, 2, 3, 4]als erste Antwort. Ich könnte dies mithilfe der Abfrage beheben ?- L1=[1,2,3,4], permutation(L1,L2), dif(L1,L2).

C-Code-Permutation

user2530773 Hier ist ein Permutationscode, der jedoch nicht alle möglichen Permutationen druckt. Nur gedruckt ist die Eingabe. Was ist los mit diesem Code? #include <stdio.h> #include <string.h> #include <stdlib.h> int bitmask; char* characters; int character

Permutation und Kombination in Python

Python Hat Python eine eingebaute Funktion, mit der ich eine Sequenz wie diese generieren kann? Für i = 5, wie viele verschiedene Arten 0 und 1 können fünf Stellen besetzen wie 00000 00001 00010 00011 00100 . . . . 11111 für i = 6, wie viele Wege 0 und 1 könn

Permutation in SQL

user5529778 Ich habe das folgende Problem und kann keine Lösung finden (auch nachdem ich viel im Internet gesucht habe). Ich habe eine Tabelle mit Projekten und den zugehörigen Mitarbeitern (ca. 100.000 Einträge): +------------+-------------+ | Project ID |

Python 3, Permutation, Kombination

Baller Mein Problem ist: Schreiben Sie einen Code, der alle möglichen Kombinationen für x, y, z so ausgibt, dass sie dem Eingabewert der Gesamtsumme entsprechen. x,y,z = integer:: x*500 + y*300 + z*400 = total sum aber es wurden nicht alle möglichen Antworten

String-Permutation

Amir Ich habe folgenden Java-Code gefunden. Es zählt alle Permutationen eines Strings. Ich kann jedoch nicht verstehen, was es in der for-Schleife der Permutationsmethode tut. Genauer gesagt kann ich den Zweck des rem-Strings und des rekursiven Aufrufs nicht v

String Permutation Kick udf

Zied Hermi Ich konvertiere ein Schwein-Skript mit Scala in Spark 1.6, ich habe einen Datenrahmen, der eine Zeichenfolge enthält, und ich möchte Zeichen in einer bestimmten Reihenfolge austauschen. Beispiel: +----------------+ | Info| +--------------

PHP: Alphabetische Permutation

Mikko Ich habe schwierige Hausaufgaben: Die Liste enthält alphabetisch alle Strings, die die Buchstaben AK bilden können. Der Anfang der Liste sieht so aus: ABCDEFGHIJK, ABCDEFGHIKJ, ABCDEFGHJIK, ABCDEFGHJKI, ... Der dritte String in der Liste ist ABCDEFGHJIK.

Fragment is unstable in Android Studio

KARUNESH PALEKAR I am a complete beginner in using Android Studio . Here in this code I am trying to implement a Fragment using a button imposed in the Toolbar .Basically, I want to display the fragment content when clicked on the add button.I want to take few

Permutation ohne Wiederholung

Chris Ich suche nach einem einfachen Befehl / einer einfachen Funktion, um eine Permutation eines Zahlensatzes zu generieren, der als Parameter eines Shell-Befehls angegeben wird. Hier am Beispiel kann ich alle 6-Zahlen-Permutationen aus 1-6 Zahlen in Python g

Matrixspalten Permutation Python

Wanderung Ich versuche, eine Lösung zu finden, um alle Spaltenpermutationen einer Matrix zu finden. Also habe ich diesen Code geschrieben, aber er funktioniert nicht. Gelöst: #! python import numpy def permutation(matrix): if numpy.size(matrix,1) == 1:

Permutation in C++

unbekannt29 class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int> > result; vector<int> sofar; permutehelper(nums, sofar, result); return result; } void permutehelper(vect

Fragment is unstable in Android Studio

KARUNESH PALEKAR I am a complete beginner in using Android Studio . Here in this code I am trying to implement a Fragment using a button imposed in the Toolbar .Basically, I want to display the fragment content when clicked on the add button.I want to take few

Permutation mit Begrenzung

SeekNDstroy Ich möchte jeweils eine Menge von Elementen permutieren. Allerdings für jedes Element in der Menge. Ich möchte die Wiederholungszeiten begrenzen. Hier ist ein Codeschnipsel zum Verständnis: _list_ = [0,1,3] limit_dict = { 0 : [0, 1],

Python Effizientere Permutation

Dan7nm Ich habe eine Zeichenfolge, die aus x Menge des Buchstabens 'r' und y Menge von 'u' besteht. Und mein Ziel ist es, alle möglichen Kombinationen derselben Menge x,y mit unterschiedlichen Reihenfolgen zu drucken. Dies ist mein Beispiel für einen funktioni