How to do random arrangement of letters in C?

1. Aug 17, 2010

4102

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.

#include <iostream>
#include <cstdlib>
#include <ctime>
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;
}

2. Aug 17, 2010

Staff: Mentor

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.

3. Aug 17, 2010

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:

Code (Text):
#include<iostream>
#include<ctime>

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);
}

4. Aug 17, 2010

unusualname

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

Code (Text):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
char poss[] = "ALTEC";

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

srand(time(NULL));

for (i=0; i<l; i++)
{
do {
r = rand()%l;
} while (poss[r] == 0);

putchar(poss[r]);
poss[r] = 0;
}

puts("");

return 0;
}

Last edited: Aug 17, 2010
5. Aug 17, 2010

unusualname

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.

Code (Text):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
char poss[] = "ALTEC";

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;
}

6. Aug 21, 2010

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 :|

7. Aug 21, 2010

Hurkyl

Staff Emeritus
You try googling "random permutation"?

8. Aug 21, 2010

4102

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?

9. Aug 22, 2010

Filip Larsen

10. Aug 23, 2010

unusualname

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

Code (Text):
#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;

Code (Text):
$gcc -o strperm strperm.c$ ./strperm "ALTEC"
TALCE
\$ ./strperm "ALTEC123"
A2E31CTL
...

EDIT
more efficient than using memove, just use a single char copy:

Code (Text):

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

Last edited: Aug 23, 2010