How to do random arrangement of letters in C?

[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.
Please help! Thanks!

#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++)
{
count << possibilities[rand() % 5];
}
cin.get();
return 0;
}

 

[Mark44]

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.

 

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

 

[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

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

 

[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.

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

 

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

 

[Hurkyl]

You try googling "random permutation"?

 

[4102]

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

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?

 

[Filip Larsen]

For a bit of theoretical background you may want to read up on random shuffles, like http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

 

[unusualname]

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