A permutation on a set of numbers {0,...,m-1} is a function from {0,...,m-1} int

Question

A permutation on a set of numbers {0,...,m-1} is a function from {0,...,m-1} into itself where no 2 numbers are mapped onto the same image( i.e. the function "f" on {0,12} defined by f(0)=1, f(1)=0, and f(2)=2 is a permutation). We can represent a permutation on {0,...,n-1} as a list of length n, where the kth element of the list contains the image of k under the corresponding permutation. For instance, the above function f would be represented as [1,02].

Write a function main(n1,n2), that calculates the composition of two permutations. (for example, the permutation that first appplies p2 and then p1). (i.e. main([1,0,2],[1,2,0]) would print.return [0,21]

Explanation / Answer

Solution:

To set some context, the problem states that we represent a function that reorders its input(permutation function). Given an input x from 0-m, 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.

The function main(n1,n2) takes in 2 functions n1,n2(represented as python lists) and returns a new function n3(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 01 by using p2[i] and then use it as input to the function p1 and get its output using p1[01]. We do this for all inputs by iterating over the list.

As code, this can be represented as :

def main(n1, n2):

n3 = [p1[i] for i in p2]

return n3

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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