2

Question spawned from this one. The problem can be formulated as follows:

Given two positive integers n and m, with m <= n, is there a way to find a suite of numbers, which cycles and covers all possible values from 0 to n?

As a basic example, if we take 3 as a number, for whatever number current between 0 and 3, we can compute the next value as:

next = (current+3) % 4

This will cycle. For instance: 1 -> 0 -> 3 -> 2 -> 1 etc. I found this solution by "chance" and it is even general ((i + n) % (n + 1) for any n), I cannot prove it mathematically. And it is a little too obvious.

Are there better ways to generate such a permutation?

Community
  • 1
  • 1
fge
  • 119,121
  • 33
  • 254
  • 329
  • 1
    What exactly do you need m for? – proskor Jan 16 '13 at 15:55
  • @proskor let's say, the initial value -- which can be determined randomly – fge Jan 16 '13 at 15:56
  • what do you mean find a "suite of numbers" which cycles and covers from 0 to n? why not just use the numbers 0...n ? Do you want it to appear random? If so I would rewrite the question as "how to generate a permutation of 0..n efficiently" – Iftah Jan 16 '13 at 15:58
  • Well, for example, incrementing the current value and calculating the remainder of the division will cycle over all values from 0 to n-1. – proskor Jan 16 '13 at 15:58
  • so the formula is next = (current + n) % (n+1) ? ... could be (current + 1) % (n+1) which is an obvious cycle (or I don't understand the question / I don't see its point) – Vinze Jan 16 '13 at 15:59
  • http://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others – Josh Lee Jan 16 '13 at 16:01
  • @Iftah good point, edited the question – fge Jan 16 '13 at 16:08
  • @Vinze well, it is a little too obvious. I know it will work, though, I just wondered if there existed better ways. – fge Jan 16 '13 at 16:11
  • You could use this sequence, but transform it into a "less obvious" one by doing a modular multiplication by any number that isn't a zero-divisor. – harold Jan 16 '13 at 16:35

2 Answers2

3

Incrementing each subsequent number by any number that does not share a common prime divisor with (n-m+1) would cover the sequence (e.g. for the sequence [2-11] (10 numbers) incrementing by 3, 7, or 9 would work but 2, 4, 5, 6, and 8 would not because they share a common divisor (2 and/or 5)

EDIT

I took out the shuffling idea since it seems that you want to increment by the same number each time. If you want a truly "random" sequence that has m at the first element just take m out and place it at the beginning. I'm not sure how that helps you, though.

D Stanley
  • 149,601
  • 11
  • 178
  • 240
  • And so you would replicate this for [0..m-1] as well? – fge Jan 16 '13 at 16:22
  • Well, actually, the thing is, I do not really want to increment by the same number each time, this makes it too "easy", so to speak. – fge Jan 16 '13 at 16:38
  • @fge if it's going to be truly stateless, the operation needs to be the same every time, doesn't it? – AakashM Jan 16 '13 at 16:44
3

I'm not sure what you intend m in the question to refer to, or how you're defining "a suite of numbers"). However, one way of getting a cycle of number is to use a recursion (or iteration) of the form:

next = f(current)

for some function f. For example, linear congruential RNGs use the iteration:

x = ( a · x + c ) mod m   where 0 < a, c < m

They don't always produce all values from 0 to m-1, but under certain circumstances they do:

c and m are relatively prime

a - 1 is divisible by every prime factor of m (not including m)

if m is divisible by 4, a - 1 is divisible by 4.

(This is the Hull-Dobell theorem.)

Note that a, c == 1 satisfies the above criteria for any m. Futhermore, if m is prime, any values of a and c satisify the criteria, and if m is a power of 2, then the criteria are satisfied by any a, c such that a == 1 mod 4 and c == 1 mod 2. However, for certain values of m (eg. 6), the only value of a which will work is 1.

This might not qualify as "stateless", but I don't think that there is any strictly stateless solution; for example, you might look for some function f such that:

f(0), f(1),... f(m-1)

is a permutation of

0, 1, ..., m-1

so that you could generate the cycle by calling f(i) for successive values of i. But that's still a state, since you have to remember the last value of i you used,

rici
  • 234,347
  • 28
  • 237
  • 341
  • `m` is supposed to be the starting point, it can be any number between `0` and `n`. As to "suite", well, I guess I could have said "sequence". – fge Jan 16 '13 at 17:10
  • @fge, with linear congruential generation, if you've got a valid (a,c) pair, you can start with any value in the range [0, n), since the cycle is complete. Other than that, I tried to explore what "stateless" might mean in an edit. – rici Jan 16 '13 at 17:11