# How to do random arrangement of letters in C?

by 4102
Tags: c language, c++, programming
 P: 7 Hi I'm making a program that generates a different arrangement of letters in C. For example, the word ALTEC will be rearranged randomly by the program. the output would be "LETAC" or "CEALT" etc. The program should use all the given letters and not repeat the letters. Here's a code sample I made but the problem is that it repeats other letters, example output of this is like "ELTAA" instead of "ELTAC", it should not repeat the letter that is used already. Also I need only ONE output, and not all the possible permutations. by the way, the some of the codes used is C++, what i need is for C. It's quite a mix up already I'm quite confused. Please help! Thanks! #include #include #include using namespace std; int main() { srand(time(NULL)); char possibilities[6] = "ALTEC"; for(int i = 0; i < 5; i++) { cout << possibilities[rand() % 5]; } cin.get(); return 0; }
 Mentor P: 21,258 What your code is doing is picking one of the five letters for each iteration of the loop. This doesn't work, because as you're finding, there is nothing to prevent a letter that has already been used from being used again. For the first letter of an output string, there are five possibilities, but for the next letter, there are only four possibilities left, since one letter was already used. For the third letter, there are only three possibilities, then two, and then finally, a single letter is left. Since there are five letters, there are 5! = 5*4*3*2*1 = 120 different permutations, ranging from ACELT to TLECA.
 P: 393 You can compress the data inward toward the randomly chosen index to eliminate selecting the same character twice. You must be careful to also size how your index is randomly generated, though, or you could randomly select a spot in possibilities that no longer represents unused characters. Example: #include #include using namespace std; int main() { //declarations char possibilities[] = "ABC"; const int LENGTH = 3; int index; //seed the random generator srand(time(NULL)); for(int i = 0; i < LENGTH; ++i) { index = rand() % (LENGTH - i); cout << possibilities[index]; for(int j = 0; j < (LENGTH - i - index); ++j) possibilities[index + j] = possibilities[index + j + 1]; } cout << endl; //success! return(0); }
 P: 661 How to do random arrangement of letters in C? An inefficient but simple solution is to use a marker to mark when a letter has been used, and loop repeatedly until an unused letter is found. Eg in the array poss[] below 0 is used to mark the position of any used letters. eg C code like this would work, but this is a pretty terrible method except for the simplest of uses #include #include #include int main() { char poss[] = "ALTEC"; int i,r, l = strlen(poss); srand(time(NULL)); for (i=0; i
 P: 661 Doing it with memmove is algorithmically cleaner but has the overhead of doing memory operations for each character in the possibilities string (instead of calculating rand() a few times for each character) As in the above C code, the initial string poss="ALTEC" can be set to anything without changing the rest of the code. #include #include #include int main() { char poss[] = "ALTEC"; int i,r,l = strlen(poss); srand(time(NULL)); for (i=0; i
 P: 7 thanks guys. :D but I'm looking for pure C code. having it in c++ is not an option. Thank you! L :D I'm still confused :|
 Emeritus Sci Advisor PF Gold P: 16,091 You try googling "random permutation"?
P: 7
 Quote by xcvxcvvc You can compress the data inward toward the randomly chosen index to eliminate selecting the same character twice. You must be careful to also size how your index is randomly generated, though, or you could randomly select a spot in possibilities that no longer represents unused characters. Example: #include #include using namespace std; int main() { //declarations char possibilities[] = "ABC"; const int LENGTH = 3; int index; //seed the random generator srand(time(NULL)); for(int i = 0; i < LENGTH; ++i) { index = rand() % (LENGTH - i); cout << possibilities[index]; for(int j = 0; j < (LENGTH - i - index); ++j) possibilities[index + j] = possibilities[index + j + 1]; } cout << endl; //success! return(0); }
This is one is really close to what i need, i just don't know how to convert "cout << possibilities[index];" to a C code which should begin at "printf(________);"

so please can you help me on this one?
 PF Gold P: 959 For a bit of theoretical background you may want to read up on random shuffles, like http://en.wikipedia.org/wiki/Fisher%...3Yates_shuffle
P: 661
 Quote by 4102 thanks guys. :D but I'm looking for pure C code. having it in c++ is not an option. Thank you! L :D I'm still confused :|
I used pure C code, in both examples.

To make it more versatile, supply the possibilities string on the command line instead of hardcoding it

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
if (argc <= 1) return 1;
char * poss = argv[1];

int i,r,l = strlen(poss);

srand(time(NULL));

for (i=0; i<l; i++)
{
r = rand()%(l-i);
putchar(poss[r]);
memmove(poss+r,poss+r+1,l-r);
}

puts("");

return 0;
$gcc -o strperm strperm.c$ ./strperm "ALTEC"
TALCE
\$ ./strperm "ALTEC123"
A2E31CTL
...
EDIT
more efficient than using memove, just use a single char copy:

...
for (i=strlen(poss); i>0; i--)
{
r = rand()%i;
putchar(poss[r]);
poss[r]=poss[i-1];
}
...

 Related Discussions Calculus & Beyond Homework 6 Set Theory, Logic, Probability, Statistics 8 Calculus & Beyond Homework 3 Calculus & Beyond Homework 2 Introductory Physics Homework 2