Random Permutations Consider the following approach for shuffling a deck of n cards: Apply the following procedure for i

[answerhappygod]

Random Permutations
Consider the following approach for shuffling a deck of ncards:
Apply the following procedure for i = 1, . . . , n:
• Choose a random card in the deck.
• Swap the i-th card in the deck with the randomly-selectedcard.
We say that a deck is perfectly shuffled if after applying theshuffling algorithm to any initial configuration of the cards, allpossible orderings of the deck are equally likely.
1. Describe a shuffling algorithm that perfectly shuffles anydeck of n cards in O(n) swaps. Prove that all possible orderings ofthe deck are equally likely using your algorithm (Hint: allorderings will be equally likely if every element has a 1/nprobability of ending up at any arbitrary index).