Prev: give myself an A+++ in mechanical engineering today for fixing garage door with torsion spring
Next: OPEN CHALLENGE TO CURRENT MATHEMATICS ON PRIME NUMBERS LIST
From: James Waldby on 30 May 2010 03:42
On Sat, 29 May 2010 16:10:09 -0700, tc ma wrote:
> The requirement is to find an pseudorandom integer sequence i0, i1, i2,
> i3, ... , i48, i49 so that there are at least 15 adjacent differences
> which are greater than 36.
....
[Adjacent difference like abs(a[j]-a[j+1]), j = 0 to 49,
a[j] in {1, 2, 3, ..., 50} ]
....
[snip example with 24 adjacent differences > 36]

> Is there an algorithm to find an pseudorandom integer sequence which
> meet the > requirement? > One algorithm I can think of is:
> 1. Create a not-random integer sequence which has at least 15 adjacent
> differences which are greater than 36. e.g. the above integer sequence
> alternates between a small and large integer
> 2. Randomlly select two odd-indexed integer.
> If swapping them still meet the requirement, then swap them
> 3. Randomlly select two even-indexed integer.
> If swapping them still meet the requirement, then swap them
> 4. Repeat steps 2 and 3 many times

First, re terminology: Instead of calling the result a
pseudorandom integer sequence, call it a random (or pseudorandom)
permutation. This will make explicit a requirement you implied
via example but didn't state, that all the a_j are distinct.
Also, the notation:
= |i - i |
| j - j+1|
in your post isn't useful, since the two minus signs make it look
sort of like a 2-number vector, instead of abs (i_j - i_{j+1});
notation like abs(a[j]-a[j+1]) or abs (a_j - a_{j+1}) would be
better (or at least more conventional and understandable).

Re the algorithm you state, I imagine it could easily hang up in
the sense of not making progress toward more adjacent differences
that are big differences, ie > 36. Following is some code with
which you can compare your method; it is fairly slow (averages
about 5 ms per ok random permutation on a 2 GHz machine) and
dumb but is slightly simpler than yours, in that it muddles steps
2 and 3 together and doesn't worry about odd and even swaps.

------------code begins----------------
/* Re: Random permutations of 0...49 with at least 15
adjacent differences > 36, per sci.math thread
2010/05/30 01:43:00 j-waldby
*/
#include <stdlib.h>
#include <stdio.h>
enum { N=50, D=36, M=20}; // Perm. size, Big Diff, #Big Diff

// void shoArr (int *p, int s) code goes here -- not shown

// Count adjacent-to-i big differences when v is at p[i]
int big(int *p, int i, int v) {
int k=0;
if (i>0 && abs(v-p[i-1]) > D) ++k;
if (i<N-1 && abs(v-p[i+1]) > D) ++k;
return k;
}

int main(int argc, char *argv[]) {
int d, i, j, k, p[N], r, s, t;

for (i=0; i<N; ++i) p[i] = i; // Initialize array in order

for (r=0; r<10; ++r) { // Run program 10 times

for (i=N-1; i>0; --i) { // Random-permute the array
j = random() % i;
t = p[i]; p[i] = p[j]; p[j] = t; // Swap p[i] and p[j]
}
for (k=i=0; i<N-1; ++i) // Count # of big differences
if (abs(p[i]-p[i+1]) > D) // in initial random permutation
++k;

for (s=0; s < 1e9 && k < M; ++s) {
i = random() % N;
j = random() % N;
if (abs(i-j) > 1) {
d = big(p,i,p[j]) + big(p,j,p[i]) - big(p,i,p[i]) - big(p,j,p[j]);
if (d > 0 || // d > 0 means improved count k
random() % 500 == 0) { // random allows escape from dead end
k += d;
t = p[i]; p[i] = p[j]; p[j] = t; // Swap p[i] and p[j]
}
}
}
shoArr (p, s); // Show array p with big diff elements in red
} // and iteration # s in cyan
return 0;
}
--------------code ends------------------

--
jiw
 | 
Pages: 1
Prev: give myself an A+++ in mechanical engineering today for fixing garage door with torsion spring
Next: OPEN CHALLENGE TO CURRENT MATHEMATICS ON PRIME NUMBERS LIST