I am trying to make a word scrambler and am wondering if there are any algorithms I should use or if I should just build it from scratch. Any pointers would be helpful!
Asked
Active
Viewed 2,190 times
0
-
2How is that different from shuffling an array? – SLaks Dec 25 '11 at 19:04
-
2What exactly do you mean by "scrambling a word"? – Staven Dec 25 '11 at 19:04
-
Should the scrambled word be meaningful or purely random? – nikhil Dec 25 '11 at 19:09
-
purely random, and sorry, it is the same as shuffling an array I was just looking for good algorithms and had trouble finding them through a google search – Aspyn Dec 25 '11 at 19:11
2 Answers
4
The standard algorithm for finding a random permutation of a sequence of elements (or, in your case, letters in a word) is the Fisher-Yates shuffle, which in linear time produces a truly random permutation of a sequence of elements. The algorithm is well-established and many standard libraries provide implementations of it (for example, the C++ std::random_shuffle algorithm is typically implemented using this algorithm), so you may be able to find a prewritten implementation. If not, the algorithm is extremely easy to implement, and here's some pseudocode for it:
for each index i = 0 to n - 1, inclusive:
choose a random index j in the range i to n - 1, inclusive.
swap A[i] and A[j]
Be careful when implementing this that when picking a random index, you do not pick an index between 0 and n-1 inclusive; this produces a nonuniform distribution of letters (you can read more about that in this earlier question).
Hope this helps!
Community
- 1
- 1
templatetypedef
- 362,284
- 104
- 897
- 1,065
1
Go with the Knuth Shuffle (AKA the Fisher–Yates Shuffle). It has the desirable feature of ensuring that every permutation of the set is equally likely. Here's a link to an implementation in C (along with implementations in other languages) that works on arbitrarily sized objects.
toddsundsted
- 6,225
- 2
- 21
- 13