Odd Sequence (Algorithm?)

General Questions
#1

I’ve got some code that calculates the following sequence:

topID = 0
topID = 1
topID = 2
topID = 3
topID = 10
topID = 20
topID = 30
topID = 11
topID = 21
topID = 31
topID = 12
topID = 22
topID = 32
topID = 13
topID = 23
topID = 33
topID = 100
topID = 200
topID = 300
topID = 110
topID = 210
topID = 310
topID = 120
topID = 220
topID = 320
topID = 130
topID = 230
topID = 330
topID = 101
topID = 201
topID = 301
topID = 111
topID = 211
topID = 311
topID = 121
topID = 221
topID = 321
topID = 131
topID = 231
topID = 331
topID = 102
topID = 202
topID = 302
topID = 112
topID = 212
topID = 312
topID = 122
topID = 222
topID = 322
topID = 132
topID = 232
topID = 332
topID = 103
topID = 203
topID = 303
topID = 113
topID = 213
topID = 313
topID = 123
topID = 223
topID = 323
topID = 133
topID = 233
topID = 333
topID = 1000
topID = 2000
topID = 3000
topID = 1100
topID = 2100
topID = 3100
topID = 1200
topID = 2200
topID = 3200
topID = 1300
topID = 2300
topID = 3300
topID = 1010
topID = 2010
topID = 3010
topID = 1110
topID = 2110
topID = 3110
topID = 1210
topID = 2210
topID = 3210
topID = 1310
topID = 2310
topID = 3310
topID = 1020
topID = 2020
topID = 3020
topID = 1120
topID = 2120
topID = 3120
topID = 1220
topID = 2220
topID = 3220
topID = 1320
topID = 2320
topID = 3320

It is however pretty ugly code. Is this any sort of normal sequence and is there any short way of calculating it? I’m currently doing it all through adds, shifts, and binary operators.

The sequence itself is essentially the mapping to a leaf in a tree. The above would be for a tree with four nodes at each branch and new branches/leaves are made based on the mapping. The goal is to have the mapping work in such a manner that any new leaf has all four slots filled before allocating memory for a new leaf. When all current-layer leaves are filled, one slot in one leaf is converted to a node pointer and the current item moved into the sub-leaf, ad infitum.

Simply incrementing the key (i.e. 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, …) will work fine and keeps the tree of even-depth but means that up to almost four times the needed memory can be allocated, while as the above sequence causes there to be only +3 empty slots as worst case (assuming I have it right…)

#2

I’ve only given it a cursory scan, but it looks like you’re counting in ternary and writing the numbers right-to-left.

#3

That was my first thought, but I’m not sure it’s that simple…

#4

You’re right, it’s not exactly, but it’s pretty close (if you use base 4; after all, they don’t have the digit 3 in base 3).

It really looks like counting in base 4 written right-to-left with 0x > x.

#5

Can you explain what you mean by 0x > x ? I still can’t see a proper sequence in there

#6

It is essentially base 4 counting (though the real version of the code will be 32 or 64 base though it could be anything), but simply numbering left to right would be:

0
1
2
3
01
11
21
31
02

which is quite different from my sequence. That goes:

0
1
2
3
10
20
30
11
21

And I think what ultrafilter means by 0x > x would be that 01 > 1, 02 > 2, and so on. Reversed order numbering.

To try and show it as a tree a bit better:


One leaf (top node)
00
01
02
03

One subleaf
-->00
   10
   20
   30
01
02
03

Two subleafs
-->00
   10
   20
   30
-->01
   11
   21
   31
02
03

With the above showing how the map goes to the proper place in the tree.

#7

hrmm… one way to do it for, is:



List<int> topIDList;
for(int i = 1; i < 100; i++)
    List newTopIDList;
    for(int j = 1; j < 4; j++)
        foreach (int n in topIDList)
            String newTopIDString;
            sprintf("%d%0id, newTopIDString);
            newTopIDList.Add(int.Parse(newTopIDString));
    topIDList.Append(newTopIDList);

the sprintf bit is a bit tricky, you would probably have to manually make the format string making liberal use of escape charecters. The algorithm basically works by noting that each larger length of strings is just a 1, 2 or 3 appended onto the previous strings.

#8

Uh, duhh… It would help if I included the arguments to the sprintf properly



String newTopIDFormat = "\%d\%0" + i + "d"; //eg, for i = 4, it is "%d%04d
sprintf(newTopIDString, newTopIDFormat, j, n); //So for j = 2, n = 23, it would be 20023
#9

The mappings are bitmasks, but really the main problem with that method is that you would need to store every string you had ever created–and the structure is intended to hold up to the limit countable in a 32 or 64 bit value (so four billion or more.)

#10

This is a reordered base-4 counting system. One way to describe it is: leading zeroes stripped, sorted primarily by length and then lexicographically on the reverse-ordered string. I’m not sure how helpful that is though.

More helpful for counting with these numbers is that within a set of same-length keys, the first digit is counting base-3 (base-4 but skipping zero) and the remaining digits are normal base-4 counting, written least-significant-digit first.

I’m not sure whether this code is any prettier than what you’ve got, but it’s quick anyway.


typedef long KeyInt;
// or long long, or whatever; digits are stored in 2-bit pairs of KeyInt
struct key { KeyInt n; int l; };

void init( struct key *k ) { k->n = 0; k->l = 1; }
void print( struct key* k ) {
  int i, n;
  for ( i = 0, n = k->n; i < k->l; ++i, n >>= 2 ) printf( "%d", n&3 );
}

void inc( struct key *k  ) {
  // increment low-order digit, base 3
  k->n++;
  if ( !(k->n & 3) ) k->n++;

  // check for carry out; increment length if present
  KeyInt co = 1 << k->l*2;
  if ( k->n & co ) { k->n -= co; k->l++; }
}

int main( int argc, char** argv ) {
  int n;
  struct key K;
  init(&K);
  for ( n = 0; n < 100; ++n ) {
    printf( "%4d: ", n );
    print(&K);
    printf( "
" );
    inc(&K);
  }
}

It’s easy to get arbitrary elements of the sequence, too; you don’t have to increment if all you want is the nth element. But it sounds like you’re always using these in sequence, so that’s probably not important to you.

#11

Hm… I’ll need to look that over in the morning. Certainly smaller than what I had (and will probably be :smack:-inducing when I do.)

#12

Ok, so the one that doesn’t require you to store the results would be:




int nextTopID (int curTopID)
    return int.Parse(_nextTopID(cur.ToString());

String _nextTopID(String curTopIDStr)
{
    foreach (char c in curTopIDStr)
        if (c != 3) //check if we overflow to the next digit
            break;
        return "1" + "0".repeat(curTopIDStr.Length);
    if(curTopIDStr[0] == "3")
        return ("1" + nextTopID(curTopIDStr[1..]);
    else
        curTopIDStr[0]++;
        return curTopIDStr;
}

curTopIDStr[1…] means take the substring from 1 to the end. Just assume the language does automatic casting between strings and ints. I know no language does but it makes the code clearer. Theres a bit of subtlety to the string formatting in that you need to preserve leading zeros though when you convert nextTopID back into and int.

It’s the same basic principle as the earlier one only made recursive rather than using dynamic programming. It has to manually compute the next increment rather than pulling it from a precomputed array.

#13

I’m not sure I understand the notation you’re using; but given an input of 330, won’t this return 111 instead of 101?

_nextTopID(“330”)
-> “1” + _nextTopID(“30”)
-> “1”+“1”+_nextTopID(“0”)
-> “1”+“1”+“1” = “111”.

In the OP, the first digit behaves differently from the rest.

#14

Ah good point. You would have to write a special case for the first digit. I missed that.



int nextTopID (int curTopID)
    return int.Parse(_nextTopID(cur.ToString(), true);

String _nextTopID(String curTopIDStr, boolean isFirstDigit)
{
    foreach (char c in curTopIDStr)
        if (c != 3) //check if we overflow to the next digit
            break;
        return "1" + "0".repeat(curTopIDStr.Length);
    if(curTopIDStr[0] == "3")
        if(isFirstDigit)
            return ("1" + nextTopID(curTopIDStr[1..], false);
        else
            return ("0" + nextTopID(curTopIDStr[1..], false);       
    else
        curTopIDStr[0]++;
        return curTopIDStr;
}
#15

The first thing I notice is that this is not a true list of the permutations of 4 elements since the first digit is never 0 (forget the first number).

Patterns I noticed (N.B. start counting at n=0)
1 digit: n = 1 to 3
2 digits: n = 4 to 15
3 digits: n = 16 to 63
…
x digits: n = 4^(x-1) to (4^x)-1

The second pattern is the digits themselves. The leading digits are in blocks of 1 (123), the second digits are in groups of 3 (000111222333), the third digits are in groups of 12 (000000000000111111111111222…). Examining the first pattern we see why. Look at the group of 2 digit numbers - there are 12 of them. Divided up into 4 elements we get 12/4 or groups of 3. Look at the group of 3 digit numbers - there are 48 of them. Divided up into 4 elements we get 48/4 or groups of 12.

Putting all of this together, I think your best bet is to contruct the result digit by digit. Let’s say you want the Nth number (bigger than 0 of course). First of all, figure how many digits it will have [1 + trunc(log4 (N))] This would give you your loop parameters.
First digit = N mod 3 (here you have to cheat since it will return the pattern 120. Put in a boolean check like IF a=0 THEN a:=3;)
Second digit = ((N-4) DIV 3) MOD 4
Third digit = ((N-16) DIV 12) MOD 4
Fourth digit = ((N-64) DIV 48) MOD 4
…
Xth digit = ((N-(4^(X-1))) DIV ((4^(X-2))*3) MOD 4

If you need the value of the number, it would be easy to reconstruct from the digits. Since the number is created working left to right but place value is read right to left, I would recommend using a stack to store the digits then calculate the value of the number.

#16

Had a chance to look at it now, and yeah… just keeping the digits in reverse order is a good bit easier (though of course this requires flipping them back around for use.) Probably this is what I’ll do.

My current code is essentially doing the same thing, just manually carrying the overflow over the “wrong” way.