LinuxQuestions.org
Register a domain and help support LQ
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 12-10-2005, 01:19 AM   #1
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Rep: Reputation: 15
using rand in matlab


I need to create a row vector that includes the numbers 1-52 randomly with no repeats. I know how to do it with repeats, but I can't figure out how to get it without repeats

Code:
function[deck] = shuffle
%SHUFFLE shuffle shuffles the deck of cards

deck = randint(1,52,51) + 1;
return
 
Old 12-10-2005, 08:36 AM   #2
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
I don't use Matlab but you need to think about your algorithm. The probelm is that rand is not guaranteed not to repeat. (A nasty double negative there) There are numerous ways to address this some which may be more appropriate to you chosen language. However here is one.
  1. Create a sorted array with the numbers 1-52 and an empty result array
  2. Repeat until the result array has 52 entries.
    • create a random number from 1 - 52
    • Find the number in the unsorted array
    • If it is zero ignore and go to step 2
    • Else add an element with this number to the result array
    • And make the element in the sorted array zero
    • go to step 2
 
Old 12-10-2005, 01:01 PM   #3
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Okay I tried what you said and this is what I come up with, but it gets stuck in a loop somwhere.
Code:
function[deck] = shuffle
%SHUFFLE shuffle shuffles the deck of cards

a = (1:52);
deck = [];
d = randint(1,1,51) + 1;
for i = 1:52
   while a(1,d) ~= d
      d = randint(1,1,51) + 1;
   end
   if a(1,d) == d
      a(1,d) = 0;
      deck(1,i) = d;
   end
end
return
 
Old 12-10-2005, 05:25 PM   #4
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
You loop is certain not correct.

Essentially it wants to be loop until your desk is 52 in size. By the look of it you have two loops. Only one is necessary. Remember it is an array that is growing by one each time you generate a unique number.

Finally it is not a very efficient algorithm but that can be improved upon once you have teh basic approach sorted out.

graeme.
 
Old 12-12-2005, 11:39 PM   #5
kike_coello
Member
 
Registered: Jul 2005
Location: maryland
Distribution: Ubuntu 9.04
Posts: 88

Rep: Reputation: 17
i don't know if graemef's solution helped since you haven't replied but the idea is good. just gotta cum up with a good algorithm

i think you should do something like he said

1. make an array with 1 to 52 sorted
2. make an empty array of 52 elements
3. now loop for the first element in the array
4. if the number that random gives (between 1 and 52) is in the list then
copy it to the first element and make the location of the random number 0
5. now loop for next, if the random number happens to be one that has been deleted from the original array (0) then loop again to get a new random number
6. do this until the original array is full of 0's, then the second array will be full of non repeating numbers

i took matlab like 3 years ago and i haven't practiced at all after the end of that class. sorry i can't give you any code but its a very simple problem and you should be able to code it
 
Old 12-13-2005, 09:43 AM   #6
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Code:
function[deck] = q5
%Q5 q5 shuffles the deck of cards

a = (1:52); %Create a row vector with all numbers from 1 to 52
deck = []; %create an empty vector to be filled with random numbers
d = randint(1,1,52) + 1; %Create a random number between 1 and 52
for i = 1:52
   while a(1,d) ~= d %Find the random number in a and set it to zero
                     %If the random number is no longer in a, find 
                     %a new random number
      d = randint(1,1,52) + 1;
   end
   a(1,d) = 0;
   deck(1,i) = d; %Insert the random value into the out row vector
end
return
This is the code I came up with from your suggestion and it works fine. The problem in the last one I posted was that I was using rand incorrectly, because I had d = randint(1,1,51) + 1 so I was only finding random numbers between 1 and 51 and that is why it got stuck in the loop. Thanks for all your help
 
Old 02-20-2009, 11:39 PM   #7
tjudd
LQ Newbie
 
Registered: Feb 2009
Posts: 2

Rep: Reputation: 0
randperm

randperm(52) should do the trick
 
Old 02-21-2009, 06:40 AM   #8
wje_lq
Member
 
Registered: Sep 2007
Location: Mariposa
Distribution: Debian lenny, Slackware 12
Posts: 808

Rep: Reputation: 178Reputation: 178
What tjudd said. He has, with one stroke, solved lmvent's problem.

But it can't hurt to go into topic of permutations a little more deeply. I'm going to do it in C, because I've never used matlab. This will be of benefit for those who actually wish to use lmvent's solution in other languages.

lmvent's solution works, but it can be slow if you ever wish to shuffle huge arrays. What you want is an algorithm that scales well. If you're going to shuffle twice as many elements, you want the shuffling to take only twice as long. But lmvent's algorithm is proportional to the square of the number of elements. Why? Because as you go through the for loop, you'll find that the while loop takes longer and longer. That's because more and more elements in the array a have been zeroed out.

With a little more computation in your major loop, you can eliminate the minor loop (and, incidentally, the extra array) entirely. For small decks, this might increase your compute time a little, but you don't care. For large decks, the payoff will be huge.

I don't know matlab, but here's a proof of concept in C. I wrote the permutation code in a macro, so you can drop it into anything regardless of the type of your data. You can convert it into a function if you want.
Code:
#define RANDPERM(xxx_type,xxx_array,xxx_size)                  \
do                                                             \
{                                                              \
  int jndex;                                                   \
  int pick_one;                                                \
                                                               \
  xxx_type temp;                                               \
                                                               \
  for(jndex=xxx_size;                                          \
      jndex>1;     /* we need do this only xxx_size-1 times */ \
      jndex--                                                  \
     )                                                         \
  {                                                            \
    pick_one           =rand()%(jndex);                        \
    temp               =xxx_array[pick_one];                   \
    xxx_array[pick_one]=xxx_array[jndex-1];                    \
    xxx_array[jndex-1] =temp;                                  \
  }                                                            \
                                                               \
} while(0)

#include <sys/types.h>    /* for the srand() statement, if you use it */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>       /* for strcpy() and strcat(), if you use them */
#include <time.h>         /* for the srand() statement, if you use it */
#include <unistd.h>       /* for the srand() statement, if you use it */

int main(void)
{
  int jndex;

  int int_deck[52];

  long long long_long_deck[62];

  char *named_deck[52];

  /* The following line is not mandatory, but would be a good idea. */

  srand(time(NULL)+getpid());

  printf("=== part 1: integers from 1 to 52\n");

  for(jndex=0;
      jndex<52;
      jndex++
     )
  {
    int_deck[jndex]=jndex+1;
  }

  RANDPERM(int,int_deck,52);

  for(jndex=0;
      jndex<52;
      jndex++
     )
  {
    printf("%2d\n",int_deck[jndex]);
  }

  printf("=== part 2: first 62 powers of 2\n");

  for(jndex=0;
      jndex<62;
      jndex++
     )
  {
    long_long_deck[jndex]=1LL<<jndex;
  }

  RANDPERM(long long,long_long_deck,62);

  for(jndex=0;
      jndex<62;
      jndex++
     )
  {
    printf("%lld\n",long_long_deck[jndex]);
  }

  printf("=== part 3: named deck\n");

  for(jndex=0;
      jndex<52;
      jndex++
     )
  {
    named_deck[jndex]=malloc(80);

    /*
     * We'll blow up with SIGSEGV here if that failed; normally, you should
     * check it and recover.
     */

    switch(jndex%13)
    {
      case 0:
      {
        strcpy(named_deck[jndex],"Ace   of ");
        break;
      }
      case 10:
      {
        strcpy(named_deck[jndex],"Jack  of ");
        break;
      }
      case 11:
      {
        strcpy(named_deck[jndex],"Queen of ");
        break;
      }
      case 12:
      {
        strcpy(named_deck[jndex],"King  of ");
        break;
      }
      default:
      {
        sprintf(named_deck[jndex],"%-2d    of ",jndex%13+1);
      }
    }

    switch(jndex/13)
    {
      case 0:
      {
        strcat(named_deck[jndex],"Hearts");
        break;
      }
      case 1:
      {
        strcat(named_deck[jndex],"Diamonds");
        break;
      }
      case 2:
      {
        strcat(named_deck[jndex],"Spades");
        break;
      }
      case 3:
      {
        strcat(named_deck[jndex],"Clubs");
        break;
      }
      default:
      {
        /* We'll never get here. */
        abort();
      }
    }
  }

  RANDPERM(char *,named_deck,52);

  for(jndex=0;
      jndex<52;
      jndex++
     )
  {
    printf("%s\n",named_deck[jndex]);
  }

  return 0;

} /* main() */
The output of one run of the demo looked like this:
Code:
=== part 1: integers from 1 to 52
 2
26
13
43
18
42
30
27
37
51
11
48
21
16
22
32
34
36
50
49
15
19
28
14
44
47
 3
25
 6
23
46
33
38
29
52
40
20
24
17
 8
45
31
 9
39
12
 4
41
 1
 5
35
 7
10
=== part 2: first 62 powers of 2
140737488355328
67108864
8796093022208
32
1
524288
36028797018963968
536870912
1125899906842624
268435456
1048576
4398046511104
17179869184
274877906944
1099511627776
70368744177664
2
4096
1152921504606846976
288230376151711744
2147483648
16384
128
16
64
4294967296
2097152
137438953472
65536
512
2199023255552
32768
9007199254740992
281474976710656
4503599627370496
17592186044416
2048
8589934592
2251799813685248
35184372088832
562949953421312
8
68719476736
1073741824
16777216
33554432
131072
134217728
549755813888
8192
4194304
72057594037927936
18014398509481984
8388608
144115188075855872
1024
34359738368
4
256
2305843009213693952
262144
576460752303423488
=== part 3: named deck
Jack  of Clubs
3     of Hearts
7     of Hearts
5     of Hearts
6     of Spades
2     of Clubs
4     of Diamonds
9     of Spades
5     of Clubs
Jack  of Spades
Jack  of Hearts
4     of Hearts
9     of Hearts
3     of Clubs
King  of Spades
Queen of Clubs
3     of Spades
9     of Diamonds
Jack  of Diamonds
8     of Spades
Queen of Diamonds
4     of Clubs
Queen of Hearts
5     of Spades
King  of Clubs
Ace   of Diamonds
Ace   of Hearts
Ace   of Spades
King  of Diamonds
Ace   of Clubs
7     of Diamonds
6     of Clubs
King  of Hearts
6     of Diamonds
7     of Spades
Queen of Spades
6     of Hearts
3     of Diamonds
4     of Spades
8     of Clubs
10    of Diamonds
2     of Hearts
9     of Clubs
10    of Hearts
2     of Spades
7     of Clubs
8     of Diamonds
10    of Spades
2     of Diamonds
5     of Diamonds
8     of Hearts
10    of Clubs
 
Old 02-22-2009, 04:20 PM   #9
sLeeQ
LQ Newbie
 
Registered: Feb 2009
Posts: 1

Rep: Reputation: 0
Cool more on random perms

Just for variety, here is a solution in Mathematica:
RandomSample[{1, 1, 2, 3, 5, 8, 13}, 4]
will return a randomly chosen subset of the first argument (namely the first 7 Fibonacci numbers) of size given by the second argument (namely 4). None of the elements will repeat, but notice that the two 1's are indistinguishable.

-----------------------------------------------------------

And just for extra variety, here is an O-O solution in Java:
Code:
public class RandomIndeces {
	private int[] indeces;
	private int n;
	private java.util.Random randy;
	
	public RandomIndeces(int size) { 
		n=size; 
		indeces= new int[n]; 
		for (int i=0; i<n; i++) indeces[i]=i;
		randy=new java.util.Random(); 
		}
	
	public int getAnother() { 
		int i=randy.nextInt(n); 
		int idx=indeces[i];
		indeces[i]=indeces[--n];
		return idx;
		}
	
	public static void main(String[] args) {
		RandomIndeces ri= new RandomIndeces(10);
		for (int i=0; i<10; i++) 
                        System.out.println(ri.getAnother());
		}
	}
-----------------------------------------------------------

Just for PCness, wje_lq should be more perspicacious with pronouns.
I suspect tjudd might be distressed to know she was referred to as "he".
!

Last edited by sLeeQ; 02-22-2009 at 04:23 PM. Reason: detail
 
Old 02-22-2009, 05:17 PM   #10
wje_lq
Member
 
Registered: Sep 2007
Location: Mariposa
Distribution: Debian lenny, Slackware 12
Posts: 808

Rep: Reputation: 178Reputation: 178
Quote:
I suspect tjudd might be distressed to know she was referred to as "he".
Not if she's the gentleman I think she is.
 
Old 02-23-2009, 04:35 PM   #11
tjudd
LQ Newbie
 
Registered: Feb 2009
Posts: 2

Rep: Reputation: 0
Quote:
Originally Posted by wje_lq View Post
Not if she's the gentleman I think she is.
ha ha:) ok just to settle it, I am female.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
rand() and syntax error lmvent Programming 2 10-06-2005 12:21 PM
genrating -2, -1, 1, 2 woth rand() hubabuba Programming 9 08-14-2005 01:59 PM
Terminal cmd for starting Matlab M-file editor without starting matlab fubzot Linux - Software 2 02-15-2005 06:49 AM
rand() question deiussum Programming 6 11-11-2004 02:10 PM
Need help using rand() in C KneeLess Programming 12 10-01-2003 12:51 PM


All times are GMT -5. The time now is 04:58 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration