Register to reply

How to do random arrangement of letters in C?

by 4102
Tags: c language, c++, programming
Share this thread:
4102
#1
Aug17-10, 05:05 AM
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 <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;
}
Phys.Org News Partner Science news on Phys.org
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
Mark44
#2
Aug17-10, 09:47 AM
Mentor
P: 21,215
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
#3
Aug17-10, 10:19 AM
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<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
#4
Aug17-10, 11:39 AM
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 <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
#5
Aug17-10, 04:35 PM
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 <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
#6
Aug21-10, 01:03 AM
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 :|
Hurkyl
#7
Aug21-10, 01:24 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
You try googling "random permutation"?
4102
#8
Aug21-10, 09:55 PM
P: 7
Quote Quote by xcvxcvvc View Post
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
#9
Aug22-10, 06:00 AM
PF Gold
Filip Larsen's Avatar
P: 958
For a bit of theoretical background you may want to read up on random shuffles, like http://en.wikipedia.org/wiki/Fisher%...3Yates_shuffle
unusualname
#10
Aug23-10, 11:35 AM
P: 661
Quote Quote by 4102 View Post
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];
  }
...


Register to reply

Related Discussions
Need help doing simple re-arrangement Calculus & Beyond Homework 6
Proof of the statement: sum of two random variables is also a random variable Set Theory, Logic, Probability, Statistics 8
Expectation and variance of a random number of random variables Calculus & Beyond Homework 3
How many permutation of six letters, a,b,c,d,e,f i got the answer for 5 letters.urnt Calculus & Beyond Homework 2
Arrangement of voltmeter Introductory Physics Homework 2