Best shuffle: Difference between revisions
Content added Content deleted
m (→{{header|D}}) |
(I am rather proud of my shuffling algorithm(s).) |
||
Line 282: | Line 282: | ||
, , (0) |
, , (0) |
||
xxxxx, xxxxx, (5)</pre> |
xxxxx, xxxxx, (5)</pre> |
||
=={{header|C sharp|C#}}== |
|||
For both solutions, a class is used to encapsulate the original string and to scrambling. A private function of the class does the actual sorting. An implicit conversion from string is also provided to allow for simple initialization, e.g.: |
|||
<lang csharp>ShuffledString[] array = {"cat", "dog", "mouse"};</lang> |
|||
Which will immediately shuffle each word. |
|||
A sequential solution, which always produces the same output for the same input. |
|||
<lang csharp> |
|||
using System; |
|||
using System.Text; |
|||
using System.Collections.Generic; |
|||
namespace BestShuffle_RC |
|||
{ |
|||
public class ShuffledString |
|||
{ |
|||
private string original; |
|||
private StringBuilder shuffled; |
|||
private int ignoredChars; |
|||
public string Original |
|||
{ |
|||
get { return original; } |
|||
} |
|||
public string Shuffled |
|||
{ |
|||
get { return shuffled.ToString(); } |
|||
} |
|||
public int Ignored |
|||
{ |
|||
get { return ignoredChars; } |
|||
} |
|||
private void Swap(int pos1, int pos2) |
|||
{ |
|||
char temp = shuffled[pos1]; |
|||
shuffled[pos1] = shuffled[pos2]; |
|||
shuffled[pos2] = temp; |
|||
} |
|||
//Determine if a swap between these two would put a letter in a "bad" place |
|||
//If true, a swap is OK. |
|||
private bool TrySwap(int pos1, int pos2) |
|||
{ |
|||
if (original[pos1] == shuffled[pos2] || original[pos2] == shuffled[pos1]) |
|||
return false; |
|||
else |
|||
return true; |
|||
} |
|||
//Constructor carries out calls Shuffle function. |
|||
public ShuffledString(string word) |
|||
{ |
|||
original = word; |
|||
shuffled = new StringBuilder(word); |
|||
Shuffle(); |
|||
DetectIgnores(); |
|||
} |
|||
//Does the hard work of shuffling the string. |
|||
private void Shuffle() |
|||
{ |
|||
int length = original.Length; |
|||
int swaps; |
|||
Random rand = new Random(); |
|||
List<int> used = new List<int>(); |
|||
for (int i = 0; i < length; i++) |
|||
{ |
|||
swaps = 0; |
|||
while(used.Count <= length - i)//Until all possibilities have been tried |
|||
{ |
|||
int j = rand.Next(i, length - 1); |
|||
//If swapping would make a difference, and wouldn't put a letter in a "bad" place, |
|||
//and hasn't already been tried, then swap |
|||
if (original[i] != original[j] && TrySwap(i, j) && !used.Contains(j)) |
|||
{ |
|||
Swap(i, j); |
|||
swaps++; |
|||
break; |
|||
} |
|||
else |
|||
used.Add(j);//If swapping doesn't work, "blacklist" the index |
|||
} |
|||
if (swaps == 0) |
|||
{ |
|||
//If a letter was ignored (no swap was found), look backward for another change to make |
|||
for (int k = i; k >= 0; k--) |
|||
{ |
|||
if (TrySwap(i, k)) |
|||
Swap(i, k); |
|||
} |
|||
} |
|||
//Clear the used indeces |
|||
used.Clear(); |
|||
} |
|||
} |
|||
//Count how many letters are still in their original places. |
|||
private void DetectIgnores() |
|||
{ |
|||
int ignores = 0; |
|||
for (int i = 0; i < original.Length; i++) |
|||
{ |
|||
if (original[i] == shuffled[i]) |
|||
ignores++; |
|||
} |
|||
ignoredChars = ignores; |
|||
} |
|||
//To allow easy conversion of strings. |
|||
public static implicit operator ShuffledString(string convert) |
|||
{ |
|||
return new ShuffledString(convert); |
|||
} |
|||
} |
|||
public class Program |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
ShuffledString[] words = { "abracadabra", "seesaw", "elk", "grrrrrr", "up", "a" }; |
|||
foreach(ShuffledString word in words) |
|||
Console.WriteLine("{0}, {1}, ({2})", word.Original, word.Shuffled, word.Ignored); |
|||
Console.ReadKey(); |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
And a randomized solution, which will produce a more or less different result on every run: |
|||
<lang csharp> |
|||
using System; |
|||
using System.Text; |
|||
using System.Collections.Generic; |
|||
namespace BestShuffle_RC |
|||
{ |
|||
public class ShuffledString |
|||
{ |
|||
private string original; |
|||
private StringBuilder shuffled; |
|||
private int ignoredChars; |
|||
public string Original |
|||
{ |
|||
get { return original; } |
|||
} |
|||
public string Shuffled |
|||
{ |
|||
get { return shuffled.ToString(); } |
|||
} |
|||
public int Ignored |
|||
{ |
|||
get { return ignoredChars; } |
|||
} |
|||
private void Swap(int pos1, int pos2) |
|||
{ |
|||
char temp = shuffled[pos1]; |
|||
shuffled[pos1] = shuffled[pos2]; |
|||
shuffled[pos2] = temp; |
|||
} |
|||
//Determine if a swap between these two would put a letter in a "bad" place |
|||
//If true, a swap is OK. |
|||
private bool TrySwap(int pos1, int pos2) |
|||
{ |
|||
if (original[pos1] == shuffled[pos2] || original[pos2] == shuffled[pos1]) |
|||
return false; |
|||
else |
|||
return true; |
|||
} |
|||
//Constructor carries out calls Shuffle function. |
|||
public ShuffledString(string word) |
|||
{ |
|||
original = word; |
|||
shuffled = new StringBuilder(word); |
|||
Shuffle(); |
|||
DetectIgnores(); |
|||
} |
|||
//Does the hard work of shuffling the string. |
|||
private void Shuffle() |
|||
{ |
|||
int length = original.Length; |
|||
int swaps; |
|||
Random rand = new Random(); |
|||
List<int> used = new List<int>(); |
|||
for (int i = 0; i < length; i++) |
|||
{ |
|||
swaps = 0; |
|||
while(used.Count <= length - i)//Until all possibilities have been tried |
|||
{ |
|||
int j = rand.Next(i, length - 1); |
|||
//If swapping would make a difference, and wouldn't put a letter in a "bad" place, |
|||
//and hasn't already been tried, then swap |
|||
if (original[i] != original[j] && TrySwap(i, j) && !used.Contains(j)) |
|||
{ |
|||
Swap(i, j); |
|||
swaps++; |
|||
break; |
|||
} |
|||
else |
|||
used.Add(j);//If swapping doesn't work, "blacklist" the index |
|||
} |
|||
if (swaps == 0) |
|||
{ |
|||
//If a letter was ignored (no swap was found), look backward for another change to make |
|||
for (int k = i; k >= 0; k--) |
|||
{ |
|||
if (TrySwap(i, k)) |
|||
Swap(i, k); |
|||
} |
|||
} |
|||
//Clear the used indeces |
|||
used.Clear(); |
|||
} |
|||
} |
|||
//Count how many letters are still in their original places. |
|||
private void DetectIgnores() |
|||
{ |
|||
int ignores = 0; |
|||
for (int i = 0; i < original.Length; i++) |
|||
{ |
|||
if (original[i] == shuffled[i]) |
|||
ignores++; |
|||
} |
|||
ignoredChars = ignores; |
|||
} |
|||
//To allow easy conversion of strings. |
|||
public static implicit operator ShuffledString(string convert) |
|||
{ |
|||
return new ShuffledString(convert); |
|||
} |
|||
} |
|||
public class Program |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
ShuffledString[] words = { "abracadabra", "seesaw", "elk", "grrrrrr", "up", "a" }; |
|||
foreach(ShuffledString word in words) |
|||
Console.WriteLine("{0}, {1}, ({2})", word.Original, word.Shuffled, word.Ignored); |
|||
Console.ReadKey(); |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
A sample output for the sequential shuffle: |
|||
<pre> |
|||
abracadabra, rdabarabaac, (0) |
|||
seesaw, easwse, (0) |
|||
elk, lke, (0) |
|||
grrrrrr, rgrrrrr, (5) |
|||
up, pu, (0) |
|||
a, a, (1) |
|||
hounddog, unddohgo, (0) |
|||
</pre> |
|||
A sample of the randomized shuffle: |
|||
<pre> |
|||
abracadabra, raacarbdaab, (0) |
|||
seesaw, essewa, (0) |
|||
elk, lke, (0) |
|||
grrrrrr, rrrgrrr, (5) |
|||
up, pu, (0) |
|||
a, a, (1) |
|||
</pre> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |