Terry Jones wrote:
> I was not meaning to say that anyone was wrong, just that I found Greg's
> characterization a bit too general, or not as well defined as it might have
> been.
I meant it in the context being discussed, which was a
shuffling algorithm being used the way shuffling algorithms
ar
Dan Christensen wrote:
> I think Terry's point is valid. While no one call to
> random.shuffle(L) can produce every possible ordering of L (when
> len(L) is large), since random.shuffle shuffle's the data in place,
> repeated calls to random.shuffle(L) could in principle produce every
> possible
> "Dan" == Dan Christensen <[EMAIL PROTECTED]> writes:
Dan> Greg Ewing <[EMAIL PROTECTED]> writes:
>> Terry Jones wrote:
>>
>>> The code below uses a RNG with period 5, is deterministic, and has one
>>> initial state. It produces 20 different outcomes.
>>
>> You misunderstand what's meant by
Greg Ewing <[EMAIL PROTECTED]> writes:
> Terry Jones wrote:
>
>> The code below uses a RNG with period 5, is deterministic, and has one
>> initial state. It produces 20 different outcomes.
>
> You misunderstand what's meant by "outcome" in this
> context. The outcome of your algorithm is the whole
[Raymond Hettinger]
> I think the note is still useful, but the "rather small" wording
> should be replaced by something most precise (such as the
> value of n=len(x) where n! > 2**19997).
Note that I already removed it, and I'm not putting it back. The
period of W-H was "so short" you could get
Terry Jones wrote:
> The code below uses a RNG with period 5, is deterministic, and has one
> initial state. It produces 20 different outcomes.
You misunderstand what's meant by "outcome" in this
context. The outcome of your algorithm is the whole
*sequence* of numbers it produces, not each indiv
On 12 Jun 2006, at 02:19, Terry Jones wrote:
>> "Greg" == Greg Ewing <[EMAIL PROTECTED]> writes:
>
> Greg> Terry Jones wrote:
>>> Suppose you have a RNG with a cycle length of 5. There's nothing
>>> to stop an
>>> algorithm from taking multiple already returned values and
>>> combining the
Alex Martelli wrote:
>...claims:
>
>Note that for even rather small len(x), the total number of
>permutations of x is larger than the period of most random number
>generators; this implies that "most" permutations of a long
>sequence can never be generated.
>
>Now -- why would the behavior of "mos
[Terry Jones]
> The code below uses a RNG with period 5, is deterministic, and has one
> initial state. It produces 20 different outcomes.
Well, I'd call the sequence of 20 numbers it produces one outcome.
>From that view, there are at most 5 outcomes it can produce (at most 5
distinct 20-number s
> "Greg" == Greg Ewing <[EMAIL PROTECTED]> writes:
Greg> Terry Jones wrote:
>> Suppose you have a RNG with a cycle length of 5. There's nothing to stop an
>> algorithm from taking multiple already returned values and combining them
>> in some (deterministic) way to generate > 5 outcomes.
Greg
Terry Jones wrote:
> Suppose you have a RNG with a cycle length of 5. There's nothing to stop an
> algorithm from taking multiple already returned values and combining them
> in some (deterministic) way to generate > 5 outcomes.
No, it's not. As long as the RNG output is the only input to
the alg
[Greg Ewing]
> But isn't the problem with the Twister that for *some
> initial states* the period could be much *shorter* than
> the theoretical maximum?
>
> Or is the probability of getting such an initial state
> too small to worry about?
The Twister's state is held in a vector of 624 32-bit wor
> "Greg" == Greg Ewing <[EMAIL PROTECTED]> writes:
Greg> A generator with only N possible internal states can't
Greg> possibly result in more than N different outcomes from
Greg> any algorithm that uses its results.
I don't mean to pick nits, but I do find this a bit too general.
Suppose you
Terry Jones wrote:
> That doc note should surely be removed. Perhaps it's an artifact from some
> earlier shuffle algorithm.
>
> The current algorithm (which is simple, well known, and which produces all
> permutations with equal probability) only calls the RNG len(x) - 1 times.
It's not a matte
Tim Peters wrote:
> Off the top of my head, then, since the Twister is provably
> equidistributed in 623 dimensions to 32-bit accuracy, I expect it
> should be able to "fairly" generate all permutations of a sequence of
> <= 623 elements (equidistribution in N dimensions implies
> equidistribution
Robert Kern wrote:
> OTOH, isn't the exact PRNG algorithm considered an implementation detail?
It's questionable whether the PRNG being used *should* be
an implementation detail. To anyone who cares even a little
bit about its quality, knowing the algorithm (or at least
some info about it, such a
> "Tim" == Tim Peters <[EMAIL PROTECTED]> writes:
Tim> [Terry Jones]
>> and which produces all permutations with equal probability)
Tim> That needs proof. Assuming a true random number generator, such a
Tim> proof is easy. Using a deterministic PRNG, if the period is "too
Tim> short" it's de
[Terry Jones]
> That doc note should surely be removed. Perhaps it's an artifact from some
> earlier shuffle algorithm.
No, it's an artifact form an earlier PRNG. The shuffle algorithm
hasn't changed.
> The current algorithm (which is simple, well known,
Both true.
> and which produces all pe
That doc note should surely be removed. Perhaps it's an artifact from some
earlier shuffle algorithm.
The current algorithm (which is simple, well known, and which produces all
permutations with equal probability) only calls the RNG len(x) - 1 times.
Terry
___
On Jun 10, 2006, at 1:08 PM, Josiah Carlson wrote:
> Josiah Carlson <[EMAIL PROTECTED]> wrote:
>>
>> Alex Martelli <[EMAIL PROTECTED]> wrote:
>>>
>>> ...claims:
>>>
>>> Note that for even rather small len(x), the total number of
>>> permutations of x is larger than the period of most random numbe
[Alex Martelli]
> ...claims:
>
> Note that for even rather small len(x), the total number of
> permutations of x is larger than the period of most random number
> generators; this implies that "most" permutations of a long
> sequence can never be generated.
>
> Now -- why would the behavior of "mos
Alex Martelli wrote:
> ...claims:
>
> Note that for even rather small len(x), the total number of
> permutations of x is larger than the period of most random number
> generators; this implies that "most" permutations of a long
> sequence can never be generated.
>
> Now -- why would the behavior
Josiah Carlson <[EMAIL PROTECTED]> wrote:
>
> Alex Martelli <[EMAIL PROTECTED]> wrote:
> >
> > ...claims:
> >
> > Note that for even rather small len(x), the total number of
> > permutations of x is larger than the period of most random number
> > generators; this implies that "most" permutatio
Alex Martelli <[EMAIL PROTECTED]> wrote:
>
> ...claims:
>
> Note that for even rather small len(x), the total number of
> permutations of x is larger than the period of most random number
> generators; this implies that "most" permutations of a long
> sequence can never be generated.
[snip]
> I
...claims:
Note that for even rather small len(x), the total number of
permutations of x is larger than the period of most random number
generators; this implies that "most" permutations of a long
sequence can never be generated.
Now -- why would the behavior of "most" random number generators be
25 matches
Mail list logo
