Hello.I'm a begginer in C++.
I'm trying to make an algorithm that will shuffle randomly the elements of a
matrix[4][3],but i don't know how to start...
Can someone help me with the algorithm ?
I think is something like this but i'm not sure :
bool test=false;
int x;
x=rand()%4;
while(test=false)
{if(x==0)
{...
test=true;}
if(x==1)
{...
test=true;}
if(x==2)
{...
test=true;}
if(x==3)
{...
test=true;}
}... -> mean that i don't know what to write there
Take each element of your array in turn, and swap it with a randomly chosen element with a position that is >= the one you're swapping. Note that this raises the possibility that an element may be swapped with itself; if it is, that's equivalent to leaving that element alone.
It should be easy to see that after this is done, the first element can be swapped with any element in the array with equal probability. Applying this argument inductively shows that each element has equal probability of winding up in any spot in the array.
Just some skeleton to help you visualize whats been said above :
for row = 0 to ROW_SIZE
for col = 0 to COL_SIZE
int rowToSwap = a random valid row
int colToSwap = a random valid col
swap array[row][col] with array[rowToSwap][colToSwap]#include<iostream>
using namespace std;
int a[4][3], aux,i,j;
int main ()
{for ( i=0;i<4;i++)
for ( j=0;j<3;j++)
{
cout<<"a["<<i+1<<","<<j+1<<"]=";cin>>a[i][j];
}
int tempRow=rand()%4;
int tempCol=rand()%3;
for(i=0;i<4;i++)
for(j=0;j<3;j++)
{aux=a[i][j];
a[i][j]=a[tempRow][tempCol];
a[tempRow][tempCol]=aux;}
for(i=0;i<4;i++)
for(j=0;j<3;j++)
cout<<a[i][j]<<endl;
system("Pause");
return 0;}I made the algorithm above using your ideas but it's always displaying this matrix :
| 6 1 2 |
| 3 4 12 |
| 5 7 8 |
| 9 10 11|
The matrix which I introduce is :
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |
|10 11 12 |
i think you need to seed rand.
something like
srand(time(NULL));Just some skeleton to help you visualize whats been said above :
for row = 0 to ROW_SIZE for col = 0 to COL_SIZE int rowToSwap = a random valid row int colToSwap = a random valid col swap array[row][col] with array[rowToSwap][colToSwap]
This is not quite right: You need to restrict the swapping so that the destination position is always >= the source position.
int rowToSwap = a random valid row that is >= row
int colToSwap = rowToSwap == row?
a random valid row that is >= col :
a random valid rowTo see why, consider what happens if there are only two elements in the array using the original strategy. We look at the first element and swap it with the second with probability 0.5. Then we look at the second and swap it with the first with probability 0.5. The net effect is to keep the original ordering 3/4 of the time. Not a random distribution.
If you are trying to implement arkoenig's method, as I understand it, since you have 12 numbers, you would want to make sure you generate random index(es) exactly 12 minus 1 = 11 times. That means you should be calling rand() from inside a loop. Make sure your code does this.
This is not quite right: You need to restrict the swapping so that the destination position is always >= the source position.
int rowToSwap = a random valid row that is >= row int colToSwap = rowToSwap == row? a random valid row that is >= col : a random valid rowTo see why, consider what happens if there are only two elements in the array using the original strategy. We look at the first element and swap it with the second with probability 0.5. Then we look at the second and swap it with the first with probability 0.5. The net effect is to keep the original ordering 3/4 of the time. Not a random distribution.
Oh I see. But if the probability of swapping is 0.5 per say, then the probability of swapping 2 times in a row is 0.5*0.5 = 0.25? So isn't the probability of keeping the original order 1/4? But either way its not equal distribution. So I see your point. Is there a induction proof on the equal random distribution on this method? Just curious.
This is not quite right: You need to restrict the swapping so that the destination position is always >= the source position.
int rowToSwap = a random valid row that is >= row int colToSwap = rowToSwap == row? a random valid row that is >= col : a random valid rowTo see why, consider what happens if there are only two elements in the array using the original strategy. We look at the first element and swap it with the second with probability 0.5. Then we look at the second and swap it with the first with probability 0.5. The net effect is to keep the original ordering 3/4 of the time. Not a random distribution.
But, since the array contains 12, no need to consider the 2-element problem. If there is a chance of a 2-element array (say via user input for size) it then becomes important. And the simple fix is to just go through elements-1 rather than all that testing because the only thing that testing does is remove the last element from being randomized, doesn't it?.
Although, looking at your algorithm:
int rowToSwap = a random valid row that is >= row
int colToSwap = rowToSwap == row?
a random valid row that is >= col :
a random valid rowhow can you really assign colToSwap to a valid row? you have a major chance to blow your array if #cols < #rows, and completely ignoring values if #cols > #rows even more than your algo already does. So it only works on square matrices.
The multi-dimensional aspect tends to add a potential layer of confusion. Make it a regular old one dimensional 12 element array and shuffle THAT.
int a[4][3];
int* array = (int*) (&a[0][0]);Now shuffle array and a will be shuffled.
>> Take each element of your array in turn, and swap it with a randomly chosen element with a position that is >= the one you're swapping.
Generating and testing whether randomly generated indexes are "greater than or equal to" other indexes is now easier and any algorithm issues regarding whether the array is square no longer arise.
:icon_rolleyes: Oh ghod! :icon_rolleyes:
loop r from 0 to rowmax-1
loop c from 0 to colmax-1
row = random (0 - rowmax-1)
col = random (0 - colmax-1)
swap array(r,c) and array(row,col)
endloop
endlooploop r from 0 to rowmax-1 loop c from 0 to colmax-1 row = random (0 - rowmax-1) col = random (0 - colmax-1) swap array(r,c) and array(row,col) endloop endloop
That's not really following arkoenig's algorithm anymore, but that shuffles the array and is straight-forward and pretty easy to implement, so that's a good solution.
that shuffles the array and is straight-forward and pretty easy to implement, so that's a good solution.
It is straight-forward and pretty easy to implement, but it is not a correct solution.
There are N! ways of arranging a sequence of N elements. A random shuffle should yield uniformly distributed results; that is, the probability of any particular ordering is 1/N!. There are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but do not in fact produce a uniform distribution over the N! possible orderings. It is easy to write the random shuffle naively and get it wrong.
The Art of Computer Programming, Vol. 2, section 3.4.2 “Random sampling and shuffling”, Knuth describes two (correct) algorithms:
a. If the number of items to sort is small, then simply put all possible orderings in a table and select one ordering at random. In this particular case the table would need 12! rows.
b. “Algorithm P” which Knuth attributes to Moses and Oakford (1963), but is now known to have been anticipated by Fisher and Yates (1938); the 'Fisher–Yates shuffle' http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
always selecting j from the entire range of valid array indexes on every iteration also produces a result which is biased, albeit less obviously so. This can be seen from the fact that doing so yields n^n distinct possible sequences of swaps, whereas there are only n! possible permutations of an n-element array. Since n^n can never be evenly divisible by n! when n>2 (the latter is divisible by n−1, which shares no prime factors with n), some permutations must be produced by more of the n^n sequences of swaps than others. - from the wiki article
Just use the C++ random_shuffle, its been tested for its distribution so its most likely good enough.
b. “Algorithm P” which Knuth attributes to Moses and Oakford (1963), but is now known to have been anticipated by Fisher and Yates (1938); the 'Fisher–Yates shuffle' http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
I believe the algorithm I suggested is equivalent to the one shown on this page under the heading "The Modern Algorithm."
I used the random_shuffle and it works better.(Thanks firstPerson for the idea)
The elements are now shuffled but is still a problem.Instead of 11 it appears 4. Why doesn't appear 11 ?
The matrix i introduce is {1,2,3,4,5,6,7,8,9,10,11,12}
The matrix displayed is : {4,2,10,3,1,12,8,4,5,7,9,6}
#include <iostream>
using namespace std;
int a[4][3];
int i,j;
int main() {
for (i = 0; i <4; ++i)
for(j=0;j<3;j++)
{ cout<<"a["<<i+1<<"]["<<j+1<<"]= ";
cin>>a[i][j];}
random_shuffle(&a[0][0], &a[4][3]);
for (i = 0; i < 4; ++i)
for(j=0;j<3;j++)
cout << a[i][j] << " ";
system("Pause");
return 0;
}Hey people, this is a beginner learning how to use the C++ language. He is not a math major trying to analyze and implement the absolute best randomly distributed matrix possible. I gave a new programmer's algorithm, one that will suffice for homework, not a mathematically perfect distribution. That is above the needs for a beginning programming class.
Note, the first post states
Hello.I'm a begginer in C++.
It does not say
I am in an advanced mathematical theory course.
Help posters at the appropriate level, please. Higher math is unnecessary.
I gave a new programmer's algorithm, one that will suffice for homework, not a mathematically perfect distribution. That is above the needs for a beginning programming class.
I completely disagree. As a practical matter, whether the original algorithm suffices for homework depends on the instructor. If I were the instructor, it certainly would not suffice.
As a philosophical matter, I think that as a general rule, it's a bad idea to advocate solutions that don't solve the stated problem correctly, and an even worse idea to do so without pointing out that the solution is oversimplified and doesn't actually yield the right answer.
As for the use of random_shuffle, I have three comments:
1) I didn't recommend it because I assumed that the OP would have used it if permitted.
2) Even if not, random_shuffle is geared toward linear data structures, not rectangular ones. It is true that you can treat an array of arrays as a linear data structure, but I believe that the subtleties of doing so are even greater than the subtleties of getting the code right in the first place. In fact...
3) The call to random_shuffle in the previous example is just plain wrong, for two reasons:
3a) The indices are wrong. If you want to use random_shuffle on the whole array, you have to pass an address that is one past the last element. That is &a[3][3], not &a[4][3]. Think about it.
3b) Unfortunately, even computing &a[3][3] yields undefined behavior because it evaluates a[3][3] in order to take its address. It shouldn't be undefined, but it is. So to do it right, you have to pass &a[3]+3:
random_shuffle(&a[0][0], a[3]+3);@OP: maybe you should use a 1D array to implement a 2D array, using the index conversion, ROW_SIZE*row_index + col_index
To the OP. If you go with random_shuffle (or even if you don't), don't forget to seed the Random Number Generator as mentioned earlier in the thread.
As to why you have to go one PAST the end of the array, see this:
http://www.cplusplus.com/reference/algorithm/random_shuffle/
Parameters
first, last
Forward iterators to the initial and final positions of the sequence to be shuffled. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
So in your function call, you go one past the end of your array.
As a side note, arkoenig's call:
random_shuffle(&a[0][0], a[3]+3);is the same as this:
random_shuffle(&a[0][0], (&a[0][0]) + 12);Finally I made the algorithm with your help.
Thanks everyone for your ideas.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.