stoopid problem

One way might be:

1) initialize array with an out-of-range number (e.g. -1)

2) for each number n 1..9
2.1) generate a random position [0:8] (pos = rand() % 9)
2.2) check if it is already filled (if( array[pos] == -1) )
2.3) if it is, pick another random position and try again
2.4) if it isn''t, store n there

It''s not very efficient, but with only 9 elements it''s ok.

thanx a ton... my programmers block is gone... how degrading... i can''t beleive i posted that question

I dunno, it's quite an interesting problem - generating a good random permutation. I don't know off hand of any optimal algorithms. For instance, neither mine nor the APs algorithm need terminate for years (although eventually they should). A better algorithm guaranteed to terminate, but not necessarily as random would be:

1) place 1-9 in the array in order
2) pick two random (integer) numbers in the interval [0:8]
3) swap the numbers at those two positions
4) loop to 2 for a fixed number of iterations

or how about:

- recursively divide the array in half (like doing a binary search)
- at each division, decide using a random binary number whether to swap the two halfs

[edited by - JuNC on July 18, 2003 11:23:51 AM]

Reducing n each time I presume. An implementation:

linked list 1..9
1) N = 9
2) select random r in [1:N]
3) walk through list r times (remove that node)
4) insert number in that node into array at [N-1]
5) N <- N - 1
6) goto 2






[edited by - JuNC on July 18, 2003 11:32:23 AM]

huh? why don't you just post

for(int x = 0; x < 9; x++)
square[x] = rand() % 9;
   

[edited by - Ruudje on July 18, 2003 11:39:17 AM]

[edited by - Ruudje on July 18, 2003 11:39:37 AM]

You didn''t read the OP did you

bool filled[9];
int numbers[9];

memset(filled,0,sizeof(bool)*9);

for(int i = 0; i < 9; ++i)
{
  int r = rand() % 9;
  while(filled[r])
    r = rand() % 9;
  numbers[i] = r;
}

NOTE: I haven''t tested this yet, but it seems sound

That''s my first one, only using a second array instead of an out-of-range number

Here is a much more efficient way to generate an array of random numbers:

for ( int i = 0; i < N; i++ )
{
    array[ i ] = i;
}
for ( int j = 0; j < N; j++ )
{
    swap( array[ j ], array[ rand()%N ] );
}   

[edited by - JohnBolton on July 18, 2003 4:15:43 PM]

quote:

---

Original post by JuNC
One way might be:

1) initialize array with an out-of-range number (e.g. -1)

2) for each number n 1..9
2.1) generate a random position [0:8] (pos = rand() % 9)
2.2) check if it is already filled (if( array[pos] == -1) )
2.3) if it is, pick another random position and try again
2.4) if it isn't, store n there

It's not very efficient, but with only 9 elements it's ok.

---

Modify 2.3 to read: if it is, walk the array until an unfilled position is found. while( array[pos] == -1 ) { pos = ( ++ pos ) % n);

Worst case is ( 1 + 2 + 3 + .. + n ), best case is n.


I like pie.

[edited by - RenderTarget on July 18, 2003 5:33:07 PM]

Yep, RenderTarget, that ones pretty good (although it's while(array[pos] != -1) . I worked that one out when I went away and actually implemented all of these to see how well they worked.

JohnBolton: again, a neat solution, similar to my 'pick two randoms'.

Anyone know of methods to compare the 'randomness' of these algorithms? Is it possible they are all equally as random, even though some are more efficient than others (either space or time)? Anyone have any links to research on this matter (mostly on *how* they compared them rather than actual results, it seems likely there is research being that it's quite an elementary problem).

[edited by - JuNC on July 18, 2003 7:12:22 PM]

quote:

---

Original post by JohnBolton

for ( int i = 0; i < N; i++ )
{
    array[ i ] = i;
}
for ( int j = 0; j < N; j++ )
{
    swap( array[ j ], array[ rand()%N ] );
} 

---

Seconded.

hm. its relatively easy. for each element, generate a random number, and reiterate through what you have gone through the array and check if that number is there. if so, then generate a new random number, reiterate through what you have gone throug hthe array and check if that number is used. if so, then generate a new random number, reiterate through what you have gone through the array and check if that number is used. if so.. etc you get the idea. .

quote:

---

Original post by Anonymous Poster
...but it doesn''t allow the 1^st position to be a one, the 2^nd a 2, etc.

---

Where''d you get this idea? rand()%N has as much chance of equalling j as any other integer in [0, N).

quote:

---

Anyone know of methods to compare the ''randomness'' of these algorithms?

---

Strange Attractors, although 9 numbers is rather too few to make use of them. However, if you extend the scope of your PRNG to 1000''s of numbers, then you can test each algo.

For an example, see this paper

How is this approach?

int a[9] = {1,2,3,4,5,6,7,8,9};
int s[9];  // array to be filled

for(int n=8; n>=0; n--)
{
    int i = rand()%(n+1);
    s[n] = a;
    a[i] = a[n];
}
 

I have not tested this code. But I once used this algo to generate about 50 random consecutive integers.

xf00f: Thats an interesting article, I''m not 100% sure on how to map those ideas onto a statistical test on a set of sequences generated by one of these algorithms. I''m gonna have a think about it tho.

Cipher3D: that algorithm was already presented by RenderTarget.

Peter19852001: hmm, a direct implementation of that algorithm doesn''t do anything (array of 0''s), but I''m too knackered right now to find out why.

Perhaps we should just save ourselves the trouble, and use random_shuffle. The standard states that its complexity is 'exactly (last - first) - 1 swaps.' I've read an implementation of random_shuffle; it's functionally very similar to the second loop in JohnBolton's code, but it (effectively) starts iterating from j = 1.

EDIT: I misread it; there's another difference. JohnBolton's code swaps the jth element with a random element with an index in the range [0, N), but the random_shuffle code swaps the jth element with a random element with an index in the range [0, j].

[edited by - Beer Hunter on July 20, 2003 6:25:16 PM]

in some implementations of STL there's a function that fills a container with a sequence of numbers, std::iota()

http://www.sgi.com/tech/stl/iota.html

if you don't have that std algorithm, don't sweat it. it's not part of the standard and you can mimick it with that simple loop posted before. just write it yourself and call it iota if you like there's an example in Breymanns: Designing components for the C++ STL. it goes like this:

namespace br_stl {
template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
while(first != last)
*first++ = value++; // now when I'm looking at it, why is he post-incrementing?

}
}

Then you have the std::random_shuffle() to shuffle the elements.

http://www.sgi.com/tech/stl/random_shuffle.html

int main()
{
  vector<int> square(9);

  iota(square.begin(), square.end(), 1);
  random_shuffle(square.begin(), square.end()); // NEW!

/*
oh and yes you can use an array too:
version 1:
  int square[9]; 
  iota(square, square+9, 1); // or iota(□[0], □[9], 1); if you prefer
  random_shuffle(square, square+9); // or random_shuffle(□[0], □[9]);

version 2:
  int square[9] = { 1,2,3,4,5,6,7,8,9 };
  random_shuffle(square, square+9);

*/

  copy(square.begin(), square.end(), ostream_iterator<int>(cout, " "));
  cout << endl; 
}

it does exactly the same as the stuff posted, but... why reinvent the wheel?

"No lies of sugar can sweeten the sournes of reality"

}+TITANIUM+{ A.K.A. DXnewbie[onMIRC]

[edited by - Seriema on July 20, 2003 7:27:27 PM]