Problem 4.3 Shuffling Cards

Introduction

The problem specification is simple: given a string \( s \), output a random permutation of \( s \). Each permutation should be equally likely.

Examples

Input:
ABC

Output:
BCA (Output may vary, as it is randomized.)

Where might you need to write such a program?

Random shuffling is widely used in various real-world applications. It is an essential step in card games, random sampling, cryptographic key generation, and load balancing algorithms. Many programming languages provide built-in functions to shuffle data, but it is an interesting problem to think about on your own, and a simple but elegant algorithm is possible.

Once you have tried on your own, see this: Fisher-Yates Shuffle Algorithm

Implementation

The following code contains a function prototype (to be implemented by you) and a main function that tests it.