6

I am trying to study the reordering of sequences. I am having difficulties finding any learned articles, probably because I don't know the key words to search for. I hope if I can describe what I want to do someone can can expand my knowledge or name what I am doing so I can research it myself.

I want to define a reordering of a sequence in a form that can be coded easily. Here I will use $S(...)$.

I start with the most simple integer sequence.

$1,2,3,4,5,...$

Perhaps I want to swap pairs of them to become:

$2,1,4,3,6,5,... = S(3,-1)$ meaning skip forward 3, then skip back 1 and repeat.

or reverse triplets

$3,2,1,6,5,4,9,... = S(5,-1,-1)$ meaning skip forward 4, then skip back 1, and once more back 1 and repeat.

or something more complicated like

$5,4,2,3,1,10,9,7,8,6,15... = S(9,-1,-2,1,-2)$

so I define a function $S(...)$ that can do that which takes as parameters as the sequence of steps in the original sequence to make the new one (I haven't explained that very well but bear with me).

Now clearly I can code S without difficulty, I just need to retain enough history of the incoming sequence to jump back and forward as directed.

Is there a name for this function $S$ or something similar? Is there a way of examining the parameters of S to determine whether the resulting sequence:

  1. emits all of the original sequence
  2. does not emit duplicates

For example, $S(2,-1)$ would produce the sequence $2,1,3,2,4,3,...$ which is not acceptable because 2 gets repeated. And $S(2)$ would generate $2,4,6,8,...$ which skips some and is also not acceptable.

Is there a way of generating these orderings? There is clearly a null form $S(1)$ which could be considered the first.

Added

This process is manipulating an infinite sequence by applying $S$ repeatedly. The two requirements apply to the whole infinite sequence generated. So, for example $S(24,-23)$ is invalid because eventually a duplicate will arise even though the first iteration does not.

OldCurmudgeon
  • 585
  • I think you have an error in the case $S(4,-1,-1)$. as $1+4=5$, not $6$. Can you confirm? – Isaac Browne May 26 '17 at 13:38
  • @IsaacBrowne - You are correct - it should be $S(5,-1,-1)$ - fixed, thanks. – OldCurmudgeon May 26 '17 at 13:42
  • The first thing I would notice then, is that for $S(x_1,x_2,...,x_n)$, the sum of the parameters must be $\sum_{i=1}^nx_i=n$ in order to cycle through all numbers. If it were less than $n$, we would have repeated numbers, and if it were greater than $n$, we would skip some numbers. Note that this may not be a sufficient condition, but it is a necessary one. – Isaac Browne May 26 '17 at 13:45
  • One key word to look for is the Symmetric Group https://en.wikipedia.org/wiki/Symmetric_group, another is Permutation https://en.wikipedia.org/wiki/Permutation. Interestingly, the mathematical theory of the symmetric group underlies the old tradition of ringing the changes https://en.wikipedia.org/wiki/Change_ringing, where the important thing was to carefully go through all possible permutations (with some restrictions to avoid exhaustion of the change ringers). – Lee Mosher May 26 '17 at 14:09
  • @LeeMosher - Thanks, I'll look that up - BTW change ringing only ever swaps two bells (except on a bob) so although similar it is not a complete match. There are also echoes of grey coding too. – OldCurmudgeon May 26 '17 at 14:16
  • 1
    Regarding swapping two bells, the corresponding theorem about finite symmetric groups is that the set of "two position swaps", known as transpositions, is a generating set for any finite symmetric group. That's what guarantees the possibility of going through all possible changes. – Lee Mosher May 26 '17 at 14:29

1 Answers1

2

Given $S(a_1,\ldots,a_n)$ we can determine if it generates all integers starting from $s$ by verifying $\displaystyle \sum_{k=1}^n a_k = n$ and that $\displaystyle f(i) = \sum_{k=1}^i a_k$ takes on every residue $\bmod n$ exactly once.

Effectively, $S(a_1,\ldots,a_n)$ is the first difference of $(f(0), f(1), \ldots,f(n))$. For example for $S(3, -1)$ we have $(0, 3, 2)$. In this format the first integer is always $0$ and the last integer is always $n$.

Now, to generate these, we first pick an $n$. Let's say $n = 5$. We then can choose an arbitrary permutation of the residues $\mod 5$, with the condition that the first element must be $0$ and then append $5$ as the last element:

$$(0,4,1,2,3,5)$$

Since only the residues must hold we can also add multiples of $n$:

$$(0,4,26,2,3,5)$$

Now if we delta encode this list, we have a valid $S$:

$$(0,4,26,2,3,5) \rightarrow S(4,22,-24,1,2)$$

orlp
  • 10,508
  • Surely $S(4,22,−24,1,2)$ would repeat. The first $22$ would emit 26 and some subsequent iteration may touch $26$ again. I'm looking for a transform of the whole (possibly infinite) sequence into a different order without duplicating or skipping any. – OldCurmudgeon May 26 '17 at 14:11
  • 2
    @OldCurmudgeon You're mistaken, it does not repeat. The first 100 numbers of $S(4, 22, -24, 1, 2)$ are $1, 5, 27, 3, 4, 6, 10, 32, 8, 9, 11, 15, 37, 13, 14, 16, 20, 42, 18, 19, 21, 25, 47, 23, 24, 26, 30, 52, 28, 29, 31, 35, 57, 33, 34, 36, 40, 62, 38, 39, 41, 45, 67, 43, 44, 46, 50, 72, 48, 49, 51, 55, 77, 53, 54, 56, 60, 82, 58, 59, 61, 65, 87, 63, 64, 66, 70, 92, 68, 69, 71, 75, 97, 73, 74, 76, 80, 102, 78, 79, 81, 85, 107, 83, 84, 86, 90, 112, 88, 89, 91, 95, 117, 93, 94, 96, 100, 122, 98, 99$. Every integer bigger than $22$ occurs in this list. – orlp May 26 '17 at 14:23
  • Good point - I notice though that it misses some, I don't see $7,12,17,22,...$ - Opps - sorry, I missed your extra note at the end. – OldCurmudgeon May 26 '17 at 14:29