# Best Shuffle Algorithm

## Introduction

The Best Shuffle algorithm is used to shuffle a string such that no two consecutive characters remain the same. It is a simple algorithm that can be used in various applications such as cryptography, data encryption, and data compression.

## Implementation

The implementation of the Best Shuffle algorithm is provided below in OCaml. The algorithm takes a string as input and returns the shuffled string.

```
let best_shuffle s =
let len = String.length s in
let r = String.copy s in
for i = 0 to pred len do
for j = 0 to pred len do
if i <> j && s.[i] <> r.[j] && s.[j] <> r.[i] then
begin
let tmp = r.[i] in
r.[i] <- r.[j];
r.[j] <- tmp;
end
done;
done;
(r)
```

Here is an example.

```
let count_same s1 s2 =
let len1 = String.length s1
and len2 = String.length s2 in
let n = ref 0 in
for i = 0 to pred (min len1 len2) do
if s1.[i] = s2.[i] then incr n
done;
!n
let () =
let test s =
let s2 = best_shuffle s in
Printf.printf " '%s', '%s' -> %d\n" s s2 (count_same s s2);
in
test "tree";
test "abracadabra";
test "seesaw";
test "elk";
test "grrrrrr";
test "up";
test "a";
;;
```

## Step-by-step Explanation

- The length of the input string is calculated and stored in the variable
`len`

. - A copy of the input string is made and stored in the variable
`r`

. - The algorithm iterates over each character in the input string using a nested loop.
- For each pair of characters, the algorithm checks if they are not equal, and if swapping them will not create two consecutive characters that are the same.
- If the conditions in step 4 are met, the characters are swapped.
- The shuffled string is returned.

## Complexity Analysis

The time complexity of the Best Shuffle algorithm is O(n^2), where n is the length of the input string. This is because the algorithm uses a nested loop to iterate over each pair of characters in the input string. The space complexity of the algorithm is O(n), where n is the length of the input string. This is because the algorithm creates a copy of the input string to store the shuffled string. Overall, the Best Shuffle algorithm is a simple and efficient algorithm for shuffling strings.