2. 3. A permutation on a set of numbers (o..n-1) is a function from 50,.n-1) int

Question

2.

3.

A permutation on a set of numbers (o..n-1) is a function from 50,.n-1) into itself such that no two numbers are mapped on the same image For instance, the function f on (0,1,2 defined by f(0)-1,(1)-0, and f(2)-2 is a permutation. In Python, we can represent a permutation on (0,.,n-1) as a list of length n, where the i-th element of the list contains the image of i under the corresponding permutation. For instance, the above function f would be represented as Write a Python function compose(p1,p2), which computes the composition of two permutations, i.e., the permutation that first applies (the permutation represented by the list) p2 and then applies (the permutation represented by the list) p1. Your function must check that p1 and p2 represent valid permutations on the same set of numbers. Example composel1,0.21 /1.20) must return

Explanation / Answer

Answer :

Problem 2 :
To set some context, the problem states that we represent a function that reorders its input(permutation function). Given an input x from 0-n, f(x) gives us x reordered. The question also states that we can represent such functions using simple lists. How?
The set of inputs to a given function in the problem range from 0-N. The indexes of a given list also range from 0-N. Furthermore, for each x, the function maps it to a new number, also between 0-N. Lists do the same. For any index x and list l, l[x] gives the element at position x. The input of the function is the index of our list. The output of a function is the value we get from our list. Therefore, we can represent such functions using lists.
As an example, [1,0,2] is a permutation function that maps input 0 to output 1 (list[0] -> 1), input 1 to 0 and input 2 to output 2.
Coming to the problem, the function compose(p1,p2) takes in 2 functions p1,p2(represented as python lists) and returns a new function p3(python list) so that it would have the same effect on a given set of inputs that applying p2 and p1 would have. We take our input(which is constrained from 0-N), get the output o1 by using p2[i] and then use it as input to the function p1 and get its output using p1[o1]. We do this for all inputs by iterating over the list.
As code, this can be represented as :
def compose(p1, p2):
p3 = [p1[i] for i in p2]
return p3
Problem 3:
As for problem 3, we repeatedly call the compose function defined above and check whether the result equals p2. We do this a fixed number of times.
def is_power(p1,p2):
x = p1
attempt_max = len(p1)
attempt = 1
while(attempt <= attempt_max):
p3 = compose(x,p1)
if(p3 == p2):
return true
attempt += 1
x = p3;
return false

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.