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…)
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.
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.
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
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.)
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.
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.
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.
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.